山东大学数据结构实验报告六

1、山东大学 软件工程 学院 数据结构 课程实验报告学号：姓名： 班级： 软件工程2014级2班实验题目：二叉树操作实验学时：实验日期： 2015.11.25实验目的：掌握二叉树的基本概念，链表描述方法；遍历方法。硬件环境：实验室软件环境：Vistual Studio 2013 实验步骤与内容：实验内容：1、 创建二叉树类。二叉树的存储结构使用链表。2、 提供操作:前序遍历、中序遍历、后序遍历、层次遍历、计算二叉树结点数目、计算二叉树高度。3、 对建立好的二叉树，执行上述各操作。4、 接收键盘录入的二叉树前序序列和中序序列(各元素各不相同)，输出该二叉树的后序序列。代码体：binarytreeno

2、de.h#ifndef BINARYTREENODE_H#define BINARYTREENODE_Hclass BinaryTreeNodefriend class BinaryTree;public:BinaryTreeNode() LeftChild = RightChild = 0; BinaryTreeNode(const int& e) data = e; LeftChild = RightChild = 0; BinaryTreeNode(const int& e, BinaryTreeNode *l, BinaryTreeNode *r) data = e; LeftChil

3、d = l; RightChild = r; private:BinaryTreeNode *LeftChild, *RightChild;int data;#endifbinarytree.h#ifndef BINARYTREE_H#define BINARYTREE_H#includeusing namespace std;#include binarytreenode.hclass BinaryTreepublic:BinaryTree() root = 0; num = 0; bool IsEmpty() return root = 0; bool Root(int &x);void

4、MakeTree(const int& element, BinaryTree& left, BinaryTree& right);void BreakTree(int& element, BinaryTree& left, BinaryTree& right);int Height() const return Height(root); int NumNode() num = 1; NumNode(root); return num; void PreOrder() PreOrder(root); cout endl; void InOrder() InOrder(root); cout

5、endl; void PostOrder() PostOrder(root); cout endl; void LevelOrder() LevelOrder(root); cout root = root; root = 0; private:void Visit(BinaryTreeNode*);int Height(BinaryTreeNode*) const;void NumNode(BinaryTreeNode*);void PreOrder(BinaryTreeNode*);void InOrder(BinaryTreeNode*);void PostOrder(BinaryTre

6、eNode*);void LevelOrder(BinaryTreeNode*);BinaryTreeNode *root;int num;#endifbinarytree.cpp#include#include#includeusing namespace std;#include binarytree.hvoid BinaryTree:Visit(BinaryTreeNode *t)cout data ;void BinaryTree:PreOrder(BinaryTreeNode* t)stack s;while (t)Visit(t);if (t-RightChild) s.push(

