二叉树的遍历和线索二叉树

二叉树的遍历

二叉树的遍历是指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。由于二叉树是一种非线性结构，每个结点都可能有两棵子树，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，进而便于遍历。

由二叉树的递归定义可知，遍历一棵二叉树便要决定对根结点 N、左子树 L 和右子树 R 的访问顺序。按照先遍历左子树再遍历右子树的原则，常见的遍历次序有先序（NLR）、中序（LNR）和后序（LRN）三种遍历算法，其中“序”指的是根结点在何时被访问。

先序遍历

先序遍历（ PreOrder ）的操作过程如下：

若二叉树为空，则什么也不做；否则，

1. 访问根结点；
2. 先序遍历左子树；
3. 先序遍历右子树。

对应的递归算法如下:

void PreOrder(BiTree T) {
    if (T != nullptr) {
        visit(T);             // 访问根节点
        PreOrder(T->lchild);  // 递归遍历左子树
        PreOrder(T->rchild);  // 递归遍历右子树
    }
}

中序遍历

中序遍历（ InOrder ）的操作过程如下：

若二叉树为空，则什么也不做；否则，

• 中序遍历左子树；
• 访问根结点；
• 中序遍历右子树。

对应的递归算法如下：

void InOrder(BiTree T) {
    if (T != nullptr) {
        InOrder(T->lchild);  // 递归遍历左子树
        visit(T);            // 访问根节点
        InOrder(T->rchild);  // 递归遍历右子树
    }
}

后序遍历

后序遍历（ PostOrder ）的操作过程如下：

若二叉树为空，则什么也不做；否则，

1. 后序遍历左子树；
2. 后序遍历右子树；
3. 访问根结点。

对应的递归算法如下：

void PostOrder(BiTree T) {
    if (T != nullptr) {
        PostOrder(T->lchild);  // 递归遍历左子树
        PostOrder(T->rchild);  // 递归遍历右子树
        visit(T);              // 访问根节点
    }
}

三种遍历算法中，递归遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，故时间复杂度都是 #card=math&code=O%28n%29&id=wcD77) 。在递归遍历中，递归工作栈的栈深恰好为树的深度，所以在最坏情况下，二叉树是有 个结点且深度为 的单支树，遍历算法的空间复杂度为 #card=math&code=O%28n%29&id=RkdYp)。

TODO 递归算法和非递归算法的转换

层次遍历

要进行层次遍历，需要借助一个队列。先将二叉树根结点入队，然后出队，访问出队结点，若它有左子树，则将左子树根结点入队；若它有右子树，则将右子树根结点入队。然后出队，访问出队结点….如此反复，直至队列为空。

二叉树的层次遍历算法如下：

void LevelOrder(BiTree T) {
    LinkQueue Q;
    InirQueue(Q);  // 初始化辅助队列
    BiTree p;
    EnQueue(Q, T);  // 将根结点入队
    while (!isEmpty(Q)) {
        DeQueue(Q, p);  // 对头结点出队
        visit(p);       // 访问出队结点
        if (p->lchild != nullptr) {
            EnQueue(Q, p->lchild);  // 左孩子入队,入队指针
        }
        if (p->rchild != nullptr) {
            EnQueue(Q, p->rchild);  // 右孩子入队
        }
    }
}

由遍历序列构造二又树

若只给出一棵二叉树的前/中/后/层序遍历序列中的一种，不能唯一确定一棵二叉树。必须有中序遍历和其他任意一种遍历序列才能确定唯一一种二叉树。

先序序列和中序序列：在先序遍历序列中，第一个结点一定是二叉树的根结点；而在中序遍历中，根结点必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列。根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。如此递归地进行下去，便能唯一地确定这棵二叉树。

类似，由二叉树的后序序列和中序序列，层序序列和中序序列也可以唯一地确定一棵二叉树。找到树的根节点，并根据
中序序列划分左右子树，再找至左右子树根节点。

线索二叉树

线索二叉树的基本概念

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点（第一个和最后一个结点除外）都有一个直接前驱和直接后继。

传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。前面提到，在含 个结点的二叉树中，有 个空指针。这是因为每个叶结点有 2 个空指针，每个度为 1 的结点有 1 个空指针，空指针总数为 ，又 ，所以空指针总数为 。由此设想能否利用这些空指针来存放指向其前驱或后继的指针？这样就可以像遍历单链表那样方便地遍历二叉树。引入线索二叉树正是为了加快查找结点前驱和后继的速度。

