试验题目.doc

实验题目： 二叉树的基本运算 需求分析 建立一棵二叉树，编程实现二叉树的如下基本操作：按先序序列构造一棵二叉链表表示的二叉树T；对这棵二叉树进行遍历：先序、中序、后序以及层次遍历序列，分别输出结点的遍历序列；先序、中序、后序输出结点的遍历序列从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。ABC@DE@G@@F@@@　　 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA CreateBiTree() 先序遍历函数BiTree PreOrderTraverse(BiTree T) 中序遍历函数BiTree InOrderTraverse(BiTree T) 后序遍历函数BiTree PostOrderTraverse(BiTree T) 函数有如下关系： 调试分析 调试过程中遇到的问题是如何解决的： 在建立二叉树时出了问题，因为是按照书上说的用空格来代替空树，但是在我调试程序中，如果输入空格，程序会出现错误，起初不知道是什么原因程序老是不能正常运行，后来进行单步调试，发现是因为空格的问题，后来我改为用@，就可以运行结果了，但是至今我还是不大清楚为什么用空格不行，因为空格和@同样都是字符形式。 对设计与实现的回顾讨论和分析： 要对树进行操作首先要建立一个二叉树，规定是按先序序列来建立，先访问根结点，再先序遍历左子树，后先序遍历右子树；后按要求建立三个函数，分别按先序、中序、后序—————————————————— 按照上述提示输入用户所要创建的树即可。 ABC@@DE@G@@F@@@ 先序遍历的结果是:ABCDEGF 中序遍历的结果是:CBEGDFA 后序遍历的结果是:CGEFDBA 程序运行结束! Press any key to continue 附录 #includeiostream.h #includemalloc.h typedef struct BiTNode//定义树的结点 { char data; struct BiTNode *lchild,*rchild; }BiTNode, *BiTree; BiTNode *CreateBiTree()//先序遍历建立二叉树，此为函数的定义返回一个BiTNode结构类型的指针 { struct BiTNode *T; char ch; cinch; if(ch==@) T=NULL; else { if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) coutfalseendl; T-data=ch; T-lchild=CreateBiTree(); T-rchild=CreateBiTree(); } return T; } BiTree PreOrderTraverse(BiTree T)//先序遍历 { if(T==NULL) return T; else { coutT-data; PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); } return T; } BiTree InOrderTraverse(BiTree T)//中序遍历 { if(T==NULL) return T; else { InOrderTraverse(T-lchild); coutT-data; InOrderTraverse(T-rchild); } return T; } BiTree PostOrderTraverse(BiTree T)//后序遍历 { if(T==NULL) return T; else { PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); coutT-data; } return T; } void main()//main函数 { struct BiTNode *T; cout********** 实验三 二叉树的基本运算 ************endl; cout********** 计科041 梁爽 *************endl; cout程序开始运行:endl; cout请按先序序列输入要创建的树:endl; T=CreateBiTree(); cout先序遍历的结果是:; PreOrderTraverse(T); coutendl; coutendl中序遍历的结果是: