数据结构实验三邵彬彬

1、实验三叉二叉树一、实验目的1.掌握二叉树的链式存储结构及相关操作的实现。2.掌握二叉树首、中、末顺序的递归遍历算法。3.了解二叉树各种非递归遍历算法的实现。二、实验要求1.实验前做好充分的准备，包括复习第六章的内容和预习实验内容。2.在实验过程中记录实验结果，并按要求完成所有问题。3.实验结束后，对实验进行总结和分析，并及时给出实验报告。第三，实验课题下表显示了本实验中选定的主题。实验名称学习当.的时候实验内容实验要求实验类型二叉树4(1)二叉树的创建、递归遍历和其他基本操作的实现。必须做结构性(2)二叉树非递归遍历算法的实现。选择成为结构性(3)哈夫曼树和哈夫曼编码算法的实现。选择成为全面的

2、描述：(1)实验内容1)是必需的。(2)实验内容2)和实验内容3)为选修内容。四.实验内容和要求1.实验主题1: (1)二叉树的创建、递归遍历和其他基本操作的实现。要求：定义以二叉链表表示的二叉树，实现二叉树的创建、遍历的递归算法(一阶、中间阶、再阶)和查找深度的操作，并验证。2.实验主题2:二叉树非递归遍历算法的实现要求：在第一个主题的基础上，实现二叉树的非递归遍历算法(一阶、中阶、末阶或逐层)并验证。3.实验主题3:哈夫曼树和哈夫曼编码的算法实现要求：通过编程创建哈夫曼树，并使用哈夫曼树解决哈夫曼编码。5.实验步骤源代码：#包括#包括使用命名空间标准；模板结构二叉树节点/二叉树节点类定义测

3、试数据；/数据字段BinTreeNode *leftChild，* rightChild/左子和右子字段二叉树节点(T x=T()，二叉树节点* l=空，二叉树节点* r=空):data (x)、leftchild (l)、right child(r) /可选参数的默认构造函数；/-模板Void preorder _ 2(二叉树节点* p)/非递归preorder遍历堆栈* S；同时(p！=空|！空()同时(p！=空)coutdata/访问根节点S.push(p)。p=p-LeftChild；/将指针移动到左边的子节点如果(！S.empty() /当堆栈不为空时撤退p=最高()；s . pop

4、()；p=p-RightChild；/将指针移动到右边的子节点/-模板order _ 2中为空(bin树节点* p)/非递归中间顺序遍历堆栈* S；做同时(p！=空)/遍历指针没有到达最左边的节点，该节点不是空的S.push(p)。p=p-LeftChild；如果(！S.empty() /当堆栈不为空时撤退p=最高()；s . pop()；coutdatap=p-RightChild；同时(p！=空|！s . empty()；/-模板Voidpost _ 2(二叉树节点* p)/非递归后向遍历堆栈* S；堆栈标记；/定义一个新堆栈来保存标签字段，以判断根节点的左右子树是否已经遍历。同时(p！=

5、空|！/左边的子树通过节点加上左同时(p！=空)S.push(p)。/首先将t和标记放入堆栈，并遍历左边的子树tag . push(0)；/遍历左子树前的字段保护p=p-LeftChild；同时(！S.empty()标记. top()=1)p=最高()；s . pop()；tag . pop()；coutdata/最后访问根节点。如果(！空()tag . pop()；tag . push(1)；/遍历右子树之前的字段保护，将堆栈顶部的标记更改为1，并遍历右子树。p=最高()；/获取保存在堆栈顶部的指针p=p-RightChild；其他休息；/-模板void InOrder_1(二叉树节点*子树

6、)/递归函数：遍历以子树为根的中间顺序的子树。if(subTree！=空)/空是递归终止条件InOrder _ 1(SubLed-LeftChild)；/中序遍历根的左子树coutdata/访问根结点InOrder_1(子树-右子树)；/中序遍历根的右子树/-模板void PreOrder _ 1(BinTreeNode * SubTree)/递归函数：前序遍历以子树为根的二叉树。if(subTree！=空)/递归结束条件coutdata/访问根结点PreOrder _ 1(SuBtree-LeftChild)；/前序遍历根的左子树预订_1(子树-右子树)；/前序遍历根的右子树/-模板void

7、 PostOrder _ 1(BinTreeNode * SubTree)/递归函数：后序次序遍历以子树为根的子树。if(subTree！=空)/空是递归终止条件postOrder _ 1(SuBtree-LeftChild)；/后序遍历根的左子树邮购_1(子树-右子树)；/后序遍历根的右子树coutdata/访问根结点/-模板void CreateBinTree(BinTreeNode * SubTree)/递归方式建立二叉树t项；cinitem如果(项目！=-1)子树=新建binTreeNode()；if(subTree=空)cerr 存储分配错！数据=项目；创建二叉树(SuBtree-LeftChild)；/递归建立左子树创建二叉树（子树-右