三、树（14 题）
三、树（14 题）¶
二叉树默认结构¶
回源 · PDF 第 15 页 ·
b_15_0；PDF 第 15 页 · b_15_41. 判断二叉树是否为正则二叉树¶
正则二叉树中每个结点的度只能为 0 或 2。
bool isRegularBinaryTree(BiTree root) {
if (root == NULL)
return true;
bool hasLeft = root->lchild != NULL;
bool hasRight = root->rchild != NULL;
if (hasLeft != hasRight)
return false;
return isRegularBinaryTree(root->lchild)
&& isRegularBinaryTree(root->rchild);
}
复杂度： 时间 O(n)，递归栈空间 O(h)；最坏情况下 h=n。
回源 · PDF 第 15 页 ·
b_15_7；PDF 第 15 页 · b_15_8；PDF 第 15 页 · b_15_9；PDF 第 15 页 · b_15_102. 将二叉表达式树转为等价中缀表达式（2017 年统考题）¶
void printInfix(BiTree root, int depth) {
if (root == NULL)
return;
bool isOperator = root->lchild != NULL || root->rchild != NULL;
if (isOperator && depth > 0)
printf("(");
printInfix(root->lchild, depth + 1);
printf("%c", root->data);
printInfix(root->rchild, depth + 1);
if (isOperator && depth > 0)
printf(")");
}
调用方式：printInfix(root, 0);。
复杂度： 时间 O(n)，递归栈空间 O(h)。
核心思路： 按中序遍历输出；除根结点外，每棵非叶子子树外加括号，从而保持原表达式树的运算次序。
回源 · PDF 第 15 页 ·
b_15_2；PDF 第 15 页 · b_15_53. 计算二叉表达式树的值¶
下面假设叶子结点为字符 '0'..'9'，内部结点为 +、-、*、/。
int evaluateExpressionTree(BiTree root) {
if (root->lchild == NULL && root->rchild == NULL)
return root->data - '0';
int left = evaluateExpressionTree(root->lchild);
int right = evaluateExpressionTree(root->rchild);
switch (root->data) {
case '+': return left + right;
case '-': return left - right;
case '*': return left * right;
case '/': return left / right;
default: return 0; // 实际程序中应报告非法运算符
}
}
复杂度： 时间 O(n)，递归栈空间 O(h)。
若叶子是变量（如
a、b），需另行传入变量到数值的映射；若允许除数为零，也必须增加错误处理。
回源 · PDF 第 15 页 ·
b_15_3；PDF 第 15 页 · b_15_64. 输出根结点到每个叶子结点的路径¶
void printRootToLeafPaths(BiTree root, char path[], int depth) {
if (root == NULL)
return;
path[depth] = root->data;
depth++;
if (root->lchild == NULL && root->rchild == NULL) {
for (int i = 0; i < depth; i++)
printf("%c%s", path[i], i + 1 == depth ? "\n" : " -> ");
return;
}
printRootToLeafPaths(root->lchild, path, depth);
printRootToLeafPaths(root->rchild, path, depth);
}
复杂度： 遍历时间 O(n)，加上输出本身所需时间；辅助数组和递归栈均为 O(h)。
若要按“叶子到根”输出，只需在叶子处将循环改为从 depth-1 递减到 0。
回源 · PDF 第 16 页 ·
b_16_1；PDF 第 16 页 · b_16_0；PDF 第 16 页 · b_16_65. 增加 parent 指针并输出每个结点到根的路径¶
typedef struct ParentBTNode {
char data;
struct ParentBTNode *lchild;
struct ParentBTNode *rchild;
struct ParentBTNode *parent;
} ParentBTNode, *ParentBiTree;
void setParents(ParentBiTree root, ParentBiTree parent) {
if (root == NULL)
return;
root->parent = parent;
setParents(root->lchild, root);
setParents(root->rchild, root);
}
void printAllPathsToRoot(ParentBiTree root) {
if (root == NULL)
return;
for (ParentBiTree p = root; p != NULL; p = p->parent)
printf("%c%s", p->data, p->parent == NULL ? "\n" : " -> ");
printAllPathsToRoot(root->lchild);
printAllPathsToRoot(root->rchild);
}
先调用 setParents(root, NULL)，再调用 printAllPathsToRoot(root)。
复杂度： 设置双亲指针为 O(n)；输出全部路径最坏为 O(nh)，递归栈为 O(h)。
校订注：原稿将“输出所有结点到根路径”的总时间直接标为
O(n)，忽略了路径输出量；在退化树中总输出长度可达O(n²)。
回源 · PDF 第 16 页 ·
b_16_26. 求结点 p、q 的最近公共祖先¶
回源 · PDF 第 16 页 ·
b_16_4链式存储¶
BiTree lowestCommonAncestor(BiTree root, BiTree p, BiTree q) {
if (root == NULL || root == p || root == q)
return root;
BiTree left = lowestCommonAncestor(root->lchild, p, q);
BiTree right = lowestCommonAncestor(root->rchild, p, q);
if (left != NULL && right != NULL)
return root;
return left != NULL ? left : right;
}
复杂度： 时间 O(n)，递归栈空间 O(h)。假定 p、q 均存在于树中。
回源 · PDF 第 16 页 ·
b_16_4；PDF 第 16 页 · b_16_3顺序存储（下标从 0 开始）¶
BiTree lowestCommonAncestorInArray(BiTree nodes[], int i, int j) {
while (i != j) {
if (i > j)
i = (i - 1) / 2;
else
j = (j - 1) / 2;
}
return nodes[i];
}
复杂度： 时间 O(h)，额外空间 O(1)；对完全二叉树有 h=O(log n)。
回源 · PDF 第 16 页 ·
b_16_5；PDF 第 16 页 · b_16_77. 用层序遍历求二叉树高度¶
int treeHeightByLevelOrder(BiTree root) {
if (root == NULL)
return 0;
BiTree queue[MAXSIZE];
int front = 0, rear = 0;
int height = 0;
queue[rear++] = root;
while (front < rear) {
int levelEnd = rear;
while (front < levelEnd) {
BiTree node = queue[front++];
if (node->lchild != NULL)
queue[rear++] = node->lchild;
if (node->rchild != NULL)
queue[rear++] = node->rchild;
}
height++;
}
return height;
}
复杂度： 时间 O(n)，队列空间 O(n)。
校订注：原稿在
if (bt != NULL)与函数末尾附近多出一个右花括号，且空树路径没有明确返回值；本版已整理。
回源 · PDF 第 17 页 ·
b_17_0；PDF 第 17 页 · b_17_1；PDF 第 17 页 · b_17_38. 计算二叉树的带权路径长度 WPL（2014 年统考题）¶
这道题的“权重”必须是数值，不能直接复用本章默认的 char data：若叶子保存字符 '5'，直接参与乘法会得到字符编码而不是数值 5。因此为 WPL 单独使用含 int weight 的结点类型，根的深度规定为 0。
typedef struct WeightedBTNode {
int weight;
struct WeightedBTNode *lchild;
struct WeightedBTNode *rchild;
} WeightedBTNode, *WeightedBiTree;
校订注：回源块中的原稿沿用二叉树默认的
char data参与 WPL；下列WeightedBTNode与int weight是本版为消除字符编码歧义而给出的校订实现。
回源 · PDF 第 17 页 ·
b_17_4递归法¶
long long weightedPathLength(WeightedBiTree root, int depth) {
if (root == NULL)
return 0;
if (root->lchild == NULL && root->rchild == NULL)
return (long long)root->weight * depth;
return weightedPathLength(root->lchild, depth + 1)
+ weightedPathLength(root->rchild, depth + 1);
}
调用方式：weightedPathLength(root, 0)。
回源 · PDF 第 17 页 ·
b_17_4；PDF 第 17 页 · b_17_5层序遍历法¶
long long weightedPathLengthByLevel(WeightedBiTree root) {
if (root == NULL)
return 0;
WeightedBiTree queue[MAXSIZE];
int front = 0, rear = 0;
int depth = 0;
long long wpl = 0;
queue[rear++] = root;
while (front < rear) {
int levelEnd = rear;
while (front < levelEnd) {
WeightedBiTree node = queue[front++];
if (node->lchild == NULL && node->rchild == NULL)
wpl += (long long)node->weight * depth;
if (node->lchild != NULL)
queue[rear++] = node->lchild;
if (node->rchild != NULL)
queue[rear++] = node->rchild;
}
depth++;
}
return wpl;
}
复杂度： 两种方法时间均为 O(n)；递归法栈空间 O(h)，层序法队列空间 O(n)。
回源 · PDF 第 17 页 ·
b_17_6；PDF 第 17 页 · b_17_89. 求二叉树的宽度¶
int maxTreeWidth(BiTree root) {
if (root == NULL)
return 0;
BiTree queue[MAXSIZE];
int front = 0, rear = 0;
int maxWidth = 0;
queue[rear++] = root;
while (front < rear) {
int levelEnd = rear;
int width = levelEnd - front;
if (width > maxWidth)
maxWidth = width;
while (front < levelEnd) {
BiTree node = queue[front++];
if (node->lchild != NULL)
queue[rear++] = node->lchild;
if (node->rchild != NULL)
queue[rear++] = node->rchild;
}
}
return maxWidth;
}
复杂度： 时间 O(n)，队列空间 O(n)。
递归法也可用 count[level] 统计每层结点数，遍历结束后取数组最大值；其递归栈为 O(h)，层计数数组为 O(h)。
回源 · PDF 第 18 页 ·
b_18_0；PDF 第 18 页 · b_18_2；PDF 第 17 页 · b_17_710. 判断二叉树是否为满二叉树¶
这里“满二叉树”指高度为 h 时恰有 2^h-1 个结点的二叉树。
void countNodesAndHeight(BiTree root, int depth,
int *nodeCount, int *height) {
if (root == NULL)
return;
(*nodeCount)++;
if (depth > *height)
*height = depth;
countNodesAndHeight(root->lchild, depth + 1, nodeCount, height);
countNodesAndHeight(root->rchild, depth + 1, nodeCount, height);
}
bool isFullBinaryTree(BiTree root) {
int nodeCount = 0;
int height = 0;
countNodesAndHeight(root, 1, &nodeCount, &height);
long long expected = (1LL << height) - 1;
return nodeCount == expected;
}
复杂度： 时间 O(n)，递归栈空间 O(h)。
回源 · PDF 第 18 页 ·
b_18_1；PDF 第 18 页 · b_18_411. 满二叉树先序序列与后序序列互转¶
满二叉树的左右子树结点数相等，因此可以直接按区间长度折半。
void preorderToPostorder(char pre[], int preL, int preR,
char post[], int postL, int postR) {
if (preL > preR)
return;
post[postR] = pre[preL];
if (preL == preR)
return;
int subtreeSize = (preR - preL) / 2;
preorderToPostorder(pre, preL + 1, preL + subtreeSize,
post, postL, postL + subtreeSize - 1);
preorderToPostorder(pre, preL + subtreeSize + 1, preR,
post, postL + subtreeSize, postR - 1);
}
void postorderToPreorder(char post[], int postL, int postR,
char pre[], int preL, int preR) {
if (postL > postR)
return;
pre[preL] = post[postR];
if (postL == postR)
return;
int subtreeSize = (postR - postL) / 2;
postorderToPreorder(post, postL, postL + subtreeSize - 1,
pre, preL + 1, preL + subtreeSize);
postorderToPreorder(post, postL + subtreeSize, postR - 1,
pre, preL + subtreeSize + 1, preR);
}
复杂度： 时间 O(n)，递归栈空间 O(h)。
回源 · PDF 第 19 页 ·
b_19_0；PDF 第 19 页 · b_19_212. 根据遍历序列建立二叉链表¶
回源 · PDF 第 19 页 ·
b_19_5先序序列 + 中序序列¶
BiTree buildFromPreIn(char pre[], int preL, int preR,
char in[], int inL, int inR) {
if (preL > preR || inL > inR)
return NULL;
BiTree root = (BiTree)malloc(sizeof(BTNode));
root->data = pre[preL];
int split = inL;
while (split <= inR && in[split] != root->data)
split++;
int leftSize = split - inL;
root->lchild = buildFromPreIn(pre, preL + 1, preL + leftSize,
in, inL, split - 1);
root->rchild = buildFromPreIn(pre, preL + leftSize + 1, preR,
in, split + 1, inR);
return root;
}
回源 · PDF 第 19 页 ·
b_19_5；PDF 第 19 页 · b_19_4后序序列 + 中序序列¶
BiTree buildFromPostIn(char post[], int postL, int postR,
char in[], int inL, int inR) {
if (postL > postR || inL > inR)
return NULL;
BiTree root = (BiTree)malloc(sizeof(BTNode));
root->data = post[postR];
int split = inL;
while (split <= inR && in[split] != root->data)
split++;
int leftSize = split - inL;
root->lchild = buildFromPostIn(post, postL, postL + leftSize - 1,
in, inL, split - 1);
root->rchild = buildFromPostIn(post, postL + leftSize, postR - 1,
in, split + 1, inR);
return root;
}
复杂度： 上述直接线性查找中序根位置的写法，最坏时间 O(n²)，递归栈 O(h)；若预先建立“元素值到中序下标”的哈希映射，可将时间降为 O(n)。
回源 · PDF 第 19 页 ·
b_19_113. 二叉链表与顺序存储数组互转¶
回源 · PDF 第 19 页 ·
b_19_3二叉链表转数组¶
void treeToArray(BiTree root, char A[], int index, int capacity) {
if (root == NULL || index >= capacity)
return;
A[index] = root->data;
treeToArray(root->lchild, A, 2 * index + 1, capacity);
treeToArray(root->rchild, A, 2 * index + 2, capacity);
}
调用前应将数组所有位置初始化为表示空结点的 '#'。
回源 · PDF 第 19 页 ·
b_19_3；PDF 第 19 页 · b_19_6数组转二叉链表¶
BiTree arrayToTree(char A[], int index, int n) {
if (index >= n || A[index] == '#')
return NULL;
BiTree root = (BiTree)malloc(sizeof(BTNode));
root->data = A[index];
root->lchild = arrayToTree(A, 2 * index + 1, n);
root->rchild = arrayToTree(A, 2 * index + 2, n);
return root;
}
复杂度： 对有效数组范围进行递归访问，时间 O(n)，递归栈空间 O(h)；稀疏且很深的树使用顺序存储可能浪费大量数组空间。
回源 · PDF 第 19 页 ·
b_19_614. 统计顺序存储二叉树的叶子结点数¶
int countArrayLeaves(char A[], int index, int n) {
if (index >= n || A[index] == '#')
return 0;
int left = 2 * index + 1;
int right = 2 * index + 2;
bool leftEmpty = left >= n || A[left] == '#';
bool rightEmpty = right >= n || A[right] == '#';
if (leftEmpty && rightEmpty)
return 1;
return countArrayLeaves(A, left, n)
+ countArrayLeaves(A, right, n);
}
复杂度： 时间 O(n)，递归栈空间 O(h)。
回源 · PDF 第 20 页 ·
b_20_0；PDF 第 20 页 · b_20_2