7、t-RightChild);if (t-LeftChild) s.push(t-LeftChild);if (s.empty()return;elset = s.top();s.pop();void BinaryTree:InOrder(BinaryTreeNode* t)stack s;BinaryTreeNode *pre = NULL;while (t)if (t-LeftChild)if (pre = t-LeftChild)Visit(t);pre = t;if (s.empty()return;elset = s.top();s.pop();else if (t-LeftChild

8、-RightChild)BinaryTreeNode *d = t-LeftChild-RightChild;while (d-RightChild)d = d-RightChild;if (pre = d)Visit(t);pre = t;if (s.empty()return;elset = s.top();s.pop();elseif (t-RightChild) s.push(t-RightChild);s.push(t);t = t-LeftChild;elseif (t-RightChild) s.push(t-RightChild);s.push(t);t = t-LeftChi

9、ld;else if (t-RightChild)Visit(t);pre = t;t = t-RightChild;elseVisit(t);pre = t;if (s.empty()return;elset = s.top();s.pop();void BinaryTree:PostOrder(BinaryTreeNode* t)stack s;BinaryTreeNode *pre = NULL;while (t)if (t-RightChild)if (pre = t-RightChild)Visit(t);pre = t;if (s.empty()return;elset = s.t

10、op();s.pop();elseif (t-LeftChild)s.push(t);s.push(t-RightChild);t = t-LeftChild;elses.push(t);t = t-RightChild;else if (t-LeftChild)if (pre = t-LeftChild)Visit(t);pre = t;if (s.empty()return;elset = s.top();s.pop();elses.push(t);t = t-LeftChild;elseVisit(t);pre = t;if (s.empty()return;elset = s.top(

11、);s.pop();void BinaryTree:LevelOrder(BinaryTreeNode* t)queue q;while (t)Visit(t);if (t-LeftChild) q.push(t-LeftChild);if (t-RightChild) q.push(t-RightChild);if (q.empty()return;elset = q.front();q.pop();bool BinaryTree:Root(int &x)if (root)x = root-data;return true;else return false;void BinaryTree:

12、MakeTree(const int& element, BinaryTree& left, BinaryTree& right)root = new BinaryTreeNode(element, left.root, right.root);left.root = right.root = 0;void BinaryTree:BreakTree(int& element, BinaryTree& left, BinaryTree& right)if (!root)cout 该树是空树 data;left.root = root-LeftChild;right.root = root-Rig

13、htChild;delete root;root = 0;int BinaryTree:Height(BinaryTreeNode *t) constif (!t) return 0;int hl = Height(t-LeftChild);int hr = Height(t-RightChild);if (hl hr) return +hl;else return +hr;void BinaryTree:NumNode(BinaryTreeNode *t)queue q;while (t)if (t-LeftChild)q.push(t-LeftChild);num+;if (t-Right

14、Child) q.push(t-RightChild);num+;if (q.empty()return;elset = q.front();q.pop();test.cpp#includeusing namespace std;#include binarytree.h/* 9 / 8 7 / 6 5 4 / / 3 2 1 0*/void ThePostOrder(const int *pre, const int *in, int *post, int n);int main()BinaryTree *bt = new BinaryTree();BinaryTree *l = new B

15、inaryTree();BinaryTree *r = new BinaryTree();bt-MakeTree(0, *l, *r);bt-Transfer(r);bt-MakeTree(1, *l, *l);bt-Transfer(l);bt-MakeTree(4, *l, *r);bt-Transfer(r);bt-MakeTree(7, *l, *r);BinaryTree *b1 = new BinaryTree();b1-MakeTree(2, *l, *r);b1-Transfer(l);b1-MakeTree(5, *l, *r);BinaryTree *b2 = new Bi

16、naryTree();b2-MakeTree(3, *l, *r);b2-Transfer(r);b2-MakeTree(6, *l, *r);b1-Transfer(r);b2-Transfer(l);b1-MakeTree(8, *l, *r);b1-Transfer(l);bt-Transfer(r);bt-MakeTree(9, *l, *r);delete b1;delete b2;delete l;delete r;b1 = NULL;b2 = NULL;l = NULL;r = NULL;cout 下面是逐层遍历: LevelOrder();cout 下面是前序遍历: PreOr

17、der();cout 下面是中序遍历: InOrder();cout 下面是后序遍历: PostOrder();cout 下面是计算二叉树结点数目: endl;cout NumNode() endl;cout 下面是计算二叉树高度: endl;cout Height() endl;delete bt;bt = NULL;int *pre, *in, *post, a;cout a;pre = new inta;cout 请输入前序遍历的结果: endl;for (int i = 0; i prei;in = new inta;cout 请输入中序遍历的结果: endl;for (int i =

18、 0; i ini;post = new inta;ThePostOrder(pre, in, post, a);cout 后序遍历的结果: endl;for (int i = 0; i a; i+)cout posti ;cout endl;delete pre;delete in;delete post;pre = NULL;in = NULL;post = NULL;system(pause);return 0;int find(const int *p, const int x, int n)for (int i = 0; i n; i+)if (pi = x)return i;cout 前序和中序不符! 1 & j 2)ThePostOrder(pre + 1), in, post, j);ThePostOrder(pre + j + 1), (in + j + 1), (post + j), n - j - 1);else if (j = n - 1 & n 2)ThePostOrder(pre + 1), in, post, j);else if (j = n - 2 & n 2)ThePostOrder(pre + 1), in, post, j);postn - 2 = pren - 1;else if (j = 1 & n 2)post0