C++ 二叉树的基本操作

实验五:二叉树的基本操作

(1)输入字符序列,建立二叉链表。

(2)先序、中序、后序遍历二叉树:递归算法。

(3)中序遍历二叉树:非递归算法。(最好也能实现先序、后序非递归算法)

(4)求二叉树的高度 。

(5)求二叉树的叶子个数。

(6)借助队列实现二叉树的层次遍历。

(7)在主函数中设计一个简单的菜单,分别调试上述算法。

参考源码

#include<stdio.h>

#include<stdlib.h>

#define OK 1

#define ERROR 0

#define OVERFLOW -1

#define LIST_INT_SIZE 100

#define LISTINCREMENT 10

int dep, count= 0;

typedef int Status;

typedef char TElemType;

 

typedef struct BiTNode{

         TElemType data;

         struct BiTNode *lchild, *rchild;

}BiTNode, *BiTree;

 

//建立二叉树

Status CreateBiTree(BiTree &T)

{

         char ch;

        

         getchar();

         scanf("%c", &ch);

         if(ch == ' '|| ch == '\n')

         {

                   T = NULL;

                   return ERROR;

         }

         else

         {

                   T = (BiTree)malloc(sizeof(BiTNode));

                   T->data = ch;

                   printf("请输入%c的左孩子:", T->data);

                   CreateBiTree(T->lchild);

                   printf("请输入%c的右孩子:", T->data);

                   CreateBiTree(T->rchild);

                   return OK;

         }

}

 

 

 

//主菜单

void print()

{

         printf("\n菜单如下:\n");

         printf("1 . 输入字符序列,建立二叉链表\n");

         printf("2 . 先序、中序、后序遍历二叉树:递归算法\n");

         printf("3 . 先序、中序、后序遍历二叉树:非递归算法\n");

         printf("4 . 求二叉树的高度 \n");

         printf("5 . 求二叉树的叶子个数\n");

         printf("6 . 借助队列实现二叉树的层次遍历\n");

         printf("0 . EXIT\n请选择操作序号:");

}

 

//先序、中序、后序遍历二叉树:递归算法

void print2()

{

         printf("\n递归算法遍历二叉树,菜单如下:\n");

         printf("1.先根遍历\n");

         printf("2.中序遍历\n");

         printf("3.后续遍历\n");

         printf("0.退出\n");

         printf("请输入二级菜单选择:");

}

 

Status Visit(BiTree T)

{

         if(T)

         {

                   printf("%c ", T->data);

                   return OK;

         }

}

 

Status PrintElement(TElemType e)

{

         printf(" %c ", e);

         return OK;

}

 

//先序

Status PreOrderTraverse(BiTree T, Status (*Visit)(TElemType e))

{

         if(T)

         {

                   if(Visit(T->data))

                            if(PreOrderTraverse(T->lchild, Visit))

                                     if(PreOrderTraverse(T->rchild, Visit))

                                               return OK;

                            return ERROR;

         }

         else

                   return OK;

}

 

//中序

Status MidOrderTraverse(BiTree T, Status (*Visit)(TElemType e))

{

         if(T)

         {

                   if(MidOrderTraverse(T->lchild, Visit))

                            if(Visit(T->data))

                                     if(MidOrderTraverse(T->rchild, Visit))

                                               return OK;

                            return ERROR;

         }

         else

                   return OK;

}

//后序

Status LastOrderTraverse(BiTree T, Status (*Visit)(TElemType e))

{

         if(T)

         {       

                   if(LastOrderTraverse(T->lchild, Visit))

                            if(LastOrderTraverse(T->rchild, Visit))

                                     if(Visit(T->data))

                                               return OK;

                            return ERROR;

         }

         else

                   return OK;

}

 

//求树的叶子的个数,和打印出叶子

Status LeafNumTree(BiTree T)

