说明

二叉树的基本操作: 递归建立和非递归建立、遍历二叉树、求树高。

C程序实现

#include "iostream"  #include "malloc.h"  using namespace std;  #define Maxsize 1024  typedef char datatype;  typedef struct node  {      datatype data;      struct node*lchild,*rchild;  }bitree;  bitree*CreatTree()//非递归的方式建立完全二叉树  {      cout<<"连续输入字符建立完全二叉树，并以‘#’结束"<
     
      data=ch;          s->lchild=NULL;          s->rchild=NULL;          rear++;          Q[rear]=s;          if (rear==1)              root=s;          else          {              if(s&&Q[front])              {                  if(rear%2==0)                      Q[front]->lchild=s;                  else                      Q[front]->rchild=s;              }              if(rear%2==1)                  front++;          }      }      return root;  }  bitree *CreatTree2(int i,int n)//定义的方式建立完全二叉树                                 //不够通用，仅提供一种参考  {      bitree *root;      root=(bitree*)malloc(sizeof(bitree));      root->data=i;      if(2*i<=n)              //若2*i<=n，那么tree的左孩子为tree[2*i]；          root->lchild=CreatTree2(2*i,n);      else          root->lchild=NULL;      if(2*i+1<=n)//若2*i+1<=n，那么tree的右孩子为tree[2*i+1]；          root ->rchild=CreatTree2(2*i+1,n);      else          root->rchild=NULL;      return root;  }  void PreOrder(bitree*p)//前序递归遍历  {      if (p!=NULL)      {          cout<<"->"<
      
       data;          PreOrder(p->lchild);          PreOrder(p->rchild);      }  }  void InOrder(bitree*p)//中序递归遍历  {      if (p!=NULL)      {          InOrder(p->lchild);          cout<<"->"<
       
        data;          InOrder(p->rchild);      }  }  void NinOrder(bitree*p)//非递归的中序遍历，其他两种非递归遍历诸君自己实现  {      bitree*stack[Maxsize];      bitree*s=p;      int top=-1;      while (top!=-1||s!=NULL)      {          while (s!=NULL)          {              if (top==Maxsize-1)              {                  cout<<"OVERFLOW";                  return;              }              else              {                  top++;                  stack[top]=s;                  s=s->lchild;              }          }          s=stack[top];          top--;          cout<
        
         data;          s=s->rchild;      }  }  void PostOrder(bitree*p)//后序递归遍历  {      if (p!=NULL)      {          PostOrder(p->lchild);          PostOrder(p->rchild);          cout<<"->"<
         
          data;      }  }  void Layer(bitree*p)//用队列实现广度优先遍历  {      bitree*Q[Maxsize];      bitree*s;      int rear=1,front=0;      Q[rear]=p;      while (front
          
           "<
           
            data; if (s->lchild!=NULL) { rear++; Q[rear]=s->lchild; } if (s->rchild!=NULL) { rear++; Q[rear]=s->rchild; } } } int CountLeaf(bitree*p)//计算叶子节点数目 { if(!p) return 0; else if(!p->lchild&&!p->rchild) return 1; else return CountLeaf(p->lchild)+CountLeaf(p->rchild); } int Height(bitree*p)//计算数的高度 { int lc,rc; if(p==NULL) return 0; lc=Height(p->lchild)+1; rc=Height(p->rchild)+1; return lc>rc?lc:rc; } int main() { bitree*p; int leaf,height; p=CreatTree(); cout<<"深度优先遍历如下所示"<
            
             <