二叉树带权路径长度WPL

路径长度WPL"/>

二叉树带权路径长度WPL

二叉树的带权路径长度的公式如下:
WPL = 叶子节点的权重*该叶子节点所位于的层数
根节点算做第0层

#include <iostream>using namespace std;typedef struct node {int weight;struct node *left;struct node *right;
} TNode;TNode *CreateTree(TNode *&t);int WPL(TNode *t, int d);int wpl = 0;//记录叶子节点的带权路径长度int main() {auto t = new TNode;CreateTree(t);WPL(t, 0);cout << wpl << endl;return 0;
}TNode *CreateTree(TNode *&t) {int c;cin >> c;if (c < 0)t = nullptr;else {t = new TNode;t->weight = c;t->left = CreateTree(t->left);t->right = CreateTree(t->right);}return t;
}
//除根节点以外所有节点的带权路径长度
//int WPL(TNode *t, int d) {
//    if (t != nullptr) {
//        wpl += d * t->weight;
//        wpl = WPL(t->left, d + 1);
//        wpl = WPL(t->right, d + 1);
//    }
//    return wpl;
//}// 叶子节点的带权路径长度
int WPL(TNode *t,int d){if (t->right== nullptr&&t->left== nullptr){wpl += d *t->weight;} else{WPL(t->left,d+1);WPL(t->right,d+1);}return wpl;
}