树

Julia999

树：是有n(n>=0)个结点的有限集.当n=0时，称为空树，在任意一颗非空树中：-有且只有一个特定的称为根的结点（根结点一定是唯一的（n>0时））
-当n>1时，其余结点m称为根的子树（m>0时，子树的个数是没有限制的，但他们是互相一定不会相交的）

结点所拥有的子树我们称之为结点的度。树的度取树内各结点的度的最大值。度为0的结点称之为叶结点（或终端结点）
度不为0的结点我们称之为分支结点或非终端结点，除根结点外，分支结点也称为内部结点。（所以说，根结点可以叫做分支结点或非终端结点（非叶子节点），但是内部结点仅仅是相对于不是叶结点和根结点而言的）

通俗的说：1.树由节点和根组成
2.每个结点只有一个父节点，但可以有多个子节点
3.但有一个节点除外，该节点没有父节点，此节点称为根节点



专业术语：
孩子，双亲，兄弟，祖先（很好理解的吧~）

根的层次从根开始定义，根为第一层，根的孩子为第二层
其双亲在同一层的节点称为堂兄弟~~
树的结点的最大层次称为树的深度或高度~~
深度：从根节点到最底层节点的层数称之为深度

                               
登录/注册后可看大图

                               
登录/注册后可看大图

树的分类：
一般树：任意一个节点的子节点的个数不受限制
二叉树：任意一个节点的子节点的个数最多两个，且子节点的位置不可以更改（有序树）
分类：
       一般二叉树
       满二叉树（不能再添了）在不增加层数的前提下，无法在多添加一个节点的二叉树就是满二叉树
       完全二叉树：如果只是删除了满二叉树最底层最右边的连续若干个节点，这样形成的二叉树就是完全二叉树
     （满二叉树是完全二叉树的一个特例）
森林：n个互不相交的树的集合

                               
登录/注册后可看大图

树的存储：
二叉树的存储：
       连续存储【完全二叉树】
             树是非线性的结构，那我们怎用线性的结构来存储呢？）
要存储一个树，必须以完全二叉树的形式来存储（只有通过将一颗普通树转换成完全二叉树，才可以表示他们之间的非线性结构）
（如果我们只存有效节点，那么我们没法根据有效的节点来推断出树的本来面貌，并且1.可以知道这个树有多少层，2.可以获取他的父节点是谁，子节点是谁，所以需要将其转换成完全二叉树）
但是也有缺点：内存消耗

链式存储
      内存消耗较少，但是要查询父节点会比较困难。

一般树的存储（其实还是为了解决非线性的用线性存储的问题）
双亲表示法（孩子记录父亲的下标）求父节点方便


孩子表示法（记录孩子指针）求孩子方便


双亲孩子表示法（存父节点和子节点的指针）求父节点，求子节点都方便


二叉树表示法：把一个普通树转换成二叉树存储
具体转换方法：
设法保证任意一个节点的左指针域指向他的第一个孩子，右指针域指向他的下一个兄弟节点，只要满足此条件，就可以把普通树转换成二叉树
一个普通树转换成的二叉树一定没有右子树


森林的存储
先把森林转换成二叉树之后再存储
方法：与一般树转换成二叉树的形式很像。将其他森林的根节点当成兄弟~


操作：
遍历：
先序遍历（先访问根）
    先访问根节点
    再先序访问左子树
    再先序访问右子树

中序遍历（始终让‘根’在中间访问）（中间访问根）
    中序遍历左子树
    再访问根节点
    再中序访问右子树


后序遍历（最后访问根）
    中序遍历左子树
    中序遍历右子树
    再访问根节点


已知两种遍历序列求二叉树
通过先序和中序或者中序和后序，我们可以推算出原始的二叉树，但是通过先序和后序，无法还原出原始的二叉树的
换种说法：
只有通过先序和中序或中序和后序，才可以唯一确定一个二叉树
（1）已知先序和中序，求后序：
先找到先序出现的第一个，就是根节点，再在中序中找到相应根节点的位置，左边就是根节点的左子树，右边就是根节点的右子树，然后再在先序中找到左子树中最早出现的，就左为左子树的‘父亲’，同理，可以找到右子树的父亲，这样不断循环，就可以找到整个后序遍历
（2）已知中序和后序，求先序：
先找到后序中最后一个作为根节点，然后在中序中找到根节点，根节点的左边作为左子树，右边作为右子树，然后在后序中出现最晚的作为左子树中的‘根’，右边中在后序中出现最晚的作为右子树中的‘根’，然后不断的循环操作找到整个先序


应用：
      树是数据库中数据组织一种重要的形式
      操作系统子父进程的关系本身就是一颗树
      面向对象语言类中的继承关系本身也是一棵树
      赫夫曼树








链式二叉树：

#include<stdio.h>
#include<malloc.h>
struct BTNode
{
    int data;
    struct BTNode *pLchild;  //p是指针，L是左 child是孩子
    struct BTNode *pRchlid;  
};

struct BTNode *CreatBTree()
{
    struct BTNode *pA=(struct BTNode *)malloc(sizeof(structBTNode));
    struct BTNode *pB=(struct BTNode *)malloc(sizeof(structBTNode));
    struct BTNode *pC=(struct BTNode *)malloc(sizeof(structBTNode));
    struct BTNode *pD=(struct BTNode *)malloc(sizeof(structBTNode));
    struct BTNode *pE=(struct BTNode *)malloc(sizeof(structBTNode));
    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->pRchild=pD;
    pD->pLchild=NULL;
    pD->pRchlid=pE;
    pE->pLchild=pE->pRchild=NULL; 

   return pA;
}

void PreTraverseBTree(struct BTNode *pT)
{
    if(NULL!=pT)
    {
         printf("%c\n",pT->data);
         if(NULL!=pT->pLchild)
         {
                PreTraverseBTree(pT->pLchild);
         }
        if(NULL!=pT->pRchlid)
        {
               PreTraverseBTree(pT->pRchild);
        }
         //pT->pLchild可以代表整个左子树
    }
    //先访问根节点
    //再先序访问左子树
    //再先序访问右子树
}

void  InTraverseBTree(struct BTNode *pT)
{
    if(NULL!=pT)
    {
         if(NULL!=pT->pLchild)
         {
                InTraverseBTree(pT->pLchild);
         }
         printf("%c\n",pT->data);
        if(NULL!=pT->pRchlid)
        {
               InTraverseBTree(pT->pRchild);
        }
         //pT->pLchild可以代表整个左子树
    }
    //中序遍历左子树 
    //再访问根节点
    //再中序访问右子树
}


void  PostTraverseBTree(struct BTNode *pT)
{
    if(NULL!=pT)
    {
         if(NULL!=pT->pLchild)
         {
                PostTraverseBTree(pT->pLchild);
         }
       
        if(NULL!=pT->pRchlid)
        {
               PostTraverseBTree(pT->pRchild);
        }
         //pT->pLchild可以代表整个左子树
    }
     printf("%c\n",pT->data);
    //中序遍历左子树 
    //再访问根节点
    //再中序访问右子树
}

int main()
{
    struct BTNode * pT=CreatBTree();  //返回根节点的地址
    PreTraverseBTree(pT);  //先序
    InTraverseBTree(pT);   //中序
    PostTraverseBTree(pT); //后序
    return 0;
}

枫丹白露666

我想问一下，考研中的代码不会写，应该咋练

Julia999

枫丹白露666 发表于 2019-10-6 15:41
我想问一下，考研中的代码不会写，应该咋练

多敲多练，祝考研顺利呀