数据结构 408-5-3

# 二叉树的遍历

遍历：按照某种次序把所有结点都访问一遍

层次遍历：基于树的层次特性确定的次序规则

二叉树的递归特性：

• 要么是个空二叉树
• 要么就是由 "根节点 + 左子树 + 右子树" 组成的二叉树

# 先序遍历

先序遍历：根左右

先序遍历 -> 前缀表达式

先序遍历 —— 第一次路过时访问的节点

先序遍历操作过程如下：

• 若二叉树为空，则什么也不做
• 若二叉树非空
  • 访问根节点
  • 先序遍历左子树
  • 先序遍历右子树

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//先序遍历
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T); //访问根节点
        PreOrder(T->lchild); //递归访问左子树
        PreOrder(T->rchild); //递归访问右子树
    }
}

# 中序遍历

中序遍历：左根右

中序遍历 -> 中缀表达式 (需要加界限符)

中序遍历 —— 第二次路过时访问的节点

中序遍历操作过程如下：

• 若二叉树为空，则什么也不做
• 若二叉树非空
  • 中序遍历左子树
  • 访问根节点
  • 中序遍历右子树

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//中序遍历
void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild); //递归访问左子树
        visit(T); //访问根节点
        InOrder(T->rchild); //递归访问右子树
    }
}

# 后续遍历

后续遍历：左右根

后序遍历 -> 后缀表达式

后序遍历 —— 第三次路过时访问的节点

后序遍历操作过程如下：

• 若二叉树为空，则什么也不做
• 若二叉树非空
  • 后序遍历左子树
  • 后序遍历右子树
  • 访问根节点

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//后序遍历
void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild); //递归访问左子树
        PostOrder(T->rchild); //递归访问右子树
        visit(T); //访问根节点
    }
}

# 二叉树的层次遍历

算法思想：

• 初始化一个辅助队列
• 根节点入队
• 若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾 (如果有的话)

void LevelOrder(BiTree T){
    LinkQueue Q; //初始化辅助队列
    InitQueue(Q);
    BiTree p;
    EnQueue(Q,T); //根节点入队
    while(!IsEmpty(Q)){ //队不空则循环
        DeQueue(Q,p); //队头节点出队
        visit(p); //访问出队节点
        if(p->lchild!=NULL)
            EnQueue(Q,p->lchild); //左孩子入队
        if(p->rchild!=NULL)
            EnQueue(Q,p->rchild); //右孩子入队
    }
}

# 由遍历序列构造二叉树

# 不同二叉树的中序遍历序列

结论：若只给出一颗二叉树的前 / 中 / 后 / 层序遍历序列中的一种，不能唯一确定一颗二叉树

中序遍历序列：左子树的中序遍历序列 + 根节点 + 右子树的前序遍历序列

# 前序 + 中序遍历序列

前序遍历序列：根节点 + 左子树的前序遍历序列 + 右子树的前序遍历序列

# 后续 + 中序遍历序列

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

# 层序 + 中序遍历序列

层序遍历序列：根节点 + 左子树的根 + 右子树的根

Key：找到树的根节点，并根据中序序列分为左右子树，再找到左右子树的根节点

结论：前序、后续、层序序列的两两组合无法唯一确定一颗二叉树

# 线索二叉树

# 线索二叉树的作用

思路：

• 从根节点出发，重新进行一次中序遍历，指针 q 记录当前访问的结点，指针 pre 记录上一个被访问的节点

  • 如何找到指定节点 p 在中序遍历序列中的前驱

    • 当 p==q 时，pre 为前驱

  • 如何找到 p 的中序后继

    • 当 pre==p 时，q 为后继

  • 缺点：找前驱、后继不是很方便：遍历操作必须从根开始

中序线索二叉树：

n 个结点的二叉树来说，有 n+1 个空链域，可用来记录前驱、后继的信息

指向前驱、后继的指针称为 "线索"

# 线索二叉树的存储结构

//二叉树的结点(链式存储)
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//线索二叉树结点
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag; //左、右线索标志
	//tag==0,表示指针指向孩子
    //tag==1,表示指针是线索
}ThreadNode,*ThreadTree;

# 三种线索二叉树

先序线索二叉树：按照先序遍历进行线索化

中序线索二叉树：按照中序遍历进行线索化

后序线索二叉树：按照后序遍历进行线索化

先序线索二叉树 —— 线索指向先序前驱、先序后继

中序线索二叉树 —— 线索指向中序前驱、中序后继

后序线索二叉树 —— 线索指向后序前驱、后序后继

# 二叉树的线索化

土办法找中序前驱：

//中序遍历
void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild); //递归遍历左子树
        visit(T);           //访问根节点
        InOrder(T->rchild); //递归遍历右子树
    }
}
//访问节点q
void visit(BiTNode *q){
    if(q==p)               //当前访问节点刚好是p
        final=pre;         //找到p的前驱
    else
        pre=q;             //pre指向当前访问节点
}
//辅助全局变量，用于查找结点p的前驱
BiTNode *p;                //p指向目标节点
BiTNode *pre=NULL;         //指向当前访问节点的前驱
BiTNode *final=NULL;       //用于记录最终结果

中序线索化：

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre=NULL;