规定：若无左子树，令 lchild 指向其前驱结点；若无右子树，令 rchild 指向其后继结点。还需增加两个标志域（ltag、rtag）标识指针域是指向左（右）孩子还是指向前驱（后继）。当 tag 值等于 0 时，表示指针指向孩子，等于 1 时，表示指针指向线索。

线索二叉树的存储结构描述如下：

typedef struct ThreadNode {
    int data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;  // 左右线索标志，0指向孩子，1指向线索
} ThreadNode, *ThreadTree;

以这种结点结构构成的二叉链表作为二叉树的存储结构，称为线索链表，其中指向结点前驱和后继的指针称为线索。加上线索的二叉树称为线索二叉树。

中序线索二叉树的构造

// 全局遍历 pre 指向当前访问结点的前驱
ThreadNode *pre = nullptr;

// 中序遍历二叉树并进行线索化
void InThread(ThreadTree T) {
    if (T != nullptr) {
        InThread(T->lchild);  // 中序遍历左子树
        visit(T);             // 访问根节点并线索化
        InThread(T->rchild);  // 中序遍历右子树
    }
}

void visit(ThreadNode *q) {
    if (q->lchild == nullptr) {  // 左子树为空，建立前驱线索
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != nullptr && pre->rchild == nullptr) {
        pre->rchild = q;  // 建立前驱结点的后继线索
        pre->rtag = 1;
    }
    pre = q;  // 将 pre 指针指向当前结点（即下一个访问结点的前驱结点）
}

// 中序线索化二叉树
void CreateInThread(ThreadTree T) {
    pre = nullptr;
    if (T != nullptr) {
        InThread(T);  // 中序线索化除最后一个结点的其他结点
        if (pre->rchild == nullptr) {
            pre->rtag = 1;  // 注意：处理最后一个结点
        }
    }
}

先序线索二叉树的构造

当 ltag == 0 时，才能对左子树先序线索化

// 全局遍历 pre 指向当前访问结点的前驱
ThreadNode *pre = nullptr;

// 先序遍历二叉树并进行线索化
void PreThread(ThreadTree T) {
    if (T != nullptr) {
        visit(T);                  // 访问根节点并线索化
        if (T->ltag == 0) {        // 注意：需要判断lchild不是前驱线索
            PreThread(T->lchild);  // 先序遍历左子树
        }
        PreThread(T->rchild);  // 先序遍历右子树
    }
}

void visit(ThreadNode *q) {
    if (q->lchild == nullptr) {  // 左子树为空，建立前驱线索
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != nullptr && pre->rchild == nullptr) {
        pre->rchild = q;  // 建立前驱结点的后继线索
        pre->rtag = 1;
    }
    pre = q;  // 将 pre 指针指向当前结点（即下一个访问结点的前驱结点）
}

// 先序线索化二叉树
void CreateInThread(ThreadTree T) {
    pre = nullptr;
    if (T != nullptr) {
        PreThread(T);  // 先序线索化除最后一个结点的其他结点
        if (pre->rchild == nullptr) {
            pre->rtag = 1;  // 处理最后一个结点
        }
    }
}

后序线索二叉树的构造

// 全局遍历 pre 指向当前访问结点的前驱
ThreadNode *pre = nullptr;

// 后序遍历二叉树并进行线索化
void PostThread(ThreadTree T) {
    if (T != nullptr) {
        PostThread(T->lchild);  // 后序遍历左子树
        PostThread(T->rchild);  // 后序遍历右子树
        visit(T);               // 访问根节点并线索化
    }
}

void visit(ThreadNode *q) {
    if (q->lchild == nullptr) {  // 左子树为空，建立前驱线索
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != nullptr && pre->rchild == nullptr) {
        pre->rchild = q;  // 建立前驱结点的后继线索
        pre->rtag = 1;
    }
    pre = q;  // 将 pre 指针指向当前结点（即下一个访问结点的前驱结点）
}

// 后序线索化二叉树
void CreateInThread(ThreadTree T) {
    pre = nullptr;
    if (T != nullptr) {
        PostThread(T);  // 后序线索化除最后一个结点的其他结点
        if (pre->rchild == nullptr) {
            pre->rtag = 1;  // 注意：处理最后一个结点
        }
    }
}

