实验四 二叉树操作实现

实验四二叉树操作实现实验四二叉树操作实现实验四二叉树操作实现实验四二叉树操作实现编制仅供参考审核批准生效日期地址：电话：传真:邮编:实验四二叉树操作实现实验日期：2017年4月20日实验目的及要求1.熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现；2.重点掌握二叉树的创建、遍历及求深度等算法；3.掌握运用递归方式描述算法及编写递归C程序的方法，提高算法分析和程序设计能力。实验内容键盘输入一个字符串，利用二叉树前序遍历的结果建成一棵二叉树，并用三种遍历方法打印，比较是否与自己预先想象的相一致。再求树的深度、1度结点数、2度节点数，交换二叉树的左右子树并输出交换后的中序遍历结果验证交换的正确性。找到二叉树中序遍历最后一个结点并输出结点值。二叉树结点类型定义：typedefchardatatype;typedefstructtnode{datatypedata;structtnode*lchild,*rchild;}BiTNode,*BiTree;任务1．题目要求创建一个程序文件，自定义相应函数完成以下操作：（1）voidvisit(BiTreep)/*输出p指针指向的结点*/（2）voidPreorder(BiTreeT)/*前序遍历*/（3）voidInorder(BiTreeT)/*中序遍历*/（4）voidPostorder(BiTreeT)/*后序遍历*/（5）BiTreeCreateTree()/*以前序遍历的顺序建立二叉树*/（6）intdeep(BiTreeT)/*求二叉树深度*/（7）intleaf(BiTreeT)/*求叶子结点数*/（8）intOneChild(BiTreeT)/*求1度结点数*/（9）intTwoChild(BiTreeT)/*求2度结点数*/（10）voidExchange(BiTreeT)/*二叉树左右子树交换*/（11）BiTreeInorderLastNode(BiTreeT);/*找二叉树中序遍历最后一个结点*/2．请回答下列问题（1）在n个结点二叉树的二叉链表存储中，其指针域的总数为2n个，其中n-1个用于链接孩子结点，n+1个空闲着。（2）在二叉链表存储中，数据域值为data，左右子树的指针分别为left和right，则判断：指针p所指结点为0度结点的条件是p->left==NULL&&p->right==NULL；指针p所指结点为1度结点的条件是(p->left==NULL&&p->right!=NULL)||(p->left!=NULL&&p->right==NULL)；指针p所指结点为2度结点的条件是p->left!=NULL&&p->right!=NULL。（3）T为二叉树的根的地址，该树是空二叉树满足条件：T==NULL。3．源程序清单（含必要的注释）#include<>#include<>typedefchardatatype;typedefstructtnode{ datatypedata; structtnode*lchild,*rchild;}BiTNode,*BiTree;voidvisit(BiTreep);/*输出p指针指向的结点*/voidPreorder(BiTreeT);/*前序遍历*/voidInorder(BiTreeT);/*中序遍历*/voidPostorder(BiTreeT);/*后序遍历*/BiTreeCreateTree();/*以前序遍历的顺序建立二叉树*/intdeep(BiTreeT);/*求二叉树深度*/intleaf(BiTreeT);/*求叶子结点数*/intOneChild(BiTreeT);/*求1度结点数*/intTwoChild(BiTreeT);/*求2度结点数*/voidExchange(BiTreeT);/*二叉树左右子树交换*/BiTreeInorderLastNode(BiTreeT);/*找二叉树中序遍历最后一个结点*/voidvisit(BiTreep){/*输出p指针指向的结点*/ if(p->data!='#'){ printf("%c",p->data); }}voidPreorder(BiTreeT){/*前序遍历*/ if(T!=NULL){ visit(T);//访问根节点 Preorder(T->lchild);//访问左子节点 Preorder(T->rchild);//访问右子节点 }}voidInorder(BiTreeT){/*中序遍历*/ if(T!=NULL){ Inorder(T->lchild);//访问左子节点 visit(T);//访问根节点 Inorder(T->rchild);//访问右子节点 }}voidPostorder(BiTreeT){/*后序遍历*/ if(T!=NULL){ Postorder(T->lchild);//访问左子节点 Postorder(T->rchild);//访问右子节点 visit(T);//访问根节点 }}BiTreeCreateTree(){/*以前序遍历的顺序建立二叉树*/ charch; BiTreeT; if((ch=getchar())=='#'){/*#表示空树*/ returnNULL; } else{ T=(BiTree)malloc(sizeof(BiTNode));//生成根节点 T->data=ch; T->lchild=CreateTree();//构造左子树 T->rchild=CreateTree();//构造右子树 returnT; }}intdeep(BiTreeT){/*求二叉树深度*/ intlh,rh; if(T==NULL){ return0; } else{ lh=deep(T->lchild); rh=deep(T->rchild); } return(lh>rhlh:rh)+1;}intleaf(BiTreeT){/*求叶子结点数*/ intm,n; if(!T){/*空树没有叶子*/ return0; } elseif(!T->lchild&&!T->rchild){/*叶子结点*/ return1; } else{/*左子树的结点数加上右子树的结点数*/ m=leaf(T->lchild); n=leaf(T->rchild); returnm+n; }}intOneChild(BiTreeT){/*求1度结点数*/ intn=0; if(T==NULL){ return0; } elseif((T->lchild==NULL&&T->rchild!=NULL)||(T->lchild!=NULL&&T->rchild==NULL)){ n=1; } returnOneChild(T->lchild)+OneChild(T->rchild)+n;}intTwoChild(BiTreeT){/*求2度结点数*/ intn=0; if(T==NULL){ return0; } elseif((T->lchild!=NULL&&T->rchild!=NULL)) { n=1; } returnTwoChild(T->lchild)+TwoChild(T->rchild)+n;}voidExchange(BiTreeT){/*二叉树左右子树交换*/ BiTreetemp; if(T){ temp=T->lchild; T->lchild=T->rchild; T->rchild=temp; Exchange(T->lchild); Exchange(T->rchild); }}BiTreeInorderLastNode(BiTreeT){/*找二叉树中序遍历最后一个结点*/ if(T) while(T->rchild) { T=T->rchild; } returnT;}intmain(){ BiTreeT; printf("以前序遍历的二叉树:"); T=CreateTree(); printf("\n先序遍历:"); Preorder(T); printf("\n"); printf("\n中序遍历:"); Inorder(T); printf("\n"); printf("\n后序遍历:"); Postorder(T); printf("\n"); printf("\n树的深度=%d\n",deep(T)); printf("叶子结点数=%d\n",leaf(T)); printf("1度结点数=%d\n",OneChild(T)); printf("2度结点数=%d\n",TwoChild(T)); printf("\n二叉树中序遍历最后一个结点为:%c",InorderLastNode(T)->data); printf("\n"); printf("\n交换后的二叉树先序遍历为:"); Exchange(T);Preorder(T); printf("\n交换后的二叉树中序遍历为:"); Inorder(T); printf("\n交换后的二叉树后序遍历为:");