《二叉树的建立与遍历.docx》由会员分享,可在线阅读,更多相关《二叉树的建立与遍历.docx(8页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、重庆高校本科同学课程设计任务书课程设计题目二叉树的建立与遍历学院软件学院专业软件工程班级09级问题描述:建立一棵二叉树,并对其进行遍历(先序、中序、后序),打印输出遍历结果。基本要求:从键盘接受输入(先序),以二叉链表作为存储结构,建立二叉树(以先序来建立), 并采纳递归算法对其进行遍历(先序、中序、后序),将遍历结果打印输出。算法思想:从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分 组成。因此,在任一给定结点上,可以按某种次序执行三个操作:(1)访问结点本身(N)(2)遍历该结点的左子树(L)(3)遍历该结点的右子树(R)以上三种操作有六种执行次序:NLR、LNR
2、、LRN、NRL、RNL、RLN。前三种次序与后 三种次序对称,故只争论先左后右的前三种次序。中序遍历的递归算法定义:若二叉树非空,则依次执行如下操作:遍历左子树、访问 根结点、遍历右子树。前序遍历的递归算法定义:若二叉树非空,则依次执行如下操作: 访问根结点、遍历左子树、遍历右子树。后序遍历得递归算法定义:若二叉树非空,则依 次执行如下操作:遍历左子树、遍历右子树、访问根结点。模块划分:1 .建立二叉树 tree *CreatBitree()2 .基本运算void push(stacktop,tree *tree) 树结点入栈void pop(stack *top,tree *T)/出栈,栈
3、内元素赋值void getTop(stack*s,tree *t)/猎取栈顶元素3 .递归遍历函数void PreOrder(tree *bl)/前序遍历函数void MidOrder(tree *b2)中序遍历函数void LastOrder(tree *b3)后序遍历函数数据结构:给出所使用的基本抽象数据类型,所定义的详细问题的数据类型, 以及新定义的抽象数据类型。源程序: cppl.cpp typedef char Entry;template struct Binary_node / data members:Entry data;Binary_node *left;B inary_n
4、ode *right;/ constructors:Binary _node();Binary_node(const Entry &x););template class Binary_tree public:Binary_tree();bool empty() const;void preorder(void (*visit)(Entry &);void inorder(void (*visit)(Entry &);void postorder(void (*visit)(Entry &);int size() const;void clear();int height() const;vo
5、id insert(const Entry &);Binary_tree (const Binary_tree &original);Binary_tree & operator =(const Binary_tree &original);-Binary _tree();protected:/ Add auxiliary function prototypes here.Binary_node *root;int recursive height(Binary node *sub root) const;void recursive_insert(Binary_node * &sub_roo
6、t,const Entry &x);void recursive_postorder(Binary_node *sub_root, void (*visit)(Entry &);void recursive_preorder(Binary_node sub_root,void (*visit)(Entry &);void recursive_inorder(Binary_node *sub_root,void (*visit)(Entry &);void recursive_clear(Binary_node * &sub_root);Binary_node * recursive_copy(
7、Binary_node *sub_root););cpp2.cpp#includencppl.cppn#includeusing namespace std;template int Binary_tree : height() const/* Post: The height of the binary tree is returned. */ (return recursive_height(root);template int Binary_tree:recursive_height(Binary_node *sub_root) const /* Post: The height of
8、the subtree rooted at sub_root is returned. */ if(sub_root=0)return 0;int L=recursive_height(sub_root-left);int R=recursive_height(sub_root-right);if(LR)return 1+L;elsereturn 1+R;templateBinary_node:Binary_node(const Entry &x) (data=x;left=0;right=0;template void Binary_tree:insert(const Entry &x)/*
9、 Post: The Entry x is added to the binary tree. */ (recursive_insert(root, x);)template void Binary_tree :recursive_insert(Binary_node * &sub_root,const Entry &x) /* Pre: sub_root is either NULL or points to a subtree of the Binary_tree.Post: The Entry x has been inserted into the subtree in such a
10、way that the properties of a binary search tree have been preserved.Uses: The functions recursive_insert, recursive_height */ (if (sub_root=0)sub_root=new B inary_node(x); elseif (recursive_height(sub_root-right)left) recursive_insert(sub_root-right, x);else recursive_insert(sub_root-left, x);)templ
11、ate B inary_tree: Binary _tree()/*Post: An empty binary tree has been created.*/(root=0;)template bool Binary_tree:empty() const/*Post: A result of true is returned if the binary tree is empty. Otherwise, false is returned.*/(return root=0;template void Binary_tree:inorder(void (*visit)(Entry &)/*Po
12、st: The tree has been traversed in inorder sequence.Uses: The function recursive_inorder*/(recursive_inorder(root, visit);)template void Binary_tree:recursive_inorder(Binary_node *sub_root, void (*visit)(Entry &)/*Pre: sub_root is either NULL or points to a subtree of the Binary_tree.Post: The subtr
13、ee has been traversed in inorder sequence.Uses: The function recursive_inorder recursively*/(if (sub_root != 0) recursive_inorder(sub_root-left, visit);(*visit)(sub_root-data);recursive_inorder(sub_root-right, visit);)template void Binary_tree:preorder(void (*visit)(Entry &)/*Post: The tree has been
14、 traversed in inorder sequence.Uses: The function recursive_inorder*/(recursive_preorder(root, visit);template void Binary_tree:recursive_preorder(Binary_node *sub_root, void (*visit)(Entry &)/*Pre: sub_root is either NULL or points to a subtree of the Binary_tree.Post: The subtree has been traverse
15、d in preorder sequence.Uses: The function recursive_preorder recursively*/if (sub_root != 0) (*visit)(sub_root-data);recursive_preorder(sub_root-left, visit);recursive_preorder(sub_root-right, visit);)template void Binary_tree:postorder(void (*visit)(Entry &)/*Post: The tree has been traversed in in
16、order sequence.Uses: The function recursive_inorder*/(recursive_postorder(root, visit);)template void Binary_tree:recursive_postorder(Binary_node sub_root, void (*visit)(Entry &)/*Pre: sub_root is either NULL or points to a subtree of the Binary_tree.Post: The subtree has been traversed in postorder
17、 sequence.Uses: The function recursive_postorder recursively*/(if (sub_root != 0) recursive_postorder(sub_root-left, visit);recursive_postorder(sub_root-right, visit);(*visit)(sub_root-data);)template void Binary_tree:recursive_clear(Binary_node * &sub_root) /* Post: The subtree rooted at sub_root i
18、s cleared. */ (Binary_node *temp 二 sub_root;if (sub root =0) return;recursive_clear(sub_root-left);recursive_clear(sub_root-right);sub_root =0;delete temp;template void Binary_tree:clear()/* Post: All entries of the binary tree are removed. */(recursive_clear(root);)template Binary_tree :Binary_tree
19、()/* Post: All entries of the binary tree are removed. All dynamically allocated memory in the structure is deleted. */ ( clear();template Binary_tree : Binary_tree (const Binary_tree &original)/* Post: A new binary tree is initialized to copy original. */ root = recursi ve_copy (original.root);)tem
20、plate Binary_node *Binary_tree : recursive_copy(B inary_node *sub_root)/* Post: The subtree rooted at sub_root is copied, and a pointer to the root of the new copy is returned. */ (if (sub_root = 0) return 0;Binary_node *temp = new Binary_node(sub_root-data);temp-left = recursive_copy(sub_root-left)
21、;temp-right = recursive_copy(sub_root-right);return temp;)template Binary_tree &Binary_tree : operator = (constBinary_tree &original)/* Post: The binary tree is reset to copy original. */Binary_tree new_copy(original); clear();root = new_copy.root;new_copy.root = 0;return *this;cpp3.cpptypedef char
22、type;#includeHcpp2.cppn#includeusing namespace std;void visitvisit(type &x);int main()(coutvv”输。?入.?数。y 据 Y个?数。yvvendl;Binary_tree mytree;int n;cinn;coutendl”以。?左人,右,,。子树。/高?度差?不?超?过丫一。?建立街6二t叉?树 jAHendlvv”输。?入.?vnvv个?type 型为数。y 据 Y”vvendl;for(int i=0;ivn;i+)(typej;cinj;mytree.insert(j);)cout”树。的 i?
23、高?度是o?:mytree.height()endlnpreordernn ”;mytree.preorder(visitvisit); coutendl,inorder, mytree.inorder(visitvisit);coutendlpostordern mytree.postorder(visitvisit); coutendl;return 0;)void visitvisit(type &x) coutxn,H;测试数据:ABCd)祖DEd)Gd)力F巾巾巾(其中巾表示空格字符)则输出结果为:先序:ABCDEGF中序:CBEGDFA后序:CGBFDBA测试状况: C:Use0李萧寒DesktopDataSt摩程设计课程没计代码(数分结构八二叉究的建立与遍历0 回输入数据个数7以至句子树高普不超过一建立二叉树 刷入7个type型妥1居ABCDEFG输出结果为:先序:ABCDEFG中序:CBEFDGA后序:CFBGDBA任务下达日期 年一月一日完成日期 年月日指导老师(签名)学生(签名)说明:1、学院、专业、班级均填全称,如:光电工程学院、测控技术、2003o2、本表除签名外均可采纳计算机打印。本表不够,可另附页,但应在页脚添加页码。
限制150内