二叉树的操作及应用

实验四二叉树的操作及应用实验学时：4实验类型：(设计型)一、实验目的1. 理解并掌握二叉树的逻辑结构和物理结构——二叉链表；2. 掌握二叉树的遍历方法；3. 掌握二叉树的构造方法；4. 掌握计算二叉树结点个数、高度、叶子结点个数算法实现；5. 掌握交换二叉树左右子树以及复制一棵二叉树算法的实现二、实验条件Visual C++ 6.0三、实验原理及相关知识1. 二叉树的存储结构描述；2. 二叉树中序、前序、后序、层次遍历的基本思想；3. 构造二叉树的基本思想；4. 求二叉树结点个数、高度、叶子结点个数算法的基本思想；5. 交换二叉树左右子树以及复制一棵二叉树算法的基本思想四、实验步骤1. 确定存储结构，写出二叉链表结构类型的具体定义2. 基本操作的算法实现(1) 中序、前序、后序、层次遍历的递归算法的基本思想及算法实现；(2) 利用先序序列构造二叉树方法的基本思想及算法实现；(3) 求结点个数、高度、叶子结点个数、交换二叉树左右子树以及复制一棵二叉树的递归 算法的基本思想及算法实现五、思考题及其它1.线索二叉树的构造及线索化方法的算法实现参考程序1】#include#include#include #define MaxSize 20typedef int ElemType;#define OK 1typedef struct BiTNode{ElemType data;struct BiTNode *lchild, *rchild;}BiTNode,*BiTree;//建立二叉树(按先序序列生成二叉树,#表示空节点) void CreateBiTree(BiTree *T){char ch; scanf("%c",&ch);get char();/*回车键(每次输入一个字符后，需敲回车键)*/ if(ch=='#'){printf("不产生子树。

\n");*T=NULL;}else{if(!(*T=(BiTNode *)malloc(sizeof(BiTNode)))){prin tf("分配空间失败")； return;}//生成一个新节点(*T)->data = ch;printf("产生左右子树\n");}}//递归前序遍历void Preorder(BiTNode *T){if(T){printf("%c ",T->data);Preorder(T->lchild);Preorder(T->rchild);}}//递归中序遍历void Inorder(BiTNode *T){if(T){//递归后序遍历void Postorder(BiTNode *T) {if(T){}}//层次遍历二叉树void Translever(BiTNode *T){struct node{BiTNode *vec[MaxSize];int f,r; //r为队尾，f为队头}queue;BiTNode *p;p=T;queue.f=0;queue.r=0;if(T)printf("%c ", p->data);queue.vec[queue.r]=p;queue.r=queue.r+1;while(queue.flchild){printf("%c ",p->lchild->data); queue.vec[queue.r]=p->lchild; queue.r=queue.r+1;}if(p->rchild){} printf("\n");}//按广义表形式输出二叉树void Disptree(BiTNode *T){if(T){ printf("%c",T->data); if(T->lchild || T->rchild){printf("(");Disptree(T->lchild); if(T->rchild) printf(",");Disptree(T->rchild); printf(")");}}}void main(){BiTree T=NULL;int j;int sign = 1;int num;printf(〃本程序可以进行建立二叉树、递归先序、中序、后序遍历二叉树、层次遍历二 叉树、输出二叉树的扩展序列的操作。

