二叉树的基本操作.doc

计科112 姓名 学号一、实验目的：1、使学生熟练掌握二叉树的逻辑结构和存储结构。2、熟练掌握二叉树的各种遍历算法。二、实验内容：建立一棵二叉树，试编程实现二叉树的如下基本操作：1. 按先序序列构造一棵二叉链表表示的二叉树T；2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；3. 求二叉树的深度/结点数目/叶结点数目；(选做)4. 将二叉树每个结点的左右子树交换位置。（选做）三：实验要求：从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）四、算法设计分析：整个的过程全是递归：1、 创建一个链表：按照先序创建2、 先序遍历：3、 中序遍历：4、 后续遍历：二叉树的基本操作的算法1、先序建立一个二叉树：Bitree Create（BiTree &T）2层次遍历二叉树T：void LevleOrder（Bitree&T）用一维数组来表示队列，front和rear分别表示队首和队尾指针Front=rear=0，若树非空，则根节点入队queuerear+=T队首元素出列，并访问这个节点b=queuefront+左右子树若非空，则次入队列3先序遍历二叉树T： void Preorder(BiTree T)；printf(%c,T-data);Preorder(T-lchild); Preorder(T-rchild);4中序遍历二叉树T： void inorder(BiTree T) inorder(T-lchild); printf(%c,T-data); inorder(T-rchild);5后序遍历二叉树T： void postorder(BiTree T) postorder(T-lchild); postorder(T-rchild); printf(%c,T-data);二、程序代码如下：#include stdio.h #include string.h #includeusing namespace std;typedef struct BiTNode char data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; BiTree Create(BiTree &T) char ch; ch=getchar(); if(ch= ) T=NULL; else T=new BiTNode; if(!T) exit(1);T-data=ch; T-lchild=Create(T-lchild); T-rchild=Create(T-rchild); return T; void levleOrder(BiTree &T)BiTree Queue100,b; int front,rear; front=rear=0; if (T) Queuerear+=T; while (front!=rear) b=Queuefront+; printf(%c,b-data); if (b-lchild!=NULL) Queuerear+=b-lchild; if (b-rchild!=NULL) Queuerear+=b-rchild; void Preorder(BiTree T) if(T) printf(%c,T-data); Preorder(T-lchild); Preorder(T-rchild); void inorder(BiTree T) if(T) inorder(T-lchild); printf(%c,T-data); inorder(T-rchild); void postorder(BiTree T) if(T) postorder(T-lchild); postorder(T-rchild); printf(%c,T-data); void main() BiTree T; printf(先序建立二叉树:); T=Create(T);printf(先序遍历:); Preorder(T);printf(n); printf(中序遍历:);inorder(T); printf(n); printf(后序遍历:); postorder(T);printf(n); printf(层