2014年408数据结构真题

//2014年  解法一：//这道题可以不使用return 返回求得的中间wpl，可以直接用一个全局变量实时的修改这个wpl//使用后序遍历，并且传递对应的深度，一直向下，直到到叶节点 算出对应的wpltypedef struct tnode{    int weight;    struct tnode *lchild,*rchild;}tnode,*tree;int wpl = 0;void postorder_wpl(tnode *p,int depth){if (p == NULL){return;    }    postorder_wpl(p->lchild,depth+1);    postorder_wpl(p->rchild,depth+1);if (p->lchild == NULL && p->rchild ==NULL){        wpl = wpl + p->weight * depth;    }}

//2014年  解法二：
//这是采用递归的方式来写，每一次的递归调用，在宏观上可以认为对应的这一大坨已经处理完了
typedef struct tnode{
    int weight;
    struct tnode *left,*right;
}tnode;

int get_WPL(tnode *root,int high){
if (root == NULL){
return 0;
    }
if (root->left == NULL && root->right == NULL){
return root->weight * high;
    }
    int left_wpl = get_WPL(root->left,high+1);  //在宏观上左子树的wpl已经算完了
    int right_wpl = get_WPL(root->right,high+1);  //在宏观上右子树的wpl已经算完了
return left_wpl + right_wpl;  //最终返回wpl之和
}