二叉树相关操作

时间：2021-07-29 17:27:31
先一层一层的遍历二叉树 用一个辅助的数据结构队列
队列！ 注意 这个很重要
队尾放节点 队头取出节点
比如：根节点放入队列 （开始只有这个一个节点在队列中）
然后呢 从队头取出这个根节点 然后打散 把他的左右孩子放入对尾（这时候有2个节点 也就是二叉树的第二层）
之后从队伍里取出这2个节点 打散 之后队伍里应该是 二叉树第三层的4个节点
。。。。。
这样就把二叉树层次遍历了
因为有些节点没有孩子节点 也就是叶子
这个队列中的节点 逐渐会越来越少
最后一个取出队列的节点 的深度也就是二叉树的高度

所以求二叉树的高度 就用这种层进性遍历 每次把节点放入队列中时 也把他的深度 和节点的指针一起放入 取出一个节点 打散的时候 注意他的子节点的度是他父节点的+1 就ok
int BiTreeDepthHierarchy(BiThrTree T)  //非递归类层次遍历求二叉树深度
{
int depth=0,hp,tp,lc; //hp为已访问的结点数，tp历史入队的结点总数，lc为每层最后一个结点标记
LinkQueue Q;
BiThrNode *p;
if(T)
{
  p=T;
  hp=0;tp=1;lc=1;
  InitQueue(Q);
  EnQueue(Q,p);
  while(!QueueEmpty(Q))
  {
   DeQueue(Q,p);
   hp++;      //hp为已访问的结点数
   if(p->lchild)
   {
    EnQueue(Q,p->lchild);
    tp++;     //tp记录历史入队的结点总数
   }
   if(p->rchild)
   {
    EnQueue(Q,p->rchild);
    tp++;
   }
   if(hp==lc)    //当hp=lc时，表明本层结点均已访问完
   {
    depth++;
    lc=tp;    //lc=tp，更新下层的末结点标记
   }
  }
}
return depth;
}

首先分析二叉树的深度（高度）和它的左、右子树深度之间的关系。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。
int Depth (BiTree T ){ // 返回二叉树的深度
   if ( !T )    depthval = 0;
   else   {
     depthLeft = Depth( T->lchild );
     depthRight= Depth( T->rchild );
     depthval = 1 + (depthLeft > depthRight  ?
                               depthLeft : depthRight);
   }
   return depthval;
}
 
#include<stdio.h>
#include<stdlib.h>
typedef struct BiTree{
     int data;
     struct BiTree *Lchild;
     struct BiTree *Rchild;
}BiTree_Node,*BiTree_Link;
BiTree_Link creat_BiTree();
int count;
int zount;
void xtravel_BiTree(BiTree_Link);
void ztravel_BiTree(BiTree_Link);
void htravel_BiTree(BiTree_Link);
int Ycount_BiTree(BiTree_Link);
int Zcount_BiTree(BiTree_Link);
void BiTree_detph(BiTree_Link);
void BiTree_root(BiTree_Link);
int main()
{
     BiTree_Link T;
     int n;
     printf("\n");
     do
     {
         printf("**********二叉树*********\n");
         printf("\n");
         printf("1、构建二叉树\n");
         printf("2、先序遍历二叉树\n");
         printf("3、中序遍历二叉树\n");
         printf("4、后序遍历二叉树\n");
         printf("5、二叉树的叶子结点数\n");
         printf("6、二叉树的结点数\n");
         printf("7、二叉树的根\n");
         printf("8、退出程序\n");
          printf("\n");
          printf("*************************\n");
         printf("请输入要选择的操作n=");
          scanf("%d",&n);
          switch(n){
          case 1:
               T=creat_BiTree();break;
          case 2:
               xtravel_BiTree(T);break;
          case 3:
               ztravel_BiTree(T);break;
          case 4:
               htravel_BiTree(T);break;
          case 5:
               Ycount_BiTree(T);
               printf("叶子结点数：%d\n",count);
               break;
          case 6:
               Zcount_BiTree(T);
               printf("结点总数：%d\n",zount);
               break;
          case 7:
               BiTree_root(T);break;
          }
     }while(n<8);
     return 0;
}

