数据结构课程设计-树与二叉树的转换的实现.doc

安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称 数据结构 课题名称 树与二叉树的转换的实现 专业 计算机科学与技术 班级 10计本2班 学号10012081姓名 联系方式 指导教师20 11 年 12 月 26 日目录一、 设计目的二、 问题描述三、 需求分析四、 概要设计五、 详细设计六、 调试分析七、 用户使用说明八、 测试结果九、 总结及分析数据结构课程设计-树与二叉树的转换及二叉树的遍历1. 设计目的通过课程设计，巩固所学的理论知识，培养综合运用所学知识解决实际问题的能力。根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相映的存储结构，并能设计出解决问题的有效算法。2. 问题描述要求：实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。3. 需求分析本程序的功能是对任意二叉树进行递归前序遍历和后序遍历，用栈实现非递归的前序、和后序遍历，还有对树的层序遍历以及树与二叉树的转换。 本程序要求用户以字符输入，若要实现终端结点，最后以回车键建入数据。本程序的结果将依次打印出递归前序遍历和后序遍历，用栈实现非递归的前序和中序遍历和后序遍历，和线索化层序遍历，输入树及树传换成二叉树。4. 概要设计4.1.二叉树创建用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。把下标为2*i+1 的值存入左孩子，为2*i+2的存入右孩子。 BiNode creat()，BiNode stree_creat(char *a,int k)。开始判断结点是否空访问根结点结束 按前根遍历方式遍历左子树按前根遍历方式遍历左子树YN图2、前序递归遍历 4.4.中序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。void InOrder(BiNode root)。图3、中序递归遍历图6、中序非递归遍历图6、中序非递归遍历中序遍历开始判断结点是否空按后根遍历方式遍历左子树结束按后根遍历方式遍历右子树访问根结点YN4.8.后序非递归算法BiNode是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。void F_PostOrder(BiNode root)。开始判断结点是否空按中根遍历方式遍历左子树结束访问根结点按中根遍历方式遍历右子树YN后序遍历4.6.先序非递归算法BiNode根指针，若 BiNode!= NULL对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取 BiNode的右子树的根指针？void F_PreOrder(BiNode root)4.7.中序非递归算法BiNode是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取BiNo 开始申请一个BiNode 数组 int top=0判断结点是否空输出结点值s+top=root结点的值变为它的左孩子判数组是否空root=stop-root=root-rchild结束判数组或结点是否空NYNYN中序非递归遍历4.8.后序非递归算法BiNode是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。void F_PostOrder(BiNode root)。开始 申请一个StackElemType数组用一个临时变量存根的信息 数组标志致零 stop.ptr = p p=p-lchild top+判数组标志致是否为一数组标位致一p = stop-1.ptr p= p-rchild结束NYYNYYN判数组是否空判树是否空输出结点的数据N判数组是否空后序非递归.9.层次序遍历算法按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。void LevelOrder(BiNode root)。开始申请一个BiNode数组s申请两个整形变量数组首元赋为根结点s2*i+1 = root-lchild ；s2*i+2 = root-rchild i+root = si max=i输出数组结束N判断树是否空Y层序遍历5. 详细设计源程序：debug.h#ifndef I_DEBUG_H_ #define I_DEBUG_H_class NoMem/异常类public: NoMem()protected:private:;class OutOfBoundspublic: OutOfBounds()protected:private:;#endifLinkedQueue.h#ifndef I_LINKEDQUEUE_H_ #define I_LINKEDQUEUE_H_#include Node.h#include debug.htemplateclass LinkedQueuepublic: LinkedQueue()front=rear=0; LinkedQueue(); bool IsEmpty()constreturn (front)?false:true); bool IsFull()const; T First()const; T Last()const; LinkedQueue&Add(const T&x); LinkedQueue&Delete(T&x);protected:private: Node*front; Node*rear;templateLinkedQueue:LinkedQueue() Node *next; while (front) next=front-link; delete front; front=next; templatebool LinkedQueue:IsFull()const Node*p; try p=new Node; delete p; return false; catch (NoMem) return false; templateT LinkedQueue:First()const if (IsEmpty()throw OutOfBounds(); return front-data;templateT LinkedQueue:Last()const if (IsEmpty()throw OutOfBounds(); return rear-data;templateLinkedQueue&LinkedQueue:Add(const T&x) Node*p=new Node; p-data=x; p-link=0; if (front)rear-link=p; else front=p; rear=p; return *this;templateLinkedQueue&LinkedQueue:Delete(T&x) if (IsEmpty()throw OutOfBounds(); x=front-data; Node *p=front; front=front-link; delete p; return *this;#endifLinkedQueue.h#ifndef I_LINKEDQUEUE_H_ #define I_LINKEDQUEUE_H_#include Node.h#include debug.htemplateclass LinkedQueuepublic: LinkedQueue()front=rear=0; LinkedQueue(); bool IsEmpty()constreturn (front)?false:true); bool IsFull()const; T First()const; T Last()const; LinkedQueue&Add(const T&x); LinkedQueue&Delete(T&x);protected:private: Node*front; Node*rear;templateLinkedQueue:LinkedQueue() Node *next; while (front) next=front-link; delete front; front=next; templatebool LinkedQueue:IsFull()const Node*p; try p=new Node; delete p; return false; catch (NoMem) return false; templateT LinkedQueue:First()const if (IsEmpty()throw OutOfBounds(); return front-data;templateT LinkedQueue:Last()const if (IsEmpty()throw OutOfBounds(); return rear-data;templateLinkedQueue&LinkedQueue:Add(const T&x) Node*p=new Node; p-data=x; p-link=0; if (front)rear-link=p; else front=p; rear=p; return *this;templateLinkedQueue&LinkedQueue:Delete(T&x) if (IsEmpty()throw OutOfBounds(); x=front-data; Node *p=front; front=front-link; delete p; return *this;#endifstack.h#include debug.h template class SNode public: T data; SNode *link;protected:private:; templateclass Stack public: Stack()top=0; Stack(); bool IsEmpty()constreturn top=0; bool IsFull()const; T Top()const; SNode* TopAddress()constreturn top; Stack& Add(const T&x); Stack&Delete(T&x); void OutPut();protected:private: SNode*top;templateStack:Stack() SNode*next; while (top) next=top-link; delete top; top=next; templatebool Stack:IsFull()const try SNode *p=new Node; delete p; return false; catch (NoMem) return true; templateT Stack:Top()const if(IsEmpty()throw OutOfBounds(); return top-data;templateStack& Stack:Add(const T&x) SNode*p=new SNode; p-data=x; p-link=top; top=p; return *this;templateStack&Stack:Delete(T&x) if (IsEmpty()throw OutOfBounds(); x=top-data; SNode*p=top; top=top-link; delete p; return *this;templatevoid Stack:OutPut() SNode*p=top; while (p) coutdata; p=p-link; if(p)cout; coutendl;stack.h#include debug.h template class SNode public: T data; SNode *link;protected:private:; templateclass Stack public: Stack()top=0; Stack(); bool IsEmpty()constreturn top=0; bool IsFull()const; T Top()const; SNode* TopAddress()constreturn top; Stack& Add(const T&x); Stack&Delete(T&x); void OutPut();protected:private: SNode*top;templateStack:Stack() SNode*next; while (top) next=top-link; delete top; top=next; templatebool Stack:IsFull()const try SNode *p=new Node; delete p; return false; catch (NoMem) return true; templateT Stack:Top()const if(IsEmpty()throw OutOfBounds(); return top-data;templateStack& Stack:Add(const T&x) SNode*p=new SNode; p-data=x; p-link=top; top=p; return *this;templateStack&Stack:Delete(T&x) if (IsEmpty()throw OutOfBounds(); x=top-data; SNode*p=top; top=top-link; delete p; return *this;templatevoid Stack:OutPut() SNode*p=top; while (p) coutdata; p=p-link; if(p)cout; coutendl;Node.h#ifndef I_NODE_H_ #define I_NODE_H_template class LinkedQueue;template class Node friend class LinkedQueue;public:protected:private: T data; Node *link;#endiftreenode.h#ifndef I_TREENODE_H_ #define I_TREENODE_H_template class Tree;templateclass TreeNode friend class Tree;public: TreeNode()first_child=next_brother=0,children_num=0; TreeNode(const T&e) data=e; first_child=next_brother=0; children_num=0; protected:private: T data; TreeNode *first_child,*next_brother; int children_num;#endiftree.h#ifndef I_TREE_H_ #define I_TREE_H_#include #include #include LinkedQueue.h#include stack.h#include treenode.husing namespace std; template class Treepublic: Tree()root=0;floor=0; Tree() void InputTree(); void ShowTree(); void Show_BinaryTree(); void ShowPath(); void Show_BPath(); void DeleteTree();protected:private: void DeleteNode(TreeNode*p); void SearchPath(TreeNode*p,Stack&mystack); void Search_BPath(TreeNode*p,Stack&mystack); void Print_BNode(TreeNode *p, int c, vector& isend,bool RorL); void PrintNode(TreeNode *p, int c, vector& isend); TreeNode *root; int *floor;/析构函数/*templatevoid Tree:DeleteTree() cout销毁所建的树:endlendl; delete floor; StackTreeNode* node_stack; DeleteNode(root);templatevoid Tree:DeleteNode(TreeNode*p) if (!p) return; if (!p-first_child&!p-next_brother) cout删除节点data!first_child); p-first_child=0; DeleteNode(p-next_brother); p-next_brother=0; DeleteNode(p); p=0;/*/输入树/*templatevoid Tree:InputTree() LinkedQueueTreeNode*Node_Q; T node_data=0; cout请输入你要建立的树的高度：num; if (num=0) cout空树!endl; exit(1); if(num0) throw OutOfBounds(); floor=new intnum+1; floor0=num; cout请输入你要建立的树的根节点数据：node_data; TreeNode*now,*mid; root=new TreeNode(node_data); TreeNode*last=root; bool begin=true; floor1=1; Node_Q.Add(root); for (int i=2;i=floor0;i+)/每一层i floori=0; last=Node_Q.First(); for (int j=1;j=floori-1&last;j+)/每一层里每个节点j cout请输入节点data的子节点，并以#结束：node_data; while (node_data!=#) if (begin) now=new TreeNode(node_data); last-first_child=now; begin=false; Node_Q.Add(now); else mid=new TreeNode(node_data); now-next_brother=mid; now=mid; Node_Q.Add(now); last-children_num+; floori+; cinnode_data; if (!Node_Q.IsEmpty() Node_Q.Delete(last); if(!Node_Q.IsEmpty()last=Node_Q.First(); begin=true; /*/输出树/*templatevoid Tree:ShowTree() cout您输入的树是:endl; if (!root) cout空树!endl; exit(1); TreeNode*p=root; bool begin=true; vector bIsEnd; bIsEnd.push_back(0); coutRoot:dataendl; for(int i=1;ifirst_child; begin=false; else p=p-next_brother; PrintNode(p,1,bIsEnd); coutendl;template void Tree:PrintNode(TreeNode *p, int c, vector& isend) for(int j=0;jc;j+) / if(isendj=0) if(j!=c-1)cout; else cout; else if(j!=c-1)cout ; else cout; if(j!=c-1)cout ; else cout; if(p)cout data; coutchildren_num; for(int i=1;ifirst_child; begin=false; else p=p-next_brother; PrintNode(p,c+1,isend); /*/输出树的路径templatevoid Tree:ShowPath() cout树的路径是:endl; if(!root) coutdataendl;return; Stack mystack; mystack.Add(root-data); SearchPath(root-first_child,mystack);template void Tree:SearchPath(TreeNode*p,Stack&mystack) if(p)mystack.Add(p-data); else return; if (!p-first_child) mystack.OutPut(); SearchPath(p-first_child,mystack); T mid; mystack.Delete(mid); SearchPath(p-next_brother,mystack);/*/输出二叉树/*templatevoid Tree:Show_BinaryTree() cout转化成二叉树是:endl; if (!root) cout空树!endl; exit(1); TreeNode*p=root; vector bIsEnd; bIsEnd.push_back(0); coutRoot:datafirst_child; Print_BNode(p,1,bIsEnd,false); coutendl;templatevoid Tree:Print_BNode(TreeNode *p, int c, vector& isend,bool RorL) if (!p) return; for(int j=0;jc;j+) / if(isendj=0) if(j!=c-1)cout; else cout; else if(j!=c-1)cout ; else cout; if(j!=c-1)cout ; else cout; cout data; if (RorL) coutR; else coutL; coutfirst_child&p-next_brother) len=2; else if (!p-first_child&!p-next_brother) len=0; else len=1; for(int i=1;ifirst_child,c+1,isend,false); p=p-next_brother; else Print_BNode(p,c+1,isend,true); else if (len=1) if(p-first_child) Print_BNode(p-first_child,c+1,isend,false); if (p-next_brother) Print_BNode(p-next_brother,c+1,isend,true); /*/输出二叉树路径/*templatevoid Tree:Show_BPath() cout二叉树的路径是:endl; Stackmystack; mystack.Add(root-data); Search_BPath(root-first_child,mystack);templatevoid Tree:Search_BPath(TreeNode*p,Stack&mystack) if (!p) return; mystack.Add(p-data); T mid; if (!p-first_child&!p-next_brother) mystack.OutPut(); SNode *now=mystack.TopAddress(); Search_BPath(p-first_child,mystack); while (mystack.TopAddress()!=now) mystack.Delete(mid); Search_BPath(p-next_brother,mystack);#endifmain3.cpp#includeusing namespace std;#include #include #define maxIsize 100#include tree.h#define LEN sizeof(struct btree) int maxI=1; typedef struct btree /二叉树节点结构体btree *