PHP开发日志

二叉树的创建和遍历

2402 Views 0 Comments

1、查找问题：分静态查找和动态查找


2、同样n个元素的查找，二分查找比顺序查找快很多。

判定树深度：[log2 n]+1，还可计算平均查找次数，11个节点仅为4.

3、树：根与子树，要求子树是不能相交的。

于是树的特点：

  1. 除根节点外，每个节点只有1个父节点。

  2. n个节点，n-1条线。

  3. 树是连通的，且是保证所有节点联通但同时线条树最少的状态。


4、节点的度

树的度 取最大的节点度


5、用什么表示树？

链表 （兄弟-儿子表示法）：

每一个元素1个数据+2个指针（firstChild+nextSibling）

转化为二叉树：度为2的树


一共2n个指针，有效n-1个，闲置n+1个。


6、二叉树：

有左右之分

  1. 斜二叉树

  2. 完美二叉树（满二叉树）k层，最多(2^k-1）个节点

  3. 完全二叉树（若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。）

总节点数=n0+n1+n2

总边数=n0+n1+n2-1=n1+2*n2

求解：n0=n2+1


推广到m叉树

n0+n1+……+nm -1=1*n1+2*n2+……+m*nm；

移项，得：

n0=n2+2*n3……+(m-1)*nm + 1


深度为k，最大节点数2^k-1个，最后一层最大节点数2^(k-1)个。


7、二叉树的存储

1）数组

元素之间的联系通过下标体现。

完全二叉树：很适合用数组（下标1开始），

因为有如下规律：


一般二叉树：差的不多也可以补齐然后用数组。

2）链表

一般二叉树，链表更适合

1个元素包含3个字段，1个是数据，另外2个指针，left和right

typedef struct TreeNode* BinTree;

struct TreeNode{
    ElementType Data;
    BinTree left;
    BinTree right;

}

8、二叉树操作集

  1. createBinTree

  2. isEmpty

  3. traversal

其中traversal又分

  1. preOrder

  2. inOrder

  3. postOrder

  4. levelOrder


9、二叉树前/中/后序遍历基于链表的递归实现。

1)前序遍历 根左右

void preOrderTraversal(BinTree BT){
    if (BT)
      {
       printf("%d",BT -> Data);
       preOrderTraversal(BT->left);
       preOrderTraversal(BT->right);
       }
}

2）中序遍历 左根右

void inOrderTraversal(BinTree BT){
    if (BT)
      {

       preOrderTraversal(BT->left);
       printf("%d",BT -> Data);
       preOrderTraversal(BT->right);
       }

}

3）后序遍历 左右根

void postOrderTraversal(BinTree BT){
    if (BT)
      {

       preOrderTraversal(BT->left);
       printf("%d",BT -> Data);
       preOrderTraversal(BT->right);
       }

}

10、二叉树前/中/后序遍历基于链表的非递 归实现。

递归写起来简单，能不能不用递归，比如：用堆栈实现中序堆栈？


【思路】

中序，左中右，中是中间的一个节点，左右是树。

因此节点作为左节点时并不能马上就访问，因为它也是子树的根。所以作为根要放在堆栈里，等左边访问完。访问左边时，子树左节点同样是子子树的根，同样放堆栈里。

什么时候可以结束呢？

这个节点作为根放入堆栈，一查发现左孩子不存在，就可以弹出来了。弹出来这个是根，这时确定的是左树已经访问完，所以马上访问根，然后下一步访问自己的右树。

为了访问右树，把右树的根压栈……

弹一个是自己，如果再弹一个应该是自己的父亲。但自己访问完应该去访问自己的右树，自己作为根的这棵树结束以后，才把自己看成儿子，去访问那棵树。所有不会马上弹第二个，访问右树的过程也是把这棵树的根节点压尽，到底反弹的过程。等右树访问完，右树所有的节点都已经在堆栈里压进去又出来过，堆栈的现场同访问右树前没有变化，就可以回去弹出根了。


堆栈保存的是子树的根！



【规则】


第一次碰到实际上都是跟左右的顺序。

每轮循环有一个当前节点。

当前节点如果不为NULL，有2种，左孩子为空和不为空。

如果左孩子不为空，就把当前节点换成它的左孩子，同时把自己保持在堆栈里，过一会回来方便找右节点。

左孩子为空，堆栈顶pop一个，刚好是当前节点（第2次碰到），然后当前节点换成它的右节点。

如果右节点为空，所以下一轮当前节点可能是NULL，意味着某几个层次的右子树、同时也作为某一个层次的左子树都处理完了，这时pop出下一个根（左子树的根）。

