二叉树

重庆科技学院学生实验 课程名称 算法与数据结构 实验项目名称 二叉树的遍历 开课院系及 数理学院，数理学院实验室 实验日期 2010-10-8 学生姓名 陈艳良 学号 2008441947 专业班级 应数普081 指导教师 陈小强 实验成绩 教师评语： 教师签字： 批改时间： 一、实验目的和要求 1、熟练掌握二叉树在二叉链表存储结构中的常用遍历方法：先序递归遍历、中序递归遍历、后序递归遍历和按层遍历。 二、实现内容 1、单链表的C++实现 1)．问描述 根据教材采用C++语言实现二叉树的遍历（泛型实现） 2)．实现功能 1、用二叉链表作为存储结构，建立一棵二叉树。 2、分别用三种递归方法遍历二叉树：先序、中序和后序，输出各遍历序列。 3)．试验 根据二叉树的C++类（已完成声明和方法的部分实现）范例编辑源程序，注意编写的规范和体会二叉树类的声明方式；实现先序递归遍历、中序递归遍历、后序递归遍历及按层遍历二叉树的方法；在测试过程中使用各种方法遍历二叉树，输出结果 4). 程序实现 // file binarytree.h #ifndef binarytree _ #define binarytree _ #include "xcept.h" #include "lqueue.h" #include "xcept.h" #include using namespace std; template class BinaryTree; template class BinaryTreeNode { friend BinaryTree; private: T data; BinaryTreeNode *LeftChild, // left subtree *RightChild; // right subtree }; template class BinaryTree { public: BinaryTree(); ~BinaryTree(); bool IsEmpty() const; bool Root(T& x) const; void SetNull(); void MakeTree(const T& element, BinaryTree& left, BinaryTree& right); void PreOrder(void(*Visit)(BinaryTreeNode *u)); //传函数作为参数 void InOrder(void(*Visit)(BinaryTreeNode *u)); void PostOrder(void(*Visit)(BinaryTreeNode *u)); void LevelOrder(void(*Visit)(BinaryTreeNode *u)); void PreOutput(); void InOutput(); void PostOutput(); void LevelOutput(); int Height() const; private: BinaryTreeNode *root; // pointer to root void PreOrder(void(*Visit) (BinaryTreeNode *u), BinaryTreeNode *t); void InOrder(void(*Visit) (BinaryTreeNode *u), BinaryTreeNode *t); void PostOrder(void(*Visit) (BinaryTreeNode *u), BinaryTreeNode *t); int Height(BinaryTreeNode *t) const; static void Free(BinaryTreeNode *t) ; static void Output(BinaryTreeNode *t); }; template BinaryTree::BinaryTree() { // Link constructor. Init head nodes in chain. root = NULL; } template BinaryTree::~BinaryTree() {// Link destructor. Delete all nodes in chain. SetNull(); } template void BinaryTree::SetNull() {// Return the number of elements in the chain. PostOrder(Free, root); root = NULL; } template bool BinaryTree::IsEmpty() const {//Is Empty return (root == NULL); } template bool BinaryTree::Root(T& x) const {// Return root data in x. // Return false if no root. if (root==NULL) { return false; // no root } else { x = root->data; return true; } } template void BinaryTree::MakeTree(const T& element, BinaryTree& left, BinaryTree& right) {// Combine left, right, and element to make new tree. // left, right, and this must be different trees. // create combined tree root = new BinaryTreeNode(); root->data = element; root->LeftChild = left.root; root->RightChild = right.root; // deny access from trees left and right left.root = right.root = NULL; } template void BinaryTree::PreOrder( void(*Visit)(BinaryTreeNode *u)) {//public Preorder traversal. PreOrder(Visit, root); } template void BinaryTree::InOrder( void(*Visit)(BinaryTreeNode *u)) {//public Inorder traversal. InOrder(Visit, root); } template void BinaryTree::PostOrder( void(*Visit)(BinaryTreeNode *u)) {//public Postorder traversal. PostOrder(Visit, root); } template void BinaryTree::LevelOrder( void(*Visit)(BinaryTreeNode *u)) {// Level-order traversal.To do exercise... //可利用已实现的LinkedQueue队列类（lqueue.h） LinkedQueue*> Q; BinaryTreeNode *t; t = root; while (t!=NULL) { Visit(t); //传Output()参数，输出结点的data if (t->LeftChild) { Q.Add(t->LeftChild); } if (t->RightChild) { Q.Add(t->RightChild); } try { Q.Delete(t); //t存放删除是列对的头结点 } catch (OutOfBounds) { return; } } } template void BinaryTree::PreOutput() { PreOrder(Output, root); cout << endl; } template void BinaryTree::InOutput() { InOrder(Output, root); cout << endl; } template void BinaryTree::PostOutput() { PostOrder(Output, root); cout << endl; } template void BinaryTree::LevelOutput() { LevelOrder(Output); cout << endl; } template int BinaryTree::Height() const { return Height(root); } //private part template void BinaryTree::PreOrder( void(*Visit)(BinaryTreeNode *u), BinaryTreeNode *t) {// Preorder traversal.To do exercise... if (t!=NULL) { Visit(t); PreOrder(Visit, t->LeftChild); PreOrder(Visit, t->RightChild); } } template void BinaryTree::InOrder( void(*Visit)(BinaryTreeNode *u), BinaryTreeNode *t) {// Inorder traversal.To do exercise... if (t!=NULL) { InOrder(Visit, t->LeftChild); Visit(t); InOrder(Visit, t->RightChild); } } template void BinaryTree::PostOrder( void(*Visit)(BinaryTreeNode *u), BinaryTreeNode *t) {// Postorder traversal.To do exercise... if (t!=NULL) { PostOrder(Visit, t->LeftChild); PostOrder(Visit, t->RightChild); Visit(t); } } template int BinaryTree::Height(BinaryTreeNode *t) const {// Return height of tree *t. if (t==NULL) return 0; // empty tree int hl = Height(t->LeftChild); // height of left int hr = Height(t->RightChild); // height of right if (hl > hr) { return ++hl; } else { return ++hr; } } template void BinaryTree::Free(BinaryTreeNode *t) { delete t; } template void BinaryTree::Output(BinaryTreeNode *t) { cout << t->data << ' '; } #endif //list.cpp // test formula based linear list class #include " binarytree.h " #include "xcept.h" #include "lqueue.h" #include "xcept.h" #include using namespace std; void main(void) { BinaryTree T,a,x,y,z; try { y.MakeTree(1,a,a); z.MakeTree(2,a,a); x.MakeTree(3,y,z); T.MakeTree(4,x,a); cout << "InOrder output is " << endl; T.InOutput(); cout << "Level Order output is " << endl; T.LevelOutput(); } catch (...) { cerr << "An exception has occurred" << endl; } } 三、实验记录 请记录： 1. 调试是否顺利，如不顺利，主要问题出在哪里？ 本次调试十分顺利。 2.输入的相关数据以及实验的最终结果。 由1、2、3、4构造的树的中序遍历为：1 3 2 4 由1、2、3、4构造的树的中序非递归遍历为：4 3 1 2 3.

心得体会

决胜全面小康心得体会学党史心得下载党史学习心得下载军训心得免费下载党史学习心得下载

通过本次试验，我对二叉树的创建有了一定的了解，并且能够运用先序、先序、中序和后序以及非递归遍历二叉树。对二叉树的构造和遍历有了本质的了解和提高。通过学习，明白了树有很多优良的性质。因此构造二叉树是具有实际价值和现实意义的。