数据结构之树

一、定义

  数据结构和树状图差不多,有一个根的节点,有若干个互不相交的子树,这些子树本身也是一棵树

二、专业术语

  节点    父节点    子节点    

 

子孙    堂兄弟(不同父节点的同一辈分的节点)

 

深度:从根节点到最底层节点的层数称之为深度,根节点是第一层

 

叶子节点:没有子节点的节点

 

非终端节点:非叶子节点

度:该子节点的个数,整个树的度为最大度数节点的度数

三、树的分类

  一般树:任意一个节点的子节点的个数都不受限制的树;

  二叉树:只有一个根节点,任意一个节点的子节点个数最多两个,且子节点的位置不能更改,有一般二叉树(各节点未饱和)、满二叉树(饱和)、完全二叉树(如果只是删除了满二叉树最底层最右边的连续若干个节点,这样形成的二叉树就是完全二叉树)的分类。二叉树是重点

  森林: n个互不相交的集合,多个根节点

四、针对不同树有不同存储方式

  一般树

    双亲表示法、孩子表示法、双亲孩子表示法、

    二叉树表示法:把一个普通树转换成二叉树来存储,具体转换方法:设法保证任意一个节点地左指针域指向它地第一个孩子,右指针域指向它的亲兄弟。只要能满足此条件,就可以把一个一般树转换为二叉树。一个普通树转化成的二叉树一定没有右子树

  森林

    同上,转换为二叉树存储。

  二叉树

        连续存储【只有完全二叉树可以连续存储】

      优点:查找某个节点的父节点和子节点(也包括判断有没有子节点)速度很快

               缺点:很耗内存,要有层次地存储

        链式存储

      优点:可以只存放有效节点,相对比较简单,相对耗内存也比较少,且不需要有层次地存储

五、二叉树的遍历  

l  二叉树的操作:一种是遍历,有三个,是将非线性转化为线性存储的方法;另一种是已知遍历序列求原二叉树。

l  二叉树连续存储的先序遍历操作(重点):

先访问根节点,再先序访问左子树,再先序访问右子树。有递归思想

l  二叉树连续存储的中序遍历操作(重点):

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

l  二叉树连续存储的后序遍历操作(重点):

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

l  只有已知两种遍历序列才可以求出原始二叉树

通过先序和中序、或者中序和后序我们可以还原出原始的二叉树,但是通过先序和后序无法还原出原始的二叉树。当然,单靠一个更不可能还原出。

六、链式存储二叉树程序(递归实现)

#include<stdio.h>
#include<malloc.h>

typedef struct BTNode
{
    char data;
    struct BTNode *pLchild;
    struct BTNode *pRchild;
}BTNODE,*PBTNODE;

PBTNODE CreateBTree();
void PreTraverseBTree(PBTNODE);
void InraverseBTree(PBTNODE);
void PostTraverseBtree(PBTNODE);


int main()
{
    PBTNODE pT;
    pT=CreateBTree();
    PreTraverseBTree(pT);//先序遍历
    printf("*********\n");
    InraverseBTree(pT);
    printf("*********\n");
    PostTraverseBtree(pT);

    return 0;
}

void PreTraverseBTree(PBTNODE pT)
{
    /*用递归实现:先访问根节点,再先序访问左子树,再右子树*/
    if(pT!=NULL)
    {
        printf("%c\n",pT->data);
        if(pT->pLchild!=NULL)
            PreTraverseBTree(pT->pLchild);
        if(pT->pRchild!=NULL)
            PreTraverseBTree(pT->pRchild);
    }
    return;
}
    
void InraverseBTree(PBTNODE pT)
{
    if(pT!=NULL)
    {
        if(pT->pLchild!=NULL)
            PreTraverseBTree(pT->pLchild);
        printf("%c\n",pT->data);
        if(pT->pRchild!=NULL)
            PreTraverseBTree(pT->pRchild);
    }
    return;
}

void PostTraverseBtree(PBTNODE pT)
{
    if(pT!=NULL)
    {
        if(pT->pLchild!=NULL)
            PreTraverseBTree(pT->pLchild);
        if(pT->pRchild!=NULL)
            PreTraverseBTree(pT->pRchild);
        printf("%c\n",pT->data);
    }
    return;
}

PBTNODE CreateBTree()//静态创建树
{
    PBTNODE pA=(PBTNODE)malloc(sizeof(BTNODE));
    PBTNODE pB=(PBTNODE)malloc(sizeof(BTNODE));
    PBTNODE pC=(PBTNODE)malloc(sizeof(BTNODE));
    PBTNODE pD=(PBTNODE)malloc(sizeof(BTNODE));
    PBTNODE pE=(PBTNODE)malloc(sizeof(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;
}

 

数据结构之树

上一篇:流程控制优化


下一篇:Win7中如何在服务中启动一个当前用户的进程——函数CreateProcessAsUser()的一次使用记录