4树
原始讲义 · 非增强校订版 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 4树
由2014年真题引入
【2014年真题，15分】二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构如下：
<table><tr><td>left 看伽</td><td>weight</td><td>right</td></tr></table>
其中叶结点的 weight 域保存该结点的非负权值。设 root 为指向T的根结点的指针，请设计求T的 WPL的算法，要求：1）给出算法的基本设计思想。
2） 使用C或C++语言，给出二叉树结点的数据类型定义。
3）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
<!-- page 107 -->
<!-- code-audit: false_positive -->
> [!info] 已人工审读：这是存储结构示意图标题，不是 C 代码。
<!-- verified-by-hand -->
> [!success] 已结合原文第 107 页及 Markdown 上下文人工校对
> 结构体定义缺少左花括号。
typedef struct BTNode
{
ElemType data;
struct BTNode *lchild, *rchild;
} BTNode;
typedef struct TNode
{
ElemType data;
struct TNode *firstchild, *nextbro;
} TNode;
typedef struct TNode
{
Elemtype data;
struct TNode *father;
}TNode;
//保存每个结点的父亲结点在数组中的下标
//每个结点的权值
//father是指向该结点父亲结点的指针
//树结点
typedef struct
{
int SqBiTNode[MAX_SIZE];
int ElemNum;
} SqBiTree;
原资料配图 · 转写内容请回源核验
## 4.2 树的递归遍历
树的遍历是408代码题的常考点，包括2014、2017、2022年，只要考察树必然需要用到遍历，一般是考察树的遍历+某种树的定义（如二叉搜索树），而二叉树的遍历包括先序中序后序遍历，他们又分为递归和非递归两种方式，每一种遍历的非递归逻辑都完全不一样，复习起来很痛苦也没有必要，而递归的代码逻辑非常简单，所以考试中除了特殊情况，树的遍历请一定使用递归（递归简单好用）。
<!-- page 109 -->
## 4.2.1 二叉树的递归遍历
递归，从本质上讲，是分治思想的一种完美体现。分治策略就是“分而治之”，它将一个复杂的大问题分解成若干个规模更小、但结构与原问题相同的子问题，然后逐个解决。 W
在二叉树的遍历中，分:将“遍历整棵树”这个大问题，分解为三个更小的问题：
• 访问根结点本身。
• 遍历左子树（一个规模更小的相同问题）。
• 遍历右子树（另一个规模更小的相同问题）。
因此，我们可以把递归想象成一个“任务分包”的过程。你作为“总指挥”，只需要应用分治思想，关注当前结点，并把子树的任务“外包”出去。 m
处理二叉树我们总共需要完成三个工作：
• 处理好你当前手头的工作（即访问结点 p 本身）。
• 把遍历左子树的整个任务，完全甩给你的“左下属”（处理左子树 order(p->lchild））。
• 把遍历右子树的整个任务，完全甩给你的“右下属”（处理右子树 order(p->rchild)）。
核心信念：当你调用 order(p->lchild) 时，你不需要关心它内部是如何一步步执行的。你只需要完全信任这个调用，相信它一旦执行，就一定能帮你把整个左子树完美地遍历一遍。同理，order(p->rchild)也一样。
有了这个“信任”，你的工作就变得极其简单：你只需要考虑三件事（访问自己、调用左下属、调用右下属）的执行顺序即可。把复杂的大问题，分解成了在当前结点的一个极小问题。
<!-- code-audit: false_positive -->
> [!info] 已人工审读：整块是讲解先中后序步骤的中文提纲，不是可编译代码。
遍历 order
• 先序遍历 PreOrder:
1. 访问自己 visit(p);
2. 调用左 PreOrder(p->lchild);
3. 调用右 PreOrder(p->rchild);
• 中序遍历 InOrder:
1. 调用左 InOrder(p->Ichild);
2. 访问自己 visit(p);
3. 调用右 InOrder(p->rchild);
• 后序遍历 PostOrder:
1. 调用左 PostOrder(p->Ichild);
2. 调用右 PostOrder(p->rchild);
3. 访问自己 visit(p);
先访问自己是先序,在中间访问自己是中序,最后访问自己是后序
//先序（根左右）
void PreOrder(BTNode *p)
{
if (p==NULL) return;
visit(p);
Preorder(p->lchild);
Preorder(p->rchild);
}
void TreePreOrder(TNode *T)
{
if (T == NULL) return;
visit(T);
TreePreOrder(T->firstchild);
TreePreOrder(T->nextbro);
}
void InOrder(BTNode *p)
{
if (p == NULL) return;
InOrder(p->lchild);
visit(p);
InOrder(p->rchild);
}
void PostOrder(BTNode *p)
{
if (p == NULL) return;
PostOrder(p->lchild);
PostOrder(p->rchild);
visit(p);
}
void TreePostorder(TNode *T)
{
if (T == NULL) return;
TreePostorder(T->firstchi1d); //先访问所有孩子
visit(T); //最后访问根
TreePostorder(T->nextbro); // 然后访问兄弟结点
}
原资料配图 · 转写内容请回源核验
原资料配图 · 转写内容请回源核验
二叉树结点定义如下：
typedef struct node{
char data[10];
struct node *left, *right;
}BTree;
• 中序遍历 (InOrder): 左 -> 根 -> 右
//需要返回值
int InOrder(BTNode *p) // 返回类型不一定是int
{
if (p==NULL) return 返回值;
Inorder(p->lchild); // 调用根据题目修改
visit(p); //是最重要的部分，根据题目要求决定
Inorder(p->rchild);
return xx;
// 不需要返回值
void InOrder(BTNode *p)
{
if (p==NULL) return;
Inorder(p->lchild); // 调用根据题目修改
visit(p); //是最重要的部分，根据题目要求决定
Inorder(p->rchild);
}
}
printf("%s", p->data); //输出操作数
int InOrder(BTNode *p)
{
if (p==NULL) return 返回值;
Inorder(p->lchild); // 调用根据题目修改
visit(p); // 是最重要的部分，根据题目要求决定
Inorder(p->rchild);
return // 返回值;
}
void ans(BTNode *T)
{
输出InOrder(T); om
完成其他工作
}
void InOrder(BTNode *p)
{
if (p==NULL) return; // p是空结点
Inorder(p->lchild); // 递归调用左子树
visit(p);
Inorder(p->rchild); // 递归调用右子树
}
void InOrder(BTNode *p)
{
if (p==NULL) return; // p是空结点
Inorder(p->lchild); //递归调用左子树
printf("%s", p->data); //输出操作数
Inorder(p->right, root); //递归调用右子树
} 专研
void InOrder(BTree* p, BTree* root) // root是原二叉树的根
{
if (p==NULL) return; // p是空结点
if ((p->left!=NULL || p->right!=NULL) && (p!=root))
printf("(");
Inorder(p->left, root); // 递归调用左子树
printf("%s", p->data); //输出操作数
Inorder(p->right, root); // 递归调用右子树
if ((p->left!=NULL || p->right!=NULL) && (p!=root))
printf(")");
}
int WPL = 0;
void PreOrder(BTNode *p, int depth)
{
if (p == NULL) return;
if (p->left == NULL && p->right == NULL)
WPL += depth * p->weight;
PreOrder(p->left, depth + 1);
PreOrder(p->right, depth + 1);
}