澳门威利斯人_威利斯人娱乐「手机版」

来自 网络资讯 2019-11-09 21:04 的文章
当前位置: 澳门威利斯人 > 网络资讯 > 正文

二叉树链式

数据结构:二叉树的链式存款和储蓄,二叉树链式

数据结构:二叉树的链式存款和储蓄(C语言版卡塔尔国


 1.写在前方

  二叉树相似有二种存款和储蓄格局,数组和链式存款和储蓄,对于数组来讲,我们采取二叉树的本性然后利用下标能够实惠的找到二个节点的子节点和父节点。

  图片 1  

  图片 2

二叉树的性质:
      1.二叉树的第i层上至多有2i-1个节点
      2.深度为K的二叉树至多有2k-1个节点
      3.任何一个二叉树中度数为2的节点的个数必度数为0的节点数目少1.
            说明:度数为0,为叶子节点。
      4.具有n个节点的完全二叉树的深度为|_Log2N_| 1
      5.若完全二叉树中的某节点编号为i,则若有左孩子编号为2i,若有右孩子编号为2i 1,母亲节点为i/2。

  结合第5条性质,能够在这里种完全二叉树中国和亚洲常便利的找到别的相关联(父亲和儿子、兄弟等)的成分。

  不过出于顺序存款和储蓄天生适配于完全二叉树,对于上边这种非完全二叉树并不合适,所以我们须求用到另意气风发种存款和储蓄格局——链式存款和储蓄。

   

  

 

 

 

 

 

  在链式存款和储蓄中,各个节点的构造如下

  

 

  贰个积存数据的变量与多个针对孩子的指针域。
  利用指针域大家便能够周详的仓库储存非完全二叉树,如下:

 

 

 

 

 

 

 

 

 

 

2.代码分解

►首先依据上述图示,大家轻易给出节点的叙说

typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

►创立和遍历链式二叉树
    创制二叉树并非那一个便于的,因为它的开创格局也呼应两种顺序,其实笔者认为二叉树的遍历和二叉树的创设能够说是差少之甚少相通的进度。无非是开创的进程是给data赋值,遍历是抽出data。
  大家先不付出创设的代码,而是要知道:

说明:
  1.叶子节点不是没有左右孩子,只不过左右孩子都是空。
      2.我们在手动创建的过程中要根据层数来判断叶子节点左右空孩子的个数!
      3.创建和遍历的执行顺序是一样的,那么输入和取出的值才会是一样的。

  比方大家要先序创立三个上述图片中的二叉树,大家理应什么输入呢?
    AB##CD##EF##G##

 # 在这里是表示叶子节点的左右节点为空。

  代码如下:

void createBitree(Bitree &T)
{
    char ch;
    if((ch=getchar())=='#')
        T=NULL;
    else
    {
        T=(Bitnode*)malloc(sizeof(Bitnode));
        T->data=ch;
        createBitree(T->Lchild);
        createBitree(T->Rchild);
    }
}                

►遍历代码和创建代码基本相似:

/*先序遍历*/
void preTraverse(Bitree T)
{
    if(T!=NULL)
    {
        printf("%c",T->data);
        preTraverse(T->Lchild);
        preTraverse(T->Rchild);
       }
}

/*中序遍历*/
void  inorder(Bitree T)
{
    if(T!=NULL)
    { 
        inorder(T->Lchild); 
        printf("%c",T->data);
        inorder(T->Rchild);
    } 
}    

/*后序遍历*/
void  postorder(Bitree T)
{

if(T!=NULL)
{
postorder(T->lchild);
postorder(T->rchild);
printf("%c",T->data);
      }
}

►大家输入字符后二种遍历情形如下:
  AB##CD##EF##G##
    ABCDEFG
    BADCFEG
    BDFGECA
►求二叉树的深度

int   Depth(Bitree T)
{//返回深度
    int d,dl,dr;
    if(!T)
        d=0;
    else {
        dl=Depth(T->Lchild);
        dr=Depth(T->Rchild);
        d=1 (dl>dr?dl:dr) ;
    }

    return d;
}

 ►二叉树的层序遍历

    queue<Bitree> TreeQueue; //使用队列
    TreeQueue.push(tree);   //先将队头元素加入队列
    Bitree p = tree;    
    while (!TreeQueue.empty())  //循环判断队列是否未空,若不空则
    {
        p = TreeQueue.front();  //获取队列头节点,并出队列
        TreeQueue.pop();        
        printf(" %c ", p->data); //打印队列元素

        if (p->Lchild)     //如果该节点有左节点
        {
            TreeQueue.push(p->Lchild);  //加入队列
        } 
        if (p->Rchild)    //如果该节点有右节点
        {
            TreeQueue.push(p->Rchild); //加入队列
        }
    }

  |说明:

    1.算法轨道:

      依旧利用下图:

    

 

 

 

 

 

 

 

  演示:
      我们首先将A加入队列, 此时对列 中只有    ⇐[A]
      我们将A出弹出队列,并将它的左右子树 BC加入队列,此时队列中有 ⇐[BC] ,打印出 A
      我们将B出弹出队列,它没有子树,我们不做任何操作,此时队列中有 ⇐[C] ,打印出 ABC
      我们将C出弹出队列,并将它的左右子树 DE加入队列,此时队列中有 ⇐[DE] ,打印出 ABC
      我们将D出弹出队列,它没有子树,我们不做任何操作,此时队列中有 ⇐[E] ,打印出 ABCD
      我们将E出弹出队列,并将它的左右子树 FG加入队列,此时队列中有 ⇐[FG] ,打印出 ABCDE
      我们将F出弹出队列,它没有子树,我们不做任何操作,此时队列中有 ⇐[G] ,打印出 ABCDEF
      我们将G出弹出队列,它没有子树,我们不做任何操作,此时队列中有 ⇐[null] ,打印出 ABCDEFG
  结论:
      根据轨迹我们不难发现,队列是保证层序遍历的基础,因为它保证了先加入队列的上层元素会必后加入队列的下层元素优先出队列。

    2.这段代码直接利用会现出问题,因为大家利用了C 规范模板库中的queue。所以,我们需求投入头文件

      #include<queue>,何况要利用命名空间 using namespace std;。

    3.我们比较数据结构最重大的是掌握和采取,实现它只是支持大家驾驭,大家绝不重复造轮子,在之后的算法中,我们将尽心的援用规范模板库。

 

数据结构:二叉树的链式存款和储蓄(C语言版卡塔尔国 1.写在头里 二叉树相符有二种存款和储蓄方式,数组和链式...

本文由澳门威利斯人发布于网络资讯,转载请注明出处:二叉树链式

关键词: 澳门威利斯人