C++ 数据结构

二叉树的遍历与重构

Posted by Hazuki on 2019-02-28

清华大学 邓俊辉 数据结构 学习笔记

遍历

V 父节点

L 左子树

R 右子树

先序遍历：V->L->R

中序遍历：L->V->R

后序遍历：L->R->V

层次（广度）：自上而下，先左后右

先序遍历

递归实现
1
2
3
4
5
6
7
8
template <typename T, typename VST>
void traverse(BinNodePosi(T) x, VST & visit)
{
    if (!x) return;
    visit (x->data);
    traverse(x->lchild, visit);
    traverse(x->rchild, visit);
} // T(n) = O(1) + T(a) + T(n-a-1) = O(n) 渐进

由于递归的实现机制，并不能做到每次递归的帧都足够小

迭代实现
1
2
3
4
5
6
7
8
9
10
11
12
template <typename T, typename VST>
void travPre_I1(BinNodePosi(T) x, VST& visit)
{
    stack <BinNodePosi(T)> s;// 辅助栈
    if (x) S.push(x); // 根节点入栈
    while (!s.empty()) // 在栈变空之前反复循环
    {
        x = S.pop(); visit(x->data); // 弹出并访问当前节点
        if (HasRChild(*)) S.push(x->rChild); // 右孩子先入后出
        if (HasLChild(*)) S.push(x->lchild); // 左孩子后入先出
    }
}

新算法

宏观过程：自顶向下依次遍历左子树，自底向上依次遍历右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template <typename T, typename VST> // 分摊O(1)
static void visitAlongLeftBranch(
    BinNodePosi(T) x, 
    VST & visit, 
    stack <BinNodePosi(T)> &S)
{
    while (x) // 反复地
    {
        visit(x->data); // 访问当前节点
        S.push(x->rChild); // 右子树入栈（将来逆序出栈）
        x = x->lChild; // 沿左侧链下行
    } // 只有右孩子、NULL 可能入栈
}

template <typename T, typename VST>
void travPre_I2(BinNodePosi(T) x, VST & visit)
{
    stack <BinNodePosi(T)> S; // 辅助栈
    while (true) // 以（右）子树为单位，逐批访问节点
    {
        visitAlongLeftBranch(x, visit, S); // 访问子树x的左侧链，右子树入栈缓冲
        if (S.empty()) break; // 栈空即退出
        x = S.pop(); // 弹出下一子树的根
    } // #pop = #push = #visit = O(n) = 分摊O(1)
}

中序遍历

递归
1
2
3
4
5
6
7
8
tmeplate <typename T, typename VST>
void traverse(BinNodePosi(T) x, VST & visit)
{
    if (!x) return;
    traverse(x->lChild, visit);
    visit(x->data);
    traberse(x->rChild, visit);
} // T(n) = T(a) + O(1) + T(n-a-1) = O(n)
迭代

从根节点开始沿左侧分支往下找到第一个访问的节点。

从根节点开始，访问左孩子和左孩子的右子树，再访问根节点，访问根节点的右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <typename T>
static void goAlongLetBranch( BinNodePosi(T) x, Stack <BinNodePosi(T)> & s)
{
    while (x) // 反复地入栈，沿左分支深入
    {
        s.push(x);
        x = x->lChild;
    }
}
template <typename T, typename V> void travIn_I1( BinNodePosi(T) x, V& visit)
{
    Stack <BinNodePosi(T)> S; // 辅助栈
    while (true) // 反复地
    {
        goAlongLeftBranch (x, s); // 从当前节点出发，逐批入栈
        if (s.empty())
            break; // 直至所有节点处理完毕
        x = S.pop(); // x的左子树或为空，或已遍历（等效于空），故可以立即访问之
        visit (x->data);
        x = x->rchild; //再转向其右子树（可能为空，留意处理手法）
    }
}

分摊分析： O(n)

虽然和递归都是 O(n)，但是从常系数上来看，递归的常系数更大，因此迭代更好。

后序遍历

将先序遍历的顺序改为V-R-L，倒置后即可。参考Leetcode-145题(参考代码)

层次遍历

自高向低，每一层自左向右访问节点

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T> template <typename VST>
void BinNode<T>::travLevel( VST & visit) // 二叉树层次遍历
{
	Queue<BinNodePosi(T)> Q; // 引入辅助队列
	Q.enqueue(this); // 根节点入队
	while (!Q.empty()) // 在队列再次变空之前，反复迭代
    {
    	BinNodePosi(T) x = Q.dequeue();// 取出队首节点，并随即访问之
    	visit （x->data);
    	if ( HasLChild(*x)) Q.enqueue(x->lChild); //左孩子入队
    	if ( HasRChild(*x)) Q.enqueue(x->rChild); //右孩子入队
    }
}

重构

已知某棵树的遍历序列，还原这棵树的拓扑结构

[先序 | 后续] + 中序

先序遍历确认根节点，在中序遍历中找到根节点，且分开左右子树，将整个二叉树的重构问题转化为左右子树的重构问题。注意左、右子树可能是空树。

[先序 + 后续] X 真二叉树

左右子树要么同时为空，要么非空

先序遍历：根节点+左子树根节点引领的左子树遍历子序列+右子树根节点引领的右子树遍历子序列

后续遍历：以左子树根节点结尾的左子树遍历子序列+右子树根节点结尾的右子树遍历子序列+根节点

可以明确界定左右子树的范围




FEATURED TAGS
C++ 数据结构
FRIENDS