B站-7.非线性结构之树

树介绍

```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
/*
非线性结构之树
定义：
    专业定义：
        1.有且只有一个称为根的节点
        2.有若干个互不相交的子树，这些子树本身也是一个树
    通俗定义：
        1.树是由节点和边组成
        2.每一个节点只有一个父节点，可以有多个子节点
        3.有一个节点例外，没有父节点，此节点为根节点
    专业术语：
        节点、父节点、子节点、子孙、堂兄弟、兄弟、深度(树的层数)
        叶子节点(没有子节点的节点)、非终端节点(非叶子节点)
        度(子节点的个数)、
分类：
    一般树：
        任意一个节点的子节点的个数不受限制

    二叉树：
        任意一个节点的子节点的个数最多两个，且子节点的位置不可更改

        分类：
            一般二叉树
            满二叉树：
                在不增加树的层数的前提下，无法再多添加
                一个节点的二叉树。
            完全二叉树：
                如果只是删除了满二叉树最底层最右边的连续若干个节点，
                这样形成的二叉树就是满二叉树。

    森林：
        n个互不相交的树的集合

树的存储：
    二叉树的存储
        连续存储[以完全二叉树的形式去存，保存树的结构，优点：1.由编号知层数 2.由编号知父节点与子节点]
            优点：
                查找某个节点的父节点和子节点速度很快
                （也包括判断有没有父节点与子节点）
            缺点：
                耗用内存空间大
        链式存储

    一般树的存储（非线型用线型去存储）
        双亲表示法：求父节点方便
        孩子表示法：求子节点方便
        双亲孩子表示法：求父节点与子节点都方便
        二叉树表示法：
            把一个普通树转化成二叉树来存储
            具体转化方法：
                设法保证任意一个节点的
                    左指针域指向它的第一个孩子（最左边），
                    右指针域指向它的兄弟，
                只要能满足此条件，就可以转化为二叉树。
                并且转化成的二叉树一定没有右子树
    森林的存储
        先把森林转化为二叉树，再存储二叉树

二叉树的操作：
    1.遍历
        先序遍历：
            先访问根节点
            再先序访问左子树
            再先序访问右子树

        中序遍历
            中序遍历左子树
            在访问根节点
            再中序遍历右子树

        后序遍历
            中序遍历左子树
            中序遍历右子树
            再在访问根节点

    2.已知两种遍历序列(先、中)(中、后)求原始二叉树
        通过先序和中序 或者 中序和后序 我们可以还原出原始二叉树
        但是通过后序与先序我们是无法推出的

        ①已知先序和中序求原始二叉树并进而求后序
          先序：ABCDEFGH
          中序：BDCEAFHG
          求后序：EDCBHGFA
        ①已知后序和中序求原始二叉树并进而求先序
          中序：BDCEAFHG
          后序：DECBHGFA
          求先序：ABCDEFGH
树的应用：
    树是数据库中数据组织的一种重要的形式
    操作系统父子进程的关系本身就是一棵树
    面向对象语言中类的继承关系 本身也是一棵树
    赫夫曼树

*/
/*
链式二叉树的实现
*/
# include <stdio.h>
# include <malloc.h>

struct BTNode
{
    char data;
    struct BTNode * pLchild; //p是指针 L是左  child是孩子
    struct BTNode * pRchild;
};

void PostTraverseBTree(struct BTNode * pT);
struct BTNode * CreateBTree(void);
void PreTraverseBTree(struct BTNode * pT);
void InTraverseBTree(struct BTNode * pT);

int main(void)
{
    struct BTNode * pT = CreateBTree();

//  PreTraverseBTree(pT);
//  InTraverseBTree(pT);
    PostTraverseBTree(pT);

    return 0;
}

void PostTraverseBTree(struct BTNode * pT)
{
    if (NULL != pT)
    {
        if (NULL != pT->pLchild)
        {
            PostTraverseBTree(pT->pLchild);
        }
        if (NULL != pT->pRchild)
        {
                PostTraverseBTree(pT->pRchild);
            //pT->pLchild可以代表整个左子树
        }
        printf("%c\n", pT->data);
    }
}

void InTraverseBTree(struct BTNode * pT)
{
    if (NULL != pT)
    {
        if (NULL != pT->pLchild)
        {
            InTraverseBTree(pT->pLchild);
        }

        printf("%c\n", pT->data);

        if (NULL != pT->pRchild)
        {
                InTraverseBTree(pT->pRchild);
            //pT->pLchild可以代表整个左子树
        }
    }
}

void PreTraverseBTree(struct BTNode * pT)
{
    if (NULL != pT)
    {
        printf("%c\n", pT->data);

        if (NULL != pT->pLchild)
        {
            PreTraverseBTree(pT->pLchild);
        }

        if (NULL != pT->pRchild)
        {
                PreTraverseBTree(pT->pRchild);
            //pT->pLchild可以代表整个左子树
        }
    }

/*
    伪算法
    先访问根节点
    再先序访问左子树
    再先序访问右子树
*/
}

struct BTNode * CreateBTree(void)
{
    struct BTNode * pA = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode * pB = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode * pC = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode * pD = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode * pE = (struct BTNode *)malloc(sizeof(struct BTNode));

    pA->data = 'A';
    pB->data = 'B';
    pC->data = 'C';
    pD->data = 'D';
    pE->data = 'E';

    pA->pLchild = pB;
    pA->pRchild = pC;
    pB->pLchild = pB->pRchild = NULL;
    pC->pLchild = pD;
    pC->pRchild = NULL;
    pD->pLchild = NULL;
    pD->pRchild = pE;
    pE->pLchild = pE->pRchild = NULL;

    return pA;
}

```

