右下侧的FAQ➡
会让你快捷使用本站
关闭提示
Arithmetic

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

PineappleCat · 3月10日 · 2020年 315次已读

树介绍

```
#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;
}
```


Click here to view the copyright notice of this site(点击此处查看本站版权声明)


0 条回应