深入理解二叉树的非递归遍历_C 语言

外层循环的意义在于，弹出一个根节点并在此之前保证它的左子树已经访问完毕。

堆栈也用链表表示，栈顶在链表头，参考：zhuanlan.zhihu.com/p/50

typedef struct SNode* Stack

struct SNode{
    ElementType item;
    struct SNode* left;
    struct SNode* right;
};

创建堆栈：

Stack createStack(){
    Stack s=(Stack)malloc(sizeof(struct SNode));
    s->Next=NULL;
    return s;

}

利用堆栈实现中序遍历

void inOrderTraversal(BinTree BT){
    Stack s =createStack();
    BinTree bt=BT;
    while(bt||!isEmpty(s))
    {
      while(bt){
      push(s, bt);
      bt=bt->left;      
       }
     if(!isEmpty(s)){
      Stack tmp=pop(s)
      if(tmp){
      printf("%d",tmp->Data);
      t=tmp->right;
      }
     }
}

利用堆栈实现先序遍历 根左右

void inOrderTraversal(BinTree BT){
    Stack s =createStack();
    BinTree bt=BT;
    while(bt||!isEmpty(s))
    {
      
      while(bt){
      printf("%d",bt->Data);
      push(s, bt);//push for the right later
      bt=bt->left;      
       }
     if(!isEmpty(s)){
      Stack tmp=pop(s)
      if(tmp){
      
      t=tmp->right;
      }
     }
}

利用堆栈实现后序遍历 左右根（较复杂）

1）法一：

作为根节点入栈时打上is_first标记。在左树结束后本来有一次出栈机会，但看到标记线不出（或者这里的统一出，出了看到标记不对再压回去），同时把下一个要处理的节点置为右儿子。等右子树结束后悔再次有pop的机会，这时才真正的访问。

void inOrderTraversal(BinTree BT){
    Stack s =createStack();
    BinTree bt=BT;
    while(bt||!isEmpty(s))
    {
      while(bt){
      //printf("%d",bt->Data);
       bt->is_first=True;
      push(s, bt);//push for the right later
      bt=bt->left;      
       }
     
     if(!isEmpty(s)){
      Stack tmp=pop(s)
      if(tmp){
       if(!is_first){
       printf("%d",tmp->Data);
       p=NULL;
       }
      else{
       tmp->is_first=false;
       push(s, tmp);
       bt=tmp->right;
      }
     }
}

2）法二：每一轮循环都去栈顶去一个元素看看，对于当前节点，如果有孩子且孩子还没被访问到，就不出栈，反而把右边和左边的孩子先后压栈；否则（），自己轻松出栈。

void PostOrderTraversal(BinTree BT)
{
    Stack S=CreateStack(MaxSize);
    BinTree pre,cur;
    pre=NULL;
    cur=NULL;
    Push(S,BT);
    while(!IsEmpty(S))
    {
        cur=S->Data[Top];
        if((cur->Left==NULL&&cur->Right==NULL)||(pre!=NULL&&(cur->Left==pre||cur->Right==pre)))//没有子节点或者pre是自己的子节点是自己的子节点
        {
            printf("%5d",cur->Data);
            Pop(S);
            pre=cur;
        }
        else
        {
            if(cur->Right!=NULL)
            Push(S,cur->Right);
            if(cur->Left!=NULL)
            Push(S,cur->Left);
        }
    }
    }

3）利用2个堆栈，把根左右转化为右左根

先序的访问顺序是root, left, right 假设将先序左右对调，则顺序变成root, right, left，暂定称之为“反序”。

后序遍历的访问顺序为left, right,root ，刚好是“反序”结果的逆向输出。

如果有了先序的代码+这个思路，改一下代码不难。

void InOrderTraversal( BinTree BT )
{
 BinTree T BT;
 Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/
 Stack Q = CreatStack( MaxSize ); /*创建并初始化堆栈Q，用于输出反向*/
 while( T || !IsEmpty(S) ){
 while(T){ /*一直向右并将沿途结点压入堆栈*/
 Push(S,T);
 Push(Q,T);/*将先序遍历到的结点压栈，用于反向*/
 T = T->Right; /*转向右子树*/
 }
 if(!IsEmpty(S)){
 T = Pop(S); 
 T = T->Left; /*转向左子树*/
 }
 }
  
 while( !IsEmpty(Q) ){
 T = Pop(Q);
 printf(“%5d”, T->Data); 
 }
}

11、二叉树层序遍历基于队列的非递归实现。

二叉树的遍历-》二维转化为一维，这个顺序是自己定夺的。

一个父节点有2个子节点，访问左边以及左边子树以后，怎么再去找右边或者自己？

需要想办法保存自己或者右边。

  1. 前序中序后序-》堆栈-》保存自己

  2. 层序-》队列-》保存右边

以上前中后的左右不是左右节点，而是左右子树-》找到左儿子也不敢当场访问，保存起来先。

层序遍历是一层一层看完，从上往下是顺序的，找到就当场访问，没有保存起来一会儿回来访问的需求。所以没有堆栈。

至于用队列，是因为这一层的所有节点都访问以后他们的子节点才会被访问，加入这一层4个节点，第1、2个节点自己是找到就当场访问，但子女没有，要等第4个访问完，所以就需要保存这些父节点。而子节点访问的顺序与父节点一致，所以用队列，先进先出，刚好。

层序遍历的思路：

  1. 找到父节点就当场访问，然后把父节点的左右孩子放进待访问的队列，等排队到了自然能访问，在此之前前面有和父节点同一层的节点需要访问。

  2. 程序从1个根节点启动。除了第1个是手工指定，以后的父节点其实都是xxx的子节点，找到父节点的时机都是排队到队头。所以主要都是在操作队列。

  3. 根节点为了与程序相适应，也准备从队头访问。为此只需要手工放入队列，然后就可以进入从队列取数-子节点入队的循环。

步骤：

  1. 创建队列，把根节点加入队列

  2. 然后进入循环，在每一轮循环里，从队头取出一个数，访问，然后把左右节点加入队尾，如果左右节点存在的话。

  3. 队列为空则循环结束

void inOrderTraversal(BinTree BT){
    if (!BT->Data)return ;
    Queue q=createQueue();
    add(q,BT->data);

    while(!q.isEmpty()){
    ElementType x=delete(q);
    printf(x->data);
     if(x->left)
    add(q,x->left);
     if(x->right)
    add(q,x->right);
   
}
}

12、层序创建二叉树

和层序遍历有相同但也有所差别。遍历时访问了父亲同时把2儿子入队，因为儿子已经存在；创建是创建父亲同时把父亲入队，到时候如果还有输入就动态创建子节点，没有的话就不创建了。

遍历结束的时机是队列空掉，创建结束的时机是输入结束。


创建二叉树存在同一的问题：如果这一层4个节点，需要填充完这一层4个才去下一层，开始填充第1个元素的左右孩子？

但链表表示，其实对4这个数字并没有记载，并不清楚这一层多少个数。换个思路，其实需要记载的不一定是数字4，而是最终的它们的子节点——所以如果可以在父节点访问时就创建好子节点并保存，到时候去取，就不用关心到底多少个。

这个保存适合队列，保证顺序，不关心数量——队列里是待填的空格，每次上面一行有了一个元素，必然意味着下面需要画左右2个空格。空格产生了先放着，等到上一次都填充完就来填充它。事实上，上一层的空格也是上上一层造成的，这样保证了应有的顺序。且排队的空格都是上一层产生，这保证了队列里不会有其他多余的东西，可以放心用。

其实左右空格是上层父节点产生的，所以……可以直接保存父节点，出队时1个父节点再去创建2个子节点，并同时完成赋值。

除了根节点，其他节点都是子节点其实。可以去区分父节点子节点似乎是徒劳的，一个节点两重身份。入队时是作为别人的子节点，自身的Data已经在父节点出队时填充好，但需要排队完善子节点；出队时作为父节点，完善自己的子节点。

BT createBinTree（）
{int x;
scanf("%d", &x);
if(!x) return NULL;
Queue q=createQueue();

BT bt= (BT)malloc(sizeof(struct TreeNode));
bt->Data=x;
bt->left=bt->right=NULL;
add(q, bt);

while(!isEmpty(q))
{BT bt=delete(q);

scanf("%d", &x);
if(x){
BT left= (BT)malloc(sizeof(struct TreeNode));
left->left=left->right=NULL;
left->Data=x;
bt->left=left;
add(left,q);
}
else
{
bt->left=NULL;
}

scanf("%d", &x);
if(x){
BT right= (BT)malloc(sizeof(struct TreeNode));
right->left=right->right=NULL;
right->Data=x;
bt->left=left;
add(right,q);
}
else
{
bt->right=NULL;
}
return bt;

}


转载请注明：PHP开发日志 >> APP开发 » 二叉树的创建和遍历