二叉树的建立

```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;
int main()
{

}
/*
按前序输入二叉树中结点的值(一个字符)
#表示空树，构造二叉链表表示二叉树T。
*/
void CreateBiTree(BiTree *T)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#'){
        *T=NULL;
    }else{
        *T = (BiTree)malloc(sizeof(BiTNode));
        if(!*T){
            exit(-1);
        }
        (*T)->data=ch;//生成根结点
        CreateBiTree(&(*T)->lchild);//构造左子树
        CreateBiTree(&(*T)->rchild);//构造右子树
    }

}
```

线索二叉树

```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
/*
线索二叉树结构实现
遍历时发现相当于操作一个双向链表
*/
typedef enum(Link,Thread) PointerTag;
/*
Link==0   表示指向左右孩子指针
Thread==1 表示指向前驱或后继的线索
*/
typedef struct BiThrNode
{
    char data;
    struct BiTNode *lchild, *rchild;
    PointerTag LTag;
    PointerTag RTag;//左右标志
}BiThrNode,*BiThrTree;

int main()
{

}
BiThrTree pre;//全局变量，始终指向刚刚访问过的结点
//中序遍历进行中序线索化
void InThreading(BiThrTree p)
{
    if(p){
        InThreading(p->lchild);//递归左子树线索化

        //*****************************************
        /*
            与中序遍历二叉树代码几乎一样，就是将打印部分换成了
            线索化的功能

        */
        //前驱线索化简单,某结点的左指针域为空，因为前驱结点刚刚访问过
        //赋值给了pre，可以将p->lchild = pre，并修改p->LTag = Thread
        if(!p->lchild){ //没有左孩子
            p->LTag = Thread;//前驱线索化
            p->lchild = pre;//左孩子指针指向前驱
        }
        //后继就要麻烦一点，因为后继结点还没有访问过
        //所以只能对某节点p的前驱结点pre的右指针做判断
        //1.右指针为空，则pre就是p的后继结点
        if(!pre->rchild){//前驱没有右孩子
            pre->RTag = Thread;//后继线索
            pre->rchild=p;//前驱右孩子指针指向后继(当前结点p)
        }
        pre = p;//保持pre指向p的前驱
        //*************************************

        InThreading(p->rchild);//递归右子树线索化
    }
}

/*T指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍历的
最后一个结点。中序遍历二叉线索链表表示的二叉树T*/
Status InOrderTraverse_Thr(BiThrTree T)
{
    BiThrTree p;
    p = T->lchild;//P左指针指向根结点
    while(p!=T){//空树或遍历结束时，p==T
        while(p->LTag == Link){//当p->LTag==1时循环到中序序列第一个结点
            p = p->lchild;
        }
        printf("%c",p->data);//显示结点数据，可以更改为其他对结点操作
        while(p->RTag==Thread&&p->rchild!=T){
            p = p->rchild;
            printf("%c",p->data);
        }
        p = p->rchild;//p进至其右子树根
    }
    return OK;
}
```