二叉树的遍历
二叉树的遍历
复习定位
二叉树的遍历是指按一定顺序访问树中的所有结点——每个结点只访问一次。先序/中序/后序的递归定义非常简单——非递归实现使用栈记录需要回溯的路径。层序使用队列逐层访问。根据遍历序列重建二叉树是常见考题——必须已知中序+(前序或后序)之一才能唯一重建。
三种深度优先遍历
先序(Preorder, NLR)——访问根 → 先序遍历左子树 → 先序遍历右子树。
中序(Inorder, LNR)——中序遍历左子树 → 访问根 → 中序遍历右子树。在二叉搜索树(BST)上——中序遍历得到升序序列。
后序(Postorder, LRN)——后序遍历左子树 → 后序遍历右子树 → 访问根。常用于释放二叉树(先释放子节点再释放根结点)。
每种遍历的递归实现只需几行代码——但是理解递归栈的调用过程更关键。
非递归遍历
以中序为例——使用显式栈模拟：
void inorder_nonrecursive(Node *root) {
Stack *S = createStack();
Node *p = root;
while (p != NULL || !isEmpty(S)) {
while (p != NULL) { // 一路向左——压栈
push(S, p);
p = p->left;
}
p = pop(S); // 弹栈——访问结点
printf("%d ", p->data);
p = p->right; // 转向右子树
}
}先序非递归只需将访问操作在第一次遇到结点时进行(压栈前)——后序非递归比较麻烦——可以使用"双栈法"(一个栈做类似先序在右子树优先的对应/另一个栈逆序输出结果)。
层序遍历
使用队列——根先入队——出队一个结点——访问——将其左右孩子入队——直到队列为空。
void level_order(Node *root) {
Queue *Q = createQueue();
enqueue(Q, root);
while (!isEmpty(Q)) {
Node *p = dequeue(Q);
printf("%d ", p->data);
if (p->left) enqueue(Q, p->left);
if (p->right) enqueue(Q, p->right);
}
}层序常用于在树中查找最短路径(无权)——求树的高度——或输出二叉树到控制台。
根据遍历序列重建二叉树
给定前序+中序或后序+中序——唯一确定二叉树。前序第一个(或后序最后一个)是根——在中序中找到根——左边是左子树序列右边是右子树——递归。
唯一确定需要中序的原因——中序能清晰区分左子树和右子树(根的位置在中间)。前序+后序不能唯一确定——因为无法知道某个结点属于左子树还是右子树。
线索二叉树
n个结点的二叉树有2n个指针域——其中n+1个是NULL。线索化将这些空指针利用起来——指向中序遍历的前驱或后继(称为线索)。
增加两个标记ltag/rtag——0表示child指针，1表示线索。中序线索化后——可以不用递归从任一结点开始沿后继线索完成中序遍历——无需栈——O(n)时间——对遍历频繁的场合有效。
复习检查
先序、中序、后序三种递归遍历的区别——"序"指的是什么时候访问根结点——先序先访问根——中序在中间——后序在最后。
中序遍历二叉搜索树的结果顺序——升序排列——这是BST的一条重要性质——可以用于验证BST和各种相关算法。
非递归中序遍历为什么适合用作将二叉树转化为排序双链表——中序遍历依次访问各个结点——可以将它们串起来。
前序+中序确定唯一二叉树——前序的第一个结点是根——在中序中找到根后——左侧的序列是左子树——右侧是右子树——递归此过程。
为什么前序+后序不可以唯一确定二叉树——假设根只有一个子结点——前序序列为NLR——后序为LRN——无法判断这个子结点是左还是右？