数据结构-树(4)

2018年2月2日2018年2月3日

上一章我们讲解了二叉树的创建和遍历，这一章就可以放开手脚大干一场了

线索二叉树

什么是线索二叉树：二叉链表中有2n个指针域，其中n+1个指针域存放的都是NULL，我们要把这些指针域利用起来，存放节点的前驱和后继。

用处：对二叉树遍历的过程实质上是对一个非线性结构进行线性化的操作，以二叉链表为存储结构时,结点的左右孩子可以直接找到,但不能直接找到结点的前驱和后继,而结点的前驱和后继只有在遍历二叉树的过程中才能得到，效率低下。在后面的中序查找和平衡二叉树中会非常有用。

结点结构

我们在原有节点的基础上又添加了LeftThread和RightThread两个标志位，因为我们需要区分每个节点的指针域内的指针究竟是指向它的孩子还是指向它的前驱或者后继。虽然增加了空间，但是减少了时间

LeftThread=0, LeftChild指向左孩子
LeftThread=1, LeftChild指向前驱
RightThread=0, RightChild指向右孩子
RightThread=1, RightChild指向后继

//
typedef enum {Link,Thread} PointerTag;

typedef struct Node
{
    char val;
    struct Node *lChild,*rChild;
    PointerTag lThread = Link,rThread = Link;//c11标准才允许初始化
} BiTreeNode,*BiTree;
//

二叉树线索化

不同的遍历顺序，每个节点的前驱和后继自然也不一样

中序线索化二叉树

后继：结点标志为1时，其右指针为其后继；结点标志为0时，其右子树最左下结点为其后继。
前驱：结点标志为1时，其左指针为其前驱；结点标志为0时，其左子树最右下结点为其前驱。

//
//pre是一个全局变量，时刻指向当前节点的前驱元素
void inThreadBiTree(BiTree T)
{
    if(T == NULL) return;//空树返回


//中序线索化左子树
    if(T->lChild)//可以不加，前面有判空
        inThredBiTree(T->lChild);



//线索化根节点
    if(!T->lChild)//该节点如果左孩子为NULL
    {
        T->lThread = Thread;//更改标志位
        T->lChild = pre;//左指针指向前驱元素
    }
    if(!pre->rChild)//如果前驱元素的右孩子为NULL
    {
        pre->rThread = Thread;//更改标志位
        pre->rChild = T;//右孩子指向后继元素
    }
    pre = T;//该节点成为下一个节点的前驱元素



//中序线索化右子树
    if(T->rChild)
        inThreadBiTree(T->rChild);
}
//

我们根据下图来看一下上面代码的思路，中序线索化和中序遍历思路一样一样的，我们其实只需要修改中序遍历中的visit也就是访问函数即可，具体来看一下

例如访问到D节点时，D节点左孩子为NULL，则左指针指向D的前驱，那我们怎么知道D的前驱是谁呢？因为D的前驱就是在D之前访问的节点，我们只需要用一个全局变量把它记录下来就可以了，这个变量就是pre！pre是D的前驱，D就是pre的后继，所以如果pre的右孩子为NULL，我们要让他指向D

所以每次访问节点时，我们有两个操作对象：（1）pre （2）当前访问的节点。

要进行两次操作：（1）当前节点左指针指向pre （2）pre右指针指向当前结点。

操作结束后我们还要让pre指向当前节点，pre的作用就是记录访问节点的足迹顺序。一个节点的左指针的赋值是在访问该节点时进行，右指针的赋值在它变为pre后进行

pre的初始化怎么办呢？类比链表中的头节点，我们也可以给二叉树添加一个头节点

这棵树的中序遍历为 CBDA

我们规定P为头节点，C节点本来没有前驱，但是现在我们可以让C的左指针指向P

A节点本来没有后继元素，但是我们规定让它的右指针指向P

我们规定P的左指针指向二叉树，右指针指向最后一个节点A

//
void inOrderThreadBiTree(BiTree T,BiTree &P)
{
    P = (BiTree)malloc(sizeof(Node));//创建头节点
    P->rThread = Thread;
    P->rChild = P;//初始化右指针指向自己
    P->lThread=Link;
    if(!T)
        P->lChild = P;//左指针指向自己,空树,类似循环链表头节点
    else
    {
        P->lChild = T;//左指针指向二叉树
        pre = P;//pre指向头节点,完成pre初始化
        inThreadBiTree(T);//中序线索化
        pre->rThread = Thread;//最后一个节点右指针指向头节点
        pre->rChild = P;
        P->rChild = pre;//头节点右指向最后一个节点
    }
}
//

如今我们再看一下头节点的作用，就是让线索化直接进入一个运行过程中，pre有了初始值，从而简化了操作，当不存在头节点时，初始化操作会变得比较麻烦

线索二叉树中序遍历

非递归实现

//
void inThreadBiTreeTraverse(BiTree P)
{
    BiTree t = P->lChild;//进入二叉树
    while(t!=P)
    {
        while(t->lThread == Link)//先访问最左边的元素
            t = t->lChild;
        cout<<t->val;
        while(t->rThread == Thread && t->rChild != P)
        {//是叶子节点，就访问后继
            t = t->rChild;
            cout << t->val;
        }
        t = t->rChild;//非叶子节点进入右子树
    }
}
//

树与森林

树与森林和二叉树的转化

前面讲到的孩子兄弟表示法，左指针指向第一个孩子，右指针指向兄弟。

而森林只需要让二叉树的根节点的右指针指向下一棵二叉树

一般树的遍历

广度优先遍历：就是层序遍历

深度优先遍历：先根次序遍历，后根次序遍历

先根次序遍历

先访问根节点，依次先根遍历根的各棵子树，但是对于一般的树来说，它的子树个数并没有数量上的限制，我们无法简单的用递归来实现，或许你会想到用迭代来实现，但是这里我们可以看看能否在对应二叉树中有所发现

这棵树的先根次序遍历为ABEHIJCDFGK

后根次序遍历为HIJEBCFKGDA

对应二叉树的前序遍历为ABEHIJCDFGK

中序遍历为HIJEBCFKGDA

所以先根次序遍历可以通过对应二叉树的先序遍历实现，后跟次序遍历可以通过对应二叉树的中序遍历实现