BiTree_Link creat_BiTree()
{
     BiTree_Link T;
     int n;
     scanf("%d",&n);
     if(n==0)
     {
          T=NULL;
     }
     else
     {
          T=(BiTree_Link)malloc(sizeof(BiTree_Node));
          if(NULL==T)
          {
               printf("Error!!!");
               exit(1);
          }
          T->data=n;
          printf("输入%d的左结点:",T->data);
          T->Lchild=creat_BiTree();
          printf("输入%d的右结点:",T->data);
          T->Rchild=creat_BiTree();
     }
     return T;
}
void xtravel_BiTree(BiTree_Link T)
{
     if(T!=NULL)
     {
          printf("%d ",T->data);
          xtravel_BiTree(T->Lchild);
          xtravel_BiTree(T->Rchild);
     }
}
void ztravel_BiTree(BiTree_Link T)
{
     if(T!=NULL)
     {
          ztravel_BiTree(T->Lchild);
          printf("%d ",T->data);
          ztravel_BiTree(T->Rchild);
     }
}
void htravel_BiTree(BiTree_Link T)
{
     if(T!=NULL)
     {
          htravel_BiTree(T->Lchild);
          htravel_BiTree(T->Rchild);
          printf("%d ",T->data);
     }
}
int Ycount_BiTree(BiTree_Link T)
{
     if(T!=NULL)
     {
          if((T->Lchild==NULL)&&(T->Rchild==NULL))
               count++;
          else
          {
               Ycount_BiTree(T->Lchild);
              Ycount_BiTree(T->Rchild);
          }
     }
     return count;
}
int Zcount_BiTree(BiTree_Link T)
{
     if(T!=NULL)
     {
          zount++;
          Zcount_BiTree(T->Lchild);
          Zcount_BiTree(T->Rchild);
     }
     return zount;
}
void BiTree_root(BiTree_Link T)
{
     if(T!=NULL)
     {
          printf("树根是:%d ",T->data);
     }
}


    /*输入文件自己建立*/ 
    #include <stdio.h> 
    #include <string.h> 
    #include <stdlib.h> 
    #define max 100 
    int x; 
    char ans[max]; 
    typedef struct Tree 
    { 
        char val; 
        struct Tree* pl; 
        struct Tree* pr; 
    }*T; 
    T createtree( T p ) 
    { 
        char ch; 
        scanf( "%c", &ch ); 
        if( ch == '#' ) 
            p = NULL; 
        else 
        { 
            p = (T)malloc( sizeof(struct Tree) ); 
            p->pl = createtree( p ); 
            p->val = ch; 
            p->pr = createtree( p ); 
        } 
        return p; 
    } 
    void view( T p ) 
    { 
        if( p != NULL ) 
        { 
            printf( "%c", p->val ); 
            view( p->pl ); 
            view( p->pr ); 
        } 
        else 
            return ; 
    } 
    void bfs( T root ) 
    { 
        T q[max]; 
        x = 0; 
        T u; 
        int front, rear; 
        rear = front = 0; 
        q[front++] = root; 
        while( front > rear ) 
        { 
            u = q[rear++]; 
            ans[x++] = u->val; 
            if( u->pl != NULL ) q[front++] = u->pl; 
            if( u->pr != NULL ) q[front++] = u->pr; 
        } 
    } 
    int main() 
    { 
        int i; 
        freopen( "in", "r", stdin ); 
        T root = NULL;   
        root = createtree( root ); 
        printf( "文件输入:  12##3## "); 
        printf( "\n\ndfs:\n" ); 
        view( root ); 
        printf( "\n\nbfs:\n" ); 
        bfs( root ); 
        for( i = 0; i < x; i++ ) 
            printf( "%c", ans[i] ); 
        return 0; 
    }  
标签：

相关文章