本文主要是介绍考研408 2014年第41题（二叉树带权路径长度【WPL】），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
function.h(结构体)：
//
// Created by legion on 2024/3/5.
//#ifndef INC_14_4_TREE_FUNCTION_H
#define INC_14_4_TREE_FUNCTION_H
#include <stdio.h>
#include <stdlib.h>typedef int BiElemType;
typedef struct BiTNode{BiElemType weight;//直接拿字符的ASCII值来计算即可struct BiTNode *lchild;struct BiTNode *rchild;
}BiTNode,*BiTree;//tag结构体是辅助队列使用的 队列是由链表实现的
typedef struct tag{BiTree p;//树的某一个结点的地址值struct tag *pnext;
}tag_t,*ptag_t;//这个链表结构体类型tag_t 为什么和结构体名不一致//辅助队列 的结构体
typedef BiTree ElemType;
typedef struct LinkNode{ElemType data;//struct LinkNode *next;
}LinkNode;
typedef struct{//队列结构体LinkNode *front,*rear;//链表头 链表尾 可以称为队头 队尾
}LinkQueue;//先进先出void InitQueue(LinkQueue &Q);
//入队bool IsEmpty(LinkQueue Q);void EnQueue(LinkQueue &Q,ElemType x);//不修改故不引用
//出队
bool DeQueue(LinkQueue &Q,ElemType &x);//出队后有可能发生real指向头指针 Q有可能发生改变 所以引用#endif //INC_14_4_TREE_FUNCTION_H
queue.cpp(函数)：
//
// Created by legion on 2024/3/7.
//
#include "function.h"//队列的初始化，使用的是带头结点的链表来实现的
void InitQueue(LinkQueue &Q)
{Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));Q.front->next==NULL;
}//判断队列是否为空
bool IsEmpty(LinkQueue Q)
{return Q.rear==Q.front;
}//入队
void EnQueue(LinkQueue &Q,ElemType x)//不修改故不引用
{LinkNode *pnew=(LinkNode*)malloc(sizeof(LinkNode));pnew->data=x;pnew->next=NULL;//要让next为NULLQ.rear->next=pnew;//尾指针的next指向pnew，因为从尾部入队Q.rear=pnew;//rear要指向新的尾部}//出队
bool DeQueue(LinkQueue &Q,ElemType &x)//出队后有可能发生real指向头指针 Q有可能发生改变 所以引用
{if(Q.rear==Q.front)//队列为空{return false;}LinkNode* q=Q.front->next;//拿到第一个结点，存入qx=q->data;Q.front->next=q->next;//让第一个结点断链if(Q.rear==q)//链表只剩余一个结点时，被删除后，要改变rear{Q.rear=Q.front;}free(q);return true;}main.cpp:
#include "function.h"//int wpl=0;
//前序遍历函数,也叫先序遍历，也是深度优先遍历
int PreOrder(BiTree p,int deep)//只是遍历 即只是读，不会改变树根
{//这个p的类型是 树的结构体 不是之前的p指针static int wpl=0;//静态局部变量，存储在数据段内，所以只会初始化一次//while循环中只会走一次 ，区别于全局变量 只能在函数内访问，所以最后要return出去if(p!=NULL){
// printf("ele%c--%d\n", p->c,deep);if(p->lchild==NULL&&p->rchild==NULL){wpl=wpl+p->weight*deep;}PreOrder(p->lchild,deep+1);//函数嵌套 打印左子树PreOrder(p->rchild,deep+1);//函数嵌套 打印右子树}return wpl;}
//中序遍历
void InOrder(BiTree p)//只是遍历 即只是读，不会改变树根
{//这个p的类型是 树的结构体 不是之前的p指针if(p!=NULL){InOrder(p->lchild);//函数嵌套 打印左子树printf("%c", p->weight);InOrder(p->rchild);//函数嵌套 打印右子树}
}
//后续遍历
void PostOrder(BiTree p)//只是遍历 即只是读，不会改变树根
{//这个p的类型是 树的结构体 不是之前的p指针if(p!=NULL){PostOrder(p->lchild);//函数嵌套 打印左子树PostOrder(p->rchild);//函数嵌套 打印右子树printf("%c", p->weight);}
}//层序遍历
//层次遍历 层序遍历 广度优先遍历
void LevelOrder(BiTree T)//树的结构体指针 有左孩子和有孩子
{LinkQueue Q;//定义一个队列QInitQueue(Q);//初始化队列Q 队头等于队尾 next指针指向NULLBiTree p;//存储出队的结点 p为一个树的结构体指针EnQueue(Q,T);//把根入队while(!IsEmpty(Q))//队列不为空才进入到循环当中{DeQueue(Q,p);putchar(p->weight);//等价于printf("%c",c);if(p->lchild){EnQueue(Q,p->lchild);//左孩子不为空 入队左孩子}if(p->rchild){EnQueue(Q,p->rchild);}}}int main() {BiTree pnew;//用来指向新申请的树结点 结构体指针类型BiTree tree=NULL;//tree是指向树根的，代表树char c;//定义队列 phead是队列头ptail是队列尾 listpnew指向新结点 pcur是指向当前父结点ptag_t phead=NULL,ptail=NULL,listpnew=NULL,pcur;//输入abcdefghijwhile(scanf("%c",&c)){if(c=='\n'){break;//读取换行结束}//calloc申请的空间大小是两个参数直接相乘，并对空间进行初始化，赋值为0pnew= (BiTree)calloc(1,sizeof(BiTNode));pnew->weight=c;//数据放进去listpnew= (ptag_t)calloc(1,sizeof(tag_t));//给队列结点申请空间listpnew->p=pnew;if(NULL==tree)//如果树为空 放进去即为树根{tree=pnew;//树的根phead=listpnew;//队列头ptail=listpnew;//队列尾pcur=listpnew;continue;} else{ptail->pnext=listpnew;//新结点放入链表 通过尾插法ptail=listpnew;//ptail指向队列尾部}//pcur始终指向要插入的结点的位置if(NULL==pcur->p->lchild){pcur->p->lchild=pnew;//把新结点放到要插入结点的左边} else if(NULL==pcur->p->rchild){pcur->p->rchild=pnew;//把新结点放到要插入结点的右边pcur=pcur->pnext;//左右都放了结点后，pcur指向队列下一个}}//14.5二叉树的前序中序后续遍历printf("------------PreOrder------------\n");
// printf("\n------------InOrder------------\n");
// InOrder(tree);
// printf("\n------------PostOrder------------\n");
// PostOrder(tree);
// printf("\n------------LevelOrder------------\n");
// LevelOrder(tree);printf("wpl=%d\n",PreOrder(tree,0));//叶子结点层数为3时其实际路径为2return 0;
}
这篇关于考研408 2014年第41题（二叉树带权路径长度【WPL】）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
