二叉树及其应用

《二叉树及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验3二叉树及其应用一、实验目的1.加深对二叉树结构的理解；2.熟练掌握二叉树的存储结构，特别是二叉链表类的描述及其实现方法；3.掌握二叉树的遍历算法原理和实现方法；4.学会编写对二叉树的各种操作算法；5.掌握二叉树结构的应用。二、实验学时：建议2~4学时三、实验内容内容1二叉树及其操作1问题描述以二叉链表结构存储二叉树，操作主要有创建二叉链表二叉树、遍历二叉树、统计该二叉树中的结点个数等。2数据结构设计根据问题要求，二叉树采用二叉链表结构存储。（1）二叉链表结点结构定义templatestructbtNode//二叉链表结点结构{Tdata;//二叉树中的元素btNo

2、de*lchild,*rchild;btNode():lchild(NULL),rchild(NULL){}//构造函数btNode(Te,btNode*l=NULL,btNode*r=NULL):data(e),lchild(l),rchild(r){}};（2）二叉链表类设计二叉树的二叉链表类的数据成员主要有指向根结点的根指针，其成员函数有构造、创建、遍历、统计结点个数、销毁等操作。templateclassbinaryTree//二叉树的二叉链表类{private:btNode*root;//二叉树的根指针TrefValue;//二叉树结点

3、为空标记voidcreate(btNode*&r);//先序创建二叉链表结构二叉树rvoidpreOrder(btNode*r);//先序遍历二叉树rvoidinOrder(btNode*r);//中序遍历二叉树rvoidpostOrder(btNode*r);//后序遍历二叉树rintnumOfNode(btNode*r);//统计二叉树r中的结点个数public:binaryTree():root(NULL){}//构造函数binaryTree(Tvalue):refValue(value),root(NULL){}//构造函数voidcreate()

4、;//先序创建二叉链表结构二叉树voidsetRefValue(TrValue):refValue(rValue){}//设置结点为空标记voidpreOrder(){preOrder(root);}//先序遍历二叉树voidinOrder(){inOrder(root);}//中序遍历二叉树voidpostOrder(){postOrder(root);}//后序遍历二叉树voidlevelOrder();//二叉树的层次遍历intnumOfNode();//统计二叉树中的结点个数};3算法设计与实现（1）二叉树创建算法可以采用先序序列方式创建二叉树的二叉链表结构。a)创建原理：对二

5、叉树（如图4.1所示）中的所有空子树添加空标记（假设为'#'。）后如图4.2所示，此时的二叉树的扩展先序遍历序列为AB#C##DE##F##,按照此序列次序来先序创建二叉树的二叉链表结构，即先创建根结点，再创建根的左子树，最后创建根的右子树。b)算法步骤：①读入根信息data；②若根信息data=='#'则返回空二叉树，否则：③创建根结点；④创建根的左子树；⑤创建根的右子树；⑥返回二叉树。c)实现：（2）先序遍历二叉树算法（3）中序遍历二叉树算法（4）后序遍历二叉树算法（5）二叉树的层次遍历算法（1）统计二叉树的结点总数a)原理：根据二叉树构成上的特点，任何一棵非空的二叉树都是由根结点

6、、左子树、右子树构成，因此有：二叉树的结点总数=1+左子树结点总数+右子树结点总数。b)算法步骤：①若二叉树为空，则返回结点总数为0，否则：②统计左子树结点总数k1；③统计右子树结点总数k2；④返回二叉树结点总数1+k1+k2。c)实现：4测试（1）测试代码voidmain(){charnullFlag='#';binaryTreebTree(nullFlag);bTree.create();cout<

7、二叉树cout<