实验四 二叉树操作实现(7页).doc

-实验四 二叉树操作实现实验日期： 2017 年 4 月 20 日 实验目的及要求1. 熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现；2. 重点掌握二叉树的创建、遍历及求深度等算法；3. 掌握运用递归方式描述算法及编写递归C程序的方法，提高算法分析和程序设计能力。实验内容键盘输入一个字符串，利用二叉树前序遍历的结果建成一棵二叉树，并用三种遍历方法打印，比较是否与自己预先想象的相一致。再求树的深度、1度结点数、2度节点数，交换二叉树的左右子树并输出交换后的中序遍历结果验证交换的正确性。找到二叉树中序遍历最后一个结点并输出结点值。二叉树结点类型定义：typedef char datatype; typedef struct tnode datatype data; struct tnode *lchild,*rchild; BiTNode,*BiTree; 任务1题目要求创建一个程序文件sy4.cpp，自定义相应函数完成以下操作：（1）void visit(BiTree p) /*输出p指针指向的结点*/（2）void Preorder(BiTree T) /*前序遍历*/（3）void Inorder(BiTree T) /*中序遍历*/（4）void Postorder(BiTree T) /*后序遍历*/（5）BiTree CreateTree( ) /*以前序遍历的顺序建立二叉树*/（6）int deep(BiTree T) /*求二叉树深度*/（7）int leaf(BiTree T) /*求叶子结点数*/（8）int OneChild(BiTree T) /*求1度结点数*/（9）int TwoChild(BiTree T) /*求2度结点数*/（10）void Exchange(BiTree T) /*二叉树左右子树交换*/（11）BiTree InorderLastNode(BiTree T); /*找二叉树中序遍历最后一个结点*/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 。3sy14.cpp源程序清单（含必要的注释）#include<stdio.h>#include<stdlib.h>typedef char datatype;typedef struct tnode datatype data;struct tnode *lchild, *rchild; BiTNode, *BiTree;void visit(BiTree p); /*输出p指针指向的结点*/void Preorder(BiTree T); /*前序遍历*/void Inorder(BiTree T); /*中序遍历*/void Postorder(BiTree T); /*后序遍历*/BiTree CreateTree(); /*以前序遍历的顺序建立二叉树*/int deep(BiTree T); /*求二叉树深度*/int leaf(BiTree T); /*求叶子结点数*/int OneChild(BiTree T); /*求1度结点数*/int TwoChild(BiTree T); /*求2度结点数*/void Exchange(BiTree T); /*二叉树左右子树交换*/BiTree InorderLastNode(BiTree T); /*找二叉树中序遍历最后一个结点*/void visit(BiTree p) /*输出p指针指向的结点*/if (p->data != '#') printf("%c ", p->data);void Preorder(BiTree T) /*前序遍历*/if (T != NULL) visit(T); /访问根节点Preorder(T->lchild); /访问左子节点Preorder(T->rchild); /访问右子节点void Inorder(BiTree T) /*中序遍历*/if (T != NULL) Inorder(T->lchild); /访问左子节点visit(T); /访问根节点Inorder(T->rchild); /访问右子节点void Postorder(BiTree T) /*后序遍历*/if (T != NULL) Postorder(T->lchild); /访问左子节点Postorder(T->rchild); /访问右子节点visit(T); /访问根节点BiTree CreateTree() /*以前序遍历的顺序建立二叉树*/char ch;BiTree T;if (ch = getchar() = '#') /*#表示空树*/return NULL;else T = (BiTree)malloc(sizeof(BiTNode); /生成根节点T->data = ch;T->lchild = CreateTree(); /构造左子树T->rchild = CreateTree(); /构造右子树return T;int deep(BiTree T) /*求二叉树深度*/int lh, rh;if (T = NULL) return 0;else lh = deep(T->lchild);rh = deep(T->rchild);return (lh > rh ? lh : rh) + 1;int leaf(BiTree T) /*求叶子结点数*/int m, n;if (!T) /*空树没有叶子*/return 0;else if (!T->lchild && !T->rchild) /*叶子结点*/return 1;else /*左子树的结点数加上右子树的结点数*/m = leaf(T->lchild);n = leaf(T->rchild);return m + n;int OneChild(BiTree T) /*求1度结点数*/int n = 0;if (T = NULL) return 0;else if (T->lchild = NULL&&T->rchild != NULL) | (T->lchild != NULL&&T->rchild = NULL) n = 1;return OneChild(T->lchild) + OneChild(T->rchild) + n;int TwoChild(BiTree T) /*求2度结点数*/int n = 0;if (T = NULL) return 0;else if (T->lchild != NULL&&T->rchild != NULL)n = 1;return TwoChild(T->lchild) + TwoChild(T->rchild) + n;void Exchange(BiTree T) /*二叉树左右子树交换*/BiTree temp;if (T) temp = T->lchild;T->lchild = T->rchild;T->rchild = temp;Exchange(T->lchild);Exchange(T->rchild);BiTree InorderLastNode(BiTree T) /*找二叉树中序遍历最后一个结点*/if(T)while (T->rchild)T = T->rchild;return T;int main() BiTree T;printf("以前序遍历的二叉树:");T = CreateTree();printf("n先序遍历:");Preorder(T);printf("n");printf("n中序遍历:");Inorder(T);printf("n");printf("n后序遍历:");Postorder(T);printf("n");printf("n树的深度=%dn", deep(T);printf("叶子结点数=%dn", leaf(T);printf("1度结点数=%dn", OneChild(T);printf("2度结点数=%dn", TwoChild(T);printf("n二叉树中序遍历最后一个结点为:%c", InorderLastNode(T)->data);printf("n");printf("n交换后的二叉树先序遍历为:");Exchange(T); Preorder(T);printf("n交换后的二叉树中序遍历为:");Inorder(T);printf("n交换后的二叉树后序遍历为:");Postorder(T);printf("n");printf("n交换后的二叉树中序遍历最后一个结点为:%c", InorderLastNode(T)->data);printf("n");return 0;4程序执行后屏幕上的输入输出内容       A      /     B    /    C   D      /      E   F             G实验总结分析（本程序的重点与难点，调试中出现的问题及解决方法等）-第 7 页-