二叉树的带权路径长度WPL算法实现 |
您所在的位置：网站首页 › 权值wpl › 二叉树的带权路径长度WPL算法实现 |
|
文章目录
题目描述算法思想实现代码
题目描述
二叉树的带权路径长度WPL是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树，采用二叉链表存储，叶子结点的weight域为该结点的权值。请设计一个算法，求二叉树的带权路径长度。 算法思想可以使用先序遍历或层次遍历解决问题。 算法思想一：基于先序递归遍历。 用一个static变量记录WPL，把每个结点的深度作为递归函数的一个参数传递。 若该结点是叶结点，则变量WPL加上该结点的深度与权值之和。若该结点是非叶结点，则左子树不为空时，对左子树调用递归算法，右子树不为空时，对右子树调用递归算法，深度参数均为本结点的深度参数加1。算法思想二：基于层序遍历。 使用队列进行层次遍历，并记录当前的层数。 当遍历到叶结点时，累计WPL。当遍历到非叶结点时，把该结点的子树加入队列。当某结点为该层最后一个结点时，层数自增1。队列空时遍历结束，返回WPL。 实现代码算法一的函数代码实现： int WPL_PreOrder(BTree root, int deep){ static int wpl = 0; if(root->lchild==NULL && root->rchild==NULL){ //若为叶结点，累积 wpl += deep*root->weight; } if(root->lchild != NULL){ //若左子树不空，对左子树递归遍历 WPL_PreOrder(root->lchild, deep+1); } if(root->rchild != NULL){ //若右子树不空，对右子树递归遍历 WPL_PreOrder(root->rchild, deep+1); } return wpl; }算法二的函数代码实现： int WPL_Level(BTree root){ queue treenode; //队列 int wpl = 0; int deep = 0; //初始化深度 BNode *lastNode; //记录当前最后一个结点 BNode *newlastNode; //记录下一层最后一个结点 lastNode = root; //初始化为根结点 newlastNode = NULL; //初始化为空 treenode.push(root); //根结点入队 while(!treenode.empty()){ //栈不空时循环 BNode *top = treenode.front(); //取出队首元素 treenode.pop(); if(top->lchild==NULL && top->rchild==NULL){ wpl += deep*top->weight; }//若为叶结点，累加 if(top->lchild != NULL){ //若为非叶结点则把左孩子结点入队 treenode.push(top->lchild); newlastNode = top->lchild; //设置下一层最后一个结点 } if(top->rchild != NULL){ //右孩子结点入队 treenode.push(top->rchild); newlastNode = top->rchild; } if(top == lastNode){ //若该结点为本层最后一个结点 lastNode = newlastNode; //更新 deep+=1; //深度加1 } } return wpl; } |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |