二叉树相关操作

时间: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; 
    }