1 #include <iostream>  2 #include <stdio.h>  3 #include <queue>  4 using namespace std;  5   6 /* 实验内容  7 该程序的功能是实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。  8 */  9  10 /* 定义DataType为char类型 */ 11 typedef char DataType; 12   13 /* 二叉树的结点类型 */ 14 typedef struct BitNode{ 15     DataType data; 16     struct BitNode *lchild,*rchild; 17 }BitNode,*BitTree; 18   19 /* 初始化二叉树，即把树根指针置空 */ 20 void BinTreeInit(BitTree &BT) 21 { 22     BT = NULL; 23 } 24   25 /* 按先序次序建立一个二叉树*/ 26 void BinTreeCreat(BitTree &BT) 27 { 28     //printf("请输入该节点的元素值："); 29     scanf("%c",&BT->data); 30     while(BT->data=http://www.mamicode.com/=‘ ‘ || BT->data=http://www.mamicode.com/=‘\n‘){ 31         scanf("%c",&BT->data); 32     } 33     if(BT->data=http://www.mamicode.com/=‘#‘){    //输入为‘#‘说明该节点为空,返回上一步 34         BT=NULL; 35         return ; 36     } 37     BT->lchild = (BitNode*)malloc(sizeof(BitNode)); 38     BT->rchild = (BitNode*)malloc(sizeof(BitNode)); 39     printf("请输入%c的左节点\n",BT->data); 40     BinTreeCreat(BT->lchild); 41     printf("请输入%c的右节点\n",BT->data); 42     //printf("进入右子树\n"); 43     BinTreeCreat(BT->rchild); 44 } 45   46 /* 检查二叉树是否为空 */ 47 int BinTreeEmpty(BitTree BT) 48 { 49     if(BT==NULL) 50         return 1; 51     else  52         return 0; 53 } 54   55 /* 按任一种遍历次序（包括按先序、中序、后序、按层次）输出二叉树中的所有结点 */ 56 void BinTraverse1(BitTree BT)    //按前序遍历 57 { 58     if(BT==NULL)    //递归出口 59         return ; 60     printf("%c",BT->data); 61     BinTraverse1(BT->lchild); 62     BinTraverse1(BT->rchild); 63 } 64  65 /* 按任一种遍历次序（包括按先序、中序、后序、按层次）输出二叉树中的所有结点 */ 66 void BinTraverse2(BitTree BT)    //按中序遍历 67 { 68     if(BT==NULL)    //递归出口 69         return ; 70     BinTraverse2(BT->lchild); 71     printf("%c",BT->data); 72     BinTraverse2(BT->rchild); 73 } 74  75 /* 按任一种遍历次序（包括按先序、中序、后序、按层次）输出二叉树中的所有结点 */ 76 void BinTraverse3(BitTree BT)    //按后序遍历 77 { 78     if(BT==NULL)    //递归出口 79         return ; 80     BinTraverse3(BT->lchild); 81     BinTraverse3(BT->rchild); 82     printf("%c",BT->data); 83 } 84  85 /* 按任一种遍历次序（包括按先序、中序、后序、按层次）输出二叉树中的所有结点 */ 86 void BinTraverse4(BitTree BT)    //按层次遍历 87 { 88     queue <BitTree> q; 89     BitTree cur = BT; 90     q.push(cur); 91     while(!q.empty()){    //队列空为止 92         cur = q.front(); 93         q.pop(); 94         if(cur==NULL)    //遇到空节点退出本次循环 95             continue; 96         printf("%c",cur->data);    //输出当前节点元素 97         q.push(cur->lchild);    //将该节点的两个孩子节点入栈 98         q.push(cur->rchild); 99     }100 }101  102 /* 求二叉树的深度 */103 int BinTreeDepth(BitTree BT)104 {105     if(BT==NULL)    //递归出口106         return 0;107     //记录左子树深度和右子树深度，返回较大的深度+1108     int ldp = BinTreeDepth(BT->lchild);109     int rdp = BinTreeDepth(BT->rchild);110     return ldp>rdp?ldp+1:rdp+1;111 }112  113 /* 求二叉树中所有结点数 */114 int  BinTreeCount(BitTree BT)115 {116     if(BT==NULL)    //递归出口117         return 0;118     //返回左子树节点数和右子树节点数再加上当前节点119     return BinTreeCount(BT->lchild) + BinTreeCount(BT->rchild) + 1;120 }121  122 /* 清除二叉树，使之变为空树 */123 void BinTreeClear(BitTree &BT)124 {125     if(BT==NULL)    //递归出口126         return ;127     //左右子树找到底，然后返回的时候依次销毁空间128     BinTreeClear(BT->lchild);129     BinTreeClear(BT->rchild);130     free(BT);131     BT=NULL;132 }133 134 int Menu()    //菜单135 {136     int n;137     printf("[1] 按先序次序建立一个二叉树\n");138     printf("[2] 检查二叉树是否为空\n");139     printf("[3] 按先序输出二叉树中的所有结点\n");140     printf("[4] 按中序输出二叉树中的所有结点\n");141     printf("[5] 按后序输出二叉树中的所有结点\n");142     printf("[6] 按层次输出二叉树中的所有结点\n");143     printf("[7] 求二叉树的深度\n");144     printf("[8] 求二叉树中所有结点数\n"); 145     printf("[9] 清除二叉树，使之变为空树\n");146     printf("[0] 退出\n");147     scanf("%d",&n);148     return n;149 }150 151 void Reply(BitTree &BT,int n)    //对菜单的响应152 {153     switch(n){154     case 1:    //创建二叉树155         if(BT!=NULL)156             printf("已创建二叉树! 请先清除二叉树再创建!\n");157         else{    //二叉树为空158             printf("按先序依次增加节点，输入‘#‘表示空节点！\n\n");159             BT = (BitNode*)malloc(sizeof(BitNode));    //创建根节点160             BT->lchild = NULL;161             BT->rchild = NULL;162             printf("请输入根节点的元素值：\n");163             BinTreeCreat(BT);164             printf("\n二叉树创建成功！\n\n");165         }166         break;167     case 2:    //检查二叉树是否为空168         if(BinTreeEmpty(BT))169             printf("二叉树为空!\n\n");170         else 171             printf("二叉树不为空!\n\n");172         break;173     case 3:    //按前序遍历174         if(BT==NULL){175             printf("二叉树为空！无法遍历！\n\n");176             break;177         }178         printf("前序遍历顺序为：\n");179         BinTraverse1(BT);180         printf("\n\n");181         break;182     case 4:    //按中序遍历183         if(BT==NULL){184             printf("二叉树为空！无法遍历！\n\n");185             break;186         }187         printf("中序遍历顺序为：\n");188         BinTraverse2(BT);189         printf("\n\n");190         break;191     case 5:    //按后序遍历192         if(BT==NULL){193             printf("二叉树为空！无法遍历！\n\n");194             break;195         }196         printf("后序遍历顺序为：\n");197         BinTraverse3(BT);198         printf("\n\n");199         break;200     case 6:    //按层次遍历201         if(BT==NULL){202             printf("二叉树为空！无法遍历！\n\n");203             break;204         }205         printf("层次遍历顺序为：\n");206         BinTraverse4(BT);207         printf("\n\n");208         break;209     case 7:    //求二叉树的深度210         printf("二叉树的深度为：%d\n\n",BinTreeDepth(BT));211         break;212     case 8:    //求二叉树的节点数213         printf("二叉树的总结点数为：%d\n\n",BinTreeCount(BT));214         break;215     case 9:    //清除二叉树216         if(BT==NULL){217             printf("二叉树已经为空！无需清空！\n\n");218             break;219         }220         BinTreeClear(BT);221         printf("清除成功！\n\n");222         break;223     default:224         exit(1);225     }226     system("pause");227     system("cls");228 }229 230 int main()231 {232     BitTree BT = NULL;233     BinTreeInit(BT);    //初始化二叉树234     while(1){235         int n = Menu();236         Reply(BT,n);237     }238     return 0;239 }