线索二叉树的遍历

在中序线索二叉树中找到指定结点 *p 的中序后继 next：

1. 若 p->rtag == 1，则 next = p->rchild
2. 若 p->rtag == 0，则 next 等于 p 的右子树中最左下的结点 ```c // 找到以 p 为根的子树中，第一个被中序遍历的结点 ThreadNode FirstNode(ThreadNode p){ // 循环找到最左下结点（不一定是叶结点） while(p->ltag == 0){

   p = p->lchild;
   

   } return p; }

// 在中序线索二叉树中找到结点 p 的后继结点 ThreadNode NextNode(ThreadNode p){ // 右子树中最左下结点 if(p->rtag == 0){ return FirstNode(p->rchild); }else { // rtag==1 直接返回后继线索 return p->rchild; } }

// 对中序线索二叉树进行中序遍历 // 利用线索实现的非递归算法 空间复杂度 O(1) void InOrder(ThreadNode T){ for(ThreadNode p = FirstNode(T);p != nullptr;p = NextNode(p)){ visit(p); } }

在中序线索二叉树中找到指定结点 `*p` 的中序前驱 `pre`：

1. 若 `p->ltag == 1`，则  `pre = p->lchild`
1. 若  `p->ltag == 0`，则  `pre` 等于 `p` 的左子树中最右下的结点
```c
// 找到以 p 为根的子树中，最后一个被中序遍历的结点
ThreadNode *LastNode(ThreadNode *p){
    // 循环找到最右下结点(不一定是叶结点)
    while(p->rtag == 0){
        p = p->rchild;
    }
    return p;
}

// 在中序线索二叉树中找到结点 p 的前驱结点
ThreadNode *PreNode(ThreadNode *p){
    // 左子树中最右下结点
    if(p->ltag == 0){
        return LastNode(p->lchild);
    }else { // ltag==1 直接返回前驱线索
        return p->lchild; 
    }
}

// 对中序线索二叉树进行逆向中序遍历
void RevInOrder(ThreadNode *T){
    for(ThreadNode *p = LastNode(T);p != nullptr;p = PreNode(p)){
        visit(p);
    }
}

先序线索二叉树找指定结点 *p 的先序后继 next

1. 若 p->rtag == 1，则 next = p->rchild；
2. 若 p->rtag == 0，则 p 必有右孩子，分成两种情况考虑：
   • 若 p 有左孩子则先序后继为左孩子；
   • 若没有左孩子则先序后继为右孩子

TODO 代码实现先序线索二叉树的后继遍历

在先序线索二叉树中找到指定结点 *p 的先序前驱 pre

1. 若 p->ltag == 1，则 next = p-> lchild；
2. 若 p->ltag == 0，则 p 必有左孩子。二叉链表在先序遍历中，左右子树中的结点只可能是根的后继，不可能是前驱，故找不到先序前驱。三叉链表在先序遍历中，如果能找到 p 的父节点：
   • p 为左孩子，p 的父节点即为其前驱结点；
   • p 是右孩子，其左兄弟为空，p 的父节点即为其前驱结点；
   • p 是右孩子，其左兄弟非空，p 的前驱为左兄弟子树中最后一个被先序遍历的结点；
   • 如果 p 是根结点，则 p 没有先序前驱。

在后序线索二叉树找到指定结点 *p 的后序前驱 pre：

1. 若 p->ltag == 1，则 pre = p->lchild
2. 若 p->ltag == 0，则 p 必有左孩子，若 p 有右孩子，则后序前驱为右孩子；若 p 没有右孩子，则后序前驱为左孩子

TODO 后序前驱遍历代码实现

在后序线索二叉树中找到指定结点 *p 的后序后继 next：

1. 若 p->rtag == 1，则 next = p->rchild
2. 若 p->rtag == 0，则 p 必有右孩子。二叉链表在后序遍历中，左右子树中的结点只可能是根的前驱，不可能是后继。三叉链表在后序遍历中，如果能找到 p 的父节点：
   • p 是右孩子，p 的父节点即为其后继结点；
   • p 是左孩子，其右兄弟为空，p 的父节点即为其后继结点；
   • p 是左孩子，其右兄弟非空，p 的后继为右兄弟子树中第一个被后序遍历的结点；
   • 如果 p 是根节点，则 p 没有后继结点