{

         int lnum,rnum;

         if(T!=NULL)

         {

                   if(T->lchild==NULL && T->rchild==NULL)

                            return 1;

                   else

                   {

                            lnum=LeafNumTree(T->lchild);

                            rnum=LeafNumTree(T->rchild);

                            return lnum+rnum;

                   }

         }

         return 0;

}

 

//求二叉树的高度

Status BiTreeDepth(BiTree T)

{

         int l,r;

         if(T)

         {

                   l=BiTreeDepth(T->lchild);

                   r=BiTreeDepth(T->rchild);

                   if(l>=r)

                            dep += l;

                   else dep += r;

         }

         else

                   return 1;

}

 

//先序、中序、后序遍历二叉树:非递归算法

void print3()

{

         printf("\n非递归算法遍历二叉树,菜单如下:\n");

         printf("1.先根遍历\n");

         printf("0.退出\n");

         printf("请输入二级菜单选择:");

}

 

typedef struct QueueNode

{

         BiTree e;

         struct QueueNode *next;

}QueueNode,*QueuePtr;                   //定义队列结点结构

typedef struct

{

         QueuePtr front;

         QueuePtr rear;

}LinkQueue;  

 

 

//栈的顺序存储表示

 typedef struct

 { BiTNode *base;   //栈底指针

   BiTNode *top;    //栈顶指针

   int   stacksize; //当前已分配的存储空间

 }SqStack;

 

//初始化一个带头结点的队列

void InitQueue(LinkQueue &q)

{

         q.front=q.rear=(QueuePtr)malloc(sizeof(QueueNode));

         q.front->next=NULL;

}

 

//入队列

void enqueue(LinkQueue &q,BiTree p)

{

         QueuePtr s;

         int first=1;

         s=(QueuePtr)malloc(sizeof(QueueNode));

         s->e =p;

         s->next=NULL;

         q.rear->next=s;

         q.rear=s;

}

 

//出队列

void dequeue(LinkQueue &q,BiTree &p)

{

         char data;

         QueuePtr s;

         s=q.front->next;

         p=s->e ;

    data=p->data;

         q.front->next=s->next;

         if(q.rear==s)

                   q.rear=q.front;

         free(s);

         printf("%c\t",data);

}

 

//判断队列是否为空

Status queueempty(LinkQueue q)

{

         if(q.front->next==NULL)

                   return 1;

         return 0;

}

//按层次遍历树中结点

void Traverse(BiTree T)

{

         LinkQueue q;

         BiTree p;

         InitQueue(q);

         p=T;

         enqueue(q,p);

         while(queueempty(q)!=1)

         {

                   dequeue(q,p);

                   if(p->lchild!=NULL)

                            enqueue(q,p->lchild);

                   if(p->rchild!=NULL)

                            enqueue(q,p->rchild);

         }

         printf("\n");

}

 

 //建立一个空栈

 void InitStack(SqStack &S)

 {    S.base=(BiTree)malloc(LIST_INT_SIZE * sizeof(BiTNode));

    if(!S.base)

                   exit(OVERFLOW );//存储分配失败

    S.top=S.base;

    S.stacksize=LIST_INT_SIZE;

 }

 

 //压入栈

 void Push(SqStack & S,BiTree p)

 { if(S.top-S.base>=S.stacksize)//满栈,追加存储结构

 {    S.base= (BiTree)realloc(S.base,(S.stacksize+LISTINCREMENT) * sizeof(BiTNode));

      if(!S.base)  exit(OVERFLOW );//存储分配失败

           S.top=S.base+S.stacksize;   

           S.stacksize+=LISTINCREMENT;

 }

           *(++S.top)=*p;

 }

 

 //退出栈

bool Pop(SqStack &S,BiTree &p)

