实验四 二叉树操作实现

《实验四 二叉树操作实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验四二叉树操作实现实验日期：2017年4月20日实验目的及要求1.熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现；2.重点掌握二叉树的创建、遍历及求深度等算法；3.掌握运用递归方式描述算法及编写递归C程序的方法，提高算法分析和程序设计能力。实验内容键盘输入一个字符串，利用二叉树前序遍历的结果建成一棵二叉树，并用三种遍历方法打印，比较是否与自己预先想象的相一致。再求树的深度、1度结点数、2度节点数，交换二叉树的左右子树并输出交换后的中序遍历结果验证交换的正确性。找到二叉树中序遍历最后一个结点并输出结点值。二叉树结点类型定义：typedefchard

2、atatype;typedefstructtnode{datatypedata;structtnode*lchild,*rchild;}BiTNode,*BiTree;任务1．题目要求创建一个程序文件sy4.cpp，自定义相应函数完成以下操作：（1）voidvisit(BiTreep)/*输出p指针指向的结点*/（2）voidPreorder(BiTreeT)/*前序遍历*/（3）voidInorder(BiTreeT)/*中序遍历*/（4）voidPostorder(BiTreeT)/*后序遍历*/（5）BiTreeCreateTree()/*以前序遍历的顺序建

3、立二叉树*/（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个空闲着。

4、（2）在二叉链表存储中，数据域值为data，左右子树的指针分别为left和right，则判断：指针p所指结点为0度结点的条件是p->left==NULL&&p->right==NULL；指针p所指结点为1度结点的条件是(p->left==NULL&&p->right!=NULL)

5、

6、(p->left!=NULL&&p->right==NULL)；指针p所指结点为2度结点的条件是p->left!=NULL&&p->right!=NULL。（3）T为二叉树的根的地址，该树是空二叉树满足条件：T==NULL。3．sy14.cpp源程序清单（含必要的注释）#include

7、#includetypedefchardatatype;typedefstructtnode{datatypedata;structtnode*lchild,*rchild;}BiTNode,*BiTree;voidvisit(BiTreep);/*输出p指针指向的结点*/voidPreorder(BiTreeT);/*前序遍历*/voidInorder(BiTreeT);/*中序遍历*/voidPostorder(BiTreeT);/*后序遍历*/BiTreeCreateTree();/*以前序遍历的顺序建立二叉树*/int

8、deep(BiTreeT);/*求二叉树深度*/intleaf(BiTreeT);/*求叶子结点数*/intOneChild(BiTreeT);/*求1度结点数*/intTwoChild(BiTreeT);/*求2度结点数*/voidExchange(BiTreeT);/*二叉树左右子树交换*/BiTreeInorderLastNode(BiTreeT);/*找二叉树中序遍历最后一个结点*/voidvisit(BiTreep){/*输出p指针指向的结点*/if(p->data!='#'){printf("%c",p->data);}}voidPreorder(Bi

9、TreeT){/*前序遍历*/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);//访问左子节

10、点Post