\『)；prin tf("请将二叉树的先序序列输入以建立二叉树\n");prin tf ("您必须一个一个地输入字符\『)；while(sign){prin tf("请选择：\n");printf (〃1.生成二叉树(#表示空结点) \n");printf (〃2.递归先序遍历 3.递归中序遍历\n〃)；printf (〃4.递归后序遍历 5.层次遍历\n");printf ("6.输出二叉树的广义表形式 \n");printf ("0.退出程序\n");scanf("%d",&j);getchar();switch(j){case 1:prin tf("生成二叉树:")；CreateBiTree(&T);printf("\n");printf("\n");break;case 2:if(T){prin tf("递归先序遍历二叉树:")；Preorder(T);printf("\n");printf("\n");}elseprin tf("二叉树为空!\n");break;case 3:if(T){prin tf("递归中序遍历二叉树:")；Inorder(T); printf("\n"); printf("\n");}else prin tf("二叉树为空!\n"); break;case 4:if(T){prin tf("递归后序遍历二叉树:")；Postorder(T);printf("\n");printf("\n");}else prin tf("二叉树为空!\n"); break;case 5:if(T){prin tf ("层次遍历二叉树:")；Translever(T);printf("\n"); printf("\n");else prin tf("二叉树为空!\n"); break;case 6:if(T){prin tf("输出二叉树:")；Disptree(T);printf("\n");printf("\n");}else prin tf("二叉树为空!\n");break;default:sign=0;prin tf("程序运行结束，按任意键退出!\n");}}}【参考程序2】#include#include#include #defineMaxSize 20typedef int ElemType;#define OK 1int count;typedef struct BiTNode{ElemType data;struct BiTNode *lchild, *rchild;}BiTNode,*BiTree;//建立二叉树(按先序序列生成二叉树,#表示空节点)void CreateBiTree(BiTree *T){char ch;scanf("%c",&ch);getchar()回车键(每次输入一个字符后，需敲回车键)*/ if(ch=='#'){printf不产生子树。

\n");*T=NULL;}else{if(!(*T=(BiTNode *)malloc(sizeof(BiTNode)))) {prin tf分配空间失败")； return;}//生成一个新节点(*T)->data = ch;printf产生左右子树\n");CreateBiTree(&((*T)->lchild)) ;CreateBiTree(&((*T)->rchild;))}}int Coun t_ Tree(BiTree计算二叉树的结点个数{int lcount,rcount;if(t==NULL) return 0;return lcount+rcount+1;}int Heigh t(BiTree计算二叉树的高度{int h1,h2; if(t==NULL) return 0;else {hl二Heigh t(t-〉lchild求左子树的高度 h2=Height(t->rchild);if(h1〉h2) return h1+求右子树的高度 return h2+l;} }void Coun tleaf(BiTree t,in t * C计算二叉树的叶子结点的个数 {if(t==NULL) *count=0;if(t-〉lchild==0 && t-〉rchild==0) (*count)++;if(t->lchild!=0) Countleaf(t->lchild,count);if(t->rchild!=0) Countleaf(t->rchild,count);}void Swapbi tree(BiTree交换二叉树的左右子树{BiTree p;if(t==NULL) return;Swapbitree(t->lchild); Swapbitree(t->rchild);p=t->lchild; t->lchild=t->rchild; t->rchild=p;}void Copybi tree(BiTree tl,BiTre复制2一/果二叉树{if (t1==NULL) {t2=NULL; return;}t2=(BiTree)malloc(sizeof(BiTNode)); t2->data=t1->data;}void Preorder(BiTree T){if(T){printf("%c ",T->data);Preorder(T->lchild);Preorder(T->rchild);}}void main(){BiTree T=NULL,T1=NULL;int j;int sign = 1;int num;count=0;prin tf本程序可以建立二叉树、求二叉树的结点个数、高度、叶子结点个数，交换二叉 树的左右子树，复制一棵二叉树。

\n");prin tf请将二叉树的先序序列输入以建立二叉树\n");printf您必须一个一个地输入字符\n");while(sign){pri ntf请选择：\n");prin tf(‘生成二叉树(#表示空结点) prin tf(递归求结点个数 prin tf(递归求叶子结点个数 prin tf(递归复制一棵二叉树 prin tf(退出程序\n");scanf("%d",&j);getchar();switch(j){case 1:prin tf生成二叉树：")； CreateBiTree(&T); printf("\n"); printf("\n");break;\n");3. 递归求高度\n ");5.递归交换二叉树左右子树\n");7.输出二叉树\n");case 2:if(T){ printf递归求二叉树的结点个数：\n");printf二叉树的结点个数为：％d\n",Count_Tree(T));}elseprin tf二叉树为空!\n"); break;case 3:if(T) {printf递归求二叉树的高度：\n");printf二叉树的高度为：％d\n",Height(T)); }else print二叉树为空！\n"); break;case 4: if(T) {printf递归求二叉树的叶子结点个数：\n"); Countleaf(T,&count);printf二叉树的叶子结点个数为：％d\n",count); }else print二叉树为空！\n"); break;case 5:if(T){printf递归交换二叉树左右子树：\n");Swapbitree(T);Preorder(T); printf("\n");}else print二叉树为空！\n");break;case 6:if(T){printf递归复制二叉树左右子树：\n");Copybitree(T,T1) ;Preorder(T1);printf("\n");}else print二叉树为空！\n");break;case 7:if(T){printf二叉树的遍历序列为：");Preorder(T);printf("\n");}else print二叉树为空！\n");break;default:sign=0;prin tf程序运行结束，按任意键退出!\n");。