{  if( S.top==S.base)

 {   printf("空栈\n");

     return false;

 }

     p=(BiTree)malloc( sizeof(BiTNode));

    *p=*S.top;

    --S.top;

    return true;

 }

 

 //判断是否是空栈       

 bool StackEmpty(SqStack &S)

 {   if( S.top==S.base) 

       return true;

    else

          return  false ;

 }

 

 

Status InOrderTraverAndCountLeaf(BiTree &T,Status(* Vist)(TElemType e))

{   int j=0,count=0;

         BiTree p;

         p=(BiTNode *)malloc( sizeof(BiTNode));//关键一步

         p=T;

    SqStack s;

         InitStack(s);

         while(p||!StackEmpty(s))

         { if(p)

         {  Push(s,p);//如果p为非空,将p压入栈

            if(!(p->lchild)&&!(p->rchild))

                     ++count;//记录叶子节点数

            p=p->lchild;        

         }//if

          else

          {

            Pop(s,p);//如果p为空,则p退栈

            Vist(p->data);

       p=p->rchild;

            }//else

         }//while

    return  count;

}

 

int main()

{

         int n, ncase;

         int count;

         bool f, f1, f2, f3;

         BiTree T;

         TElemType e;

         print();

         while(scanf("%d", &n)!=EOF)

         {

                  

                   f = true;

 

                   switch(n)

                   {

                   case 1:

                            printf("输入空格或回车表示此结点为空结束\n请输入头结点:");

                            if(CreateBiTree(T))

                                     printf("二叉树建立成功!\n");

                            else

                                     printf("二叉树建立失败!\n");

                            break;

                   case 2:

                            print2();

                            while(scanf("%d", &ncase)!= EOF)

                            {

                                     f1 = true;

                                     switch(ncase)

                                     {

                                     case 1:

                                               printf("先序遍历顺序为:");

                                               if(PreOrderTraverse(T, PrintElement))

                                                        printf("先序遍历成功!\n");

                                               else

                                                        printf("先序遍历失败!\n");

                                               break;

                                     case 2:

                                               printf("中序遍历顺序为:");

                                               if(MidOrderTraverse(T, PrintElement))

                                                        printf("中序遍历成功!\n");

                                               else

                                                        printf("中序遍历失败!\n");

                                               break;

                                     case 3:

                                               printf("后序遍历顺序为:");

                                               if(LastOrderTraverse(T, PrintElement))

                                                        printf("后序遍历成功!\n");

                                               else

                                                        printf("后序遍历失败!\n");

                                               break;

                                     case 0:

                                               f1 = false;

                                               break;

                                     default :

                                               printf("输入错误,请重新输入!\n");

                                     }

                                     if(!f1)

                                               break;

                                     print2();

                            }

                  

                            break;

                   case 3:

                            print3();

                            while(scanf("%d", &ncase)!= EOF)

                            {

                                     f2 = true;

                                     switch(ncase)

                                     {

                                     case 1:

                                               InOrderTraverAndCountLeaf(T,PrintElement);

                                               break;

                                     case 0:

                                               f2 = false;

                                               break;

                                     default :

                                               printf("输入错误,请重新输入!\n");

                                     }

                                     if(!f2)

                                               break;

                                     print3();

                            }
                            break;

                   case 4:

                            dep = 0;

                            BiTreeDepth(T);

                            printf("二叉树的高度为:%d\n", dep-1);

                            break;

                   case 5:

                            count = LeafNumTree(T);

                            printf("二叉树的叶子个数为:%d\n", count);

                            break;

                   case 6:

                            printf("按层次遍历的顺序为:\n");

                            Traverse(T);

                            printf("\n");

                            break;

                   case 0:

                            f = false;

                            break;

                   default:

                            printf("输入错误,请重新输入!\n");

                            break;

                   }

                   if(!f)
                   {
                            printf("退出程序...\n");
                            break;
                   }

                   print();

         }

         return 0;

}

参考

迁移自谢先斌的博客:http://blog.sina.com.cn/s/blog_002e203101010bvm.html

完毕。