//中序线索化二叉树
void CreateInThread(ThreadTree T){
    pre=NULL;             //pre初始化为NULL
    if(T!=NULL){          //非空二叉树才能线索化
        InThread(T);      //中序线索化二叉树
        if(pre->rchild==NULL)
            pre->rtag=1;  //处理遍历的最后一个节点
    }
}
//线索二叉树结点
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag; //左、右线索标志
	//tag==0,表示指针指向孩子
    //tag==1,表示指针是线索
}ThreadNode,*ThreadTree;
void InThread(ThreadTree T){
    if(T!=NULL){
        InThread(T->lchild); //中序遍历左子树
        visit(T);            //访问根节点
        InThread(T->rchild); //中序遍历右子树
    }
}
void visit(ThreadNode *q){
    if(q->lchild==NULL){     //左子树为空
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL && pre->rchild==NULL){
        pre->rchild=q;       //建立前驱节点的后继线索
        pre->rtag=1;
    }
    pre=q;
}

最后要检查 pre 的 rchild 是否为 NULL，如果是，则令 rtag=1

先序线索化：

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre=NULL;

void CreatePreThread(ThreadTree T){
    pre=NULL;             //pre初始化为NULL
    if(T!=NULL){          //非空二叉树才能线索化
        PreThread(T);      //先序线索化二叉树
        if(pre->rchild==NULL)
            pre->rtag=1;  //处理遍历的最后一个节点
    }
}

void PreThread(ThreadTree T){
    if(T!=NULL){
        visit(T);      //先处理根节点
        if(T->ltag==0)
            PreThread(T->lchild);
        PreThread(T->rchild);
    }
}
void visit(ThreadNode *q){
    if(q->lchild==NULL){ //左子树为空，建立前驱线索
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL && pre->rchild==NULL){
        pre->rchild=q;       //建立前驱节点的后继线索
        pre->rtag=1;
    }
    pre=q;
}

后续线索化：

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre=NULL;

void CreatePostThread(ThreadTree T){
    pre=NULL;             //pre初始化为NULL
    if(T!=NULL){          //非空二叉树才能线索化
        PreThread(T);      //中序线索化二叉树
        if(pre->rchild==NULL)
            pre->rtag=1;  //处理遍历的最后一个节点
    }
}

void PostThread(ThreadTree T){
    if(T!=NULL){
        PostThread(T->lchild);
        PostThread(T->rchild);
        visit(T);
    }
}
void visit(ThreadNode *q){
    if(q->lchild==NULL){ //左子树为空，建立前驱线索
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL && pre->rchild==NULL){
        pre->rchild=q;       //建立前驱节点的后继线索
        pre->rtag=1;
    }
    pre=q;
}

# 在线索二叉树中找前驱后继

中序二叉树找中序后继：

寻找指定节点 * p 的后继

• 若 p->rtag==1，则 next=p->rchild

• 若 p->rtag==0，则 next=p 的右子树最左下节点

寻找指定节点 * p 的前驱

• 若 p->ltag==1，则 pre=p->lchild
• 若 p->ltag==0，则 pre=p 的左子树最右下节点

//找到以p为根的子树中，第一个被中序遍历的节点
ThreadNode *FirstNode(ThreadNode *p){
    //循环找最左下节点(不一定是叶节点)
    while(p->ltag==0)
        p=p->lchild;
    return p;
}
//找到以p为根的子树中，最后一个中序遍历的节点
ThreadNode *LastNode(ThreadNode *p){
    //循环找最右下节点(不一定是叶节点)
    while(p->rtag==0)
        p=p->rchild;
    return p;
}
//在中序线索二叉树中找到结点p的后继节点
ThreadNode *NextNode(ThreadNode *p){
    //右子树最左下节点
    if(p->rtag==0)
        return FirstNode(p->rchild);
    else //rtag==1
    	return p->rchild;
}
//在中序线索二叉树中找到结点p的前驱节点
ThreadNode *PreNode(ThreadNode *p){
    //右子树最左下节点
    if(p->ltag==0)
        return LastNode(p->lchild);
    else //rtag==1
    	return p->rchild;
}
//对中序线索二叉树进行中序遍历(利用线索实现非递归算法)
void InOrder(ThreadNode *T){
    for(ThreadNode *p=FirstNode(T);p!=NULL;p=NextNode(p))
        visit(p);
}
//对中序线索二叉树进行逆向中序遍历(利用线索实现非递归算法)
void RevOrder(ThreadNode *T){
    for(ThreadNode *p=LastNode(T);p!=NULL;p=PreNode(p))
        visit(p);
}

先序线索二叉树找先序前驱：

寻找指定节点 * p 的前驱

• 若 p->ltag==1，则 next=p->lchild
• 若 p->ltag==0
  • 如果能找到 p 的父节点，且 p 是左孩子，p 的父节点为其前驱
  • 如果能找到 p 的父节点，且 p 是右孩子，其左兄弟为空，p 的父节点为其前驱
  • 如果能找到 p 的父节点，且 p 是右孩子，其左兄弟非空，p 的前驱为左兄弟子树最后一个被先序遍历的节点
  • 如果 p 是根节点，则 p 没有前驱

后续线索二叉树找后续前驱：

寻找指定节点 * p 的前驱

• 若 p->ltag==1，则 pre=p->lchild
• 若 p->ltag==0
  • 如果能找到 p 的父节点，且 p 是右孩子，p 的父节点为其前驱
  • 如果能找到 p 的父节点，且 p 是左孩子，其右兄弟为空，p 的父节点为其前驱
  • 如果能找到 p 的父节点，且 p 是左孩子，其右兄弟非空，p 的前驱为右兄弟子树第一个被后序遍历的节点
  • 如果 p 是根节点，则 p 没有后续后继