树与二叉树的转换的实现

1、安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称 数据结构 课题名称 树与二叉树的转换的实现 专业 计算机科学与技术 班级 10计本2班 学号10012081姓名 童萍 联系方式导教师江家宝20 11 年 12 月 26 日目录一、 设计目的二、 问题描述三、 需求分析四、 概要设计五、 详细设计六、 调试分析七、 用户使用说明八、 测试结果九、 总结及分析数据结构课程设计-树与二叉树的转换及二叉树的遍历1. 设计目的通过课程设计，巩固所学的理论知识，培养综合运用所学知识解决实际问题的能力。根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析

2、出数据的逻辑结构，合理地选择相映的存储结构，并能设计出解决问题的有效算法。2. 问题描述要求：实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。3. 需求分析本程序的功能是对任意二叉树进行递归前序遍历和后序遍历，用栈实现非递归的前序、和后序遍历，还有对树的层序遍历以及树与二叉树的转换。 本程序要求用户以字符输入，若要实现终端结点，最后以回车键建入数据。本程序的结果将依次打印出递归前序遍历和后序遍历，用栈实现非递归的前序和中序遍历和后序遍历，和线索化层序遍历，输入树及树传换成二叉树。4. 概要设计4.1.二叉树创建用链表实现创建一个树结

3、点的结构体，从键盘输入数据，存入数组。把下标为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、中序非递归遍历中序遍历开始判断结点是否空按后根遍历方式遍历左子树结束按后根遍

4、历方式遍历右子树访问根结点YN4.8.后序非递归算法BiNode是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。void F_PostOrder(BiNode root)。开始判断结点是否空按中根遍历方式遍历左子树结束访问根结点按中根遍历方式遍历右子树YN后序遍历4.6.先序非递归算法BiNode根指针，若 BiNode!= NULL对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取 BiNode的右子树的根指针？void F_PreOrder(BiNode root)4

5、.7.中序非递归算法BiNode是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取BiNo 开始申请一个BiNode 数组 int top=0判断结点是否空输出结点值s+top=root结点的值变为它的左孩子判数组是否空root=stop-root=root->rchild结束判数组或结点是否空NYNYN中序非递归遍历4.8.后序非递归算法BiNode是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。void F_PostOrder(BiNode

6、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

7、+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 "

8、Node.h"#include "debug.h"template<class T>class LinkedQueuepublic: LinkedQueue()front=rear=0; LinkedQueue(); bool IsEmpty()constreturn (front)?false:true); bool IsFull()const; T First()const; T Last()const; LinkedQueue<T>&Add(const T&x); LinkedQueue<T>&De

9、lete(T&x);protected:private: Node<T>*front; Node<T>*rear;template<class T>LinkedQueue<T>:LinkedQueue() Node<T> *next; while (front) next=front->link; delete front; front=next; template<class T>bool LinkedQueue<T>:IsFull()const Node<T>*p; try p=n

10、ew Node<T> delete p; return false; catch (NoMem) return false; template<class T>T LinkedQueue<T>:First()const if (IsEmpty()throw OutOfBounds(); return front->data;template<class T>T LinkedQueue<T>:Last()const if (IsEmpty()throw OutOfBounds(); return rear->data;tem

11、plate<class T>LinkedQueue<T>&LinkedQueue<T>:Add(const T&x) Node<T>*p=new Node<T> p->data=x; p->link=0; if (front)rear->link=p; else front=p; rear=p; return *this;template<class T>LinkedQueue<T>&LinkedQueue<T>:Delete(T&x) if (Is

12、Empty()throw OutOfBounds(); x=front->data; Node<T> *p=front; front=front->link; delete p; return *this;#endifLinkedQueue.h#ifndef I_LINKEDQUEUE_H_ #define I_LINKEDQUEUE_H_#include "Node.h"#include "debug.h"template<class T>class LinkedQueuepublic: LinkedQueue()f

13、ront=rear=0; LinkedQueue(); bool IsEmpty()constreturn (front)?false:true); bool IsFull()const; T First()const; T Last()const; LinkedQueue<T>&Add(const T&x); LinkedQueue<T>&Delete(T&x);protected:private: Node<T>*front; Node<T>*rear;template<class T>Linked

14、Queue<T>:LinkedQueue() Node<T> *next; while (front) next=front->link; delete front; front=next; template<class T>bool LinkedQueue<T>:IsFull()const Node<T>*p; try p=new Node<T> delete p; return false; catch (NoMem) return false; template<class T>T LinkedQu

15、eue<T>:First()const if (IsEmpty()throw OutOfBounds(); return front->data;template<class T>T LinkedQueue<T>:Last()const if (IsEmpty()throw OutOfBounds(); return rear->data;template<class T>LinkedQueue<T>&LinkedQueue<T>:Add(const T&x) Node<T>*p=n

16、ew Node<T> p->data=x; p->link=0; if (front)rear->link=p; else front=p; rear=p; return *this;template<class T>LinkedQueue<T>&LinkedQueue<T>:Delete(T&x) if (IsEmpty()throw OutOfBounds(); x=front->data; Node<T> *p=front; front=front->link; delete p;

17、return *this;#endifstack.h#include "debug.h" template <class T>class SNode public: T data; SNode<T> *link;protected:private:; template<class T>class Stack public: Stack()top=0; Stack(); bool IsEmpty()constreturn top=0; bool IsFull()const; T Top()const; SNode<T>* Top

18、Address()constreturn top; Stack<T>& Add(const T&x); Stack<T>&Delete(T&x); void OutPut();protected:private: SNode<T>*top;template<class T>Stack<T>:Stack() SNode<T>*next; while (top) next=top->link; delete top; top=next; template<class T>boo

19、l Stack<T>:IsFull()const try SNode<T> *p=new Node<T> delete p; return false; catch (NoMem) return true; template<class T>T Stack<T>:Top()const if(IsEmpty()throw OutOfBounds(); return top->data;template<class T>Stack<T>& Stack<T>:Add(const T&

20、x) SNode<T>*p=new SNode<T> p->data=x; p->link=top; top=p; return *this;template<class T>Stack<T>&Stack<T>:Delete(T&x) if (IsEmpty()throw OutOfBounds(); x=top->data; SNode<T>*p=top; top=top->link; delete p; return *this;template<class T>vo

21、id Stack<T>:OutPut() SNode<T>*p=top; while (p) cout<<p->data; p=p->link; if(p)cout<<"->" cout<<endl;stack.h#include "debug.h" template <class T>class SNode public: T data; SNode<T> *link;protected:private:; template<class T>

22、;class Stack public: Stack()top=0; Stack(); bool IsEmpty()constreturn top=0; bool IsFull()const; T Top()const; SNode<T>* TopAddress()constreturn top; Stack<T>& Add(const T&x); Stack<T>&Delete(T&x); void OutPut();protected:private: SNode<T>*top;template<clas

23、s T>Stack<T>:Stack() SNode<T>*next; while (top) next=top->link; delete top; top=next; template<class T>bool Stack<T>:IsFull()const try SNode<T> *p=new Node<T> delete p; return false; catch (NoMem) return true; template<class T>T Stack<T>:Top()con

24、st if(IsEmpty()throw OutOfBounds(); return top->data;template<class T>Stack<T>& Stack<T>:Add(const T&x) SNode<T>*p=new SNode<T> p->data=x; p->link=top; top=p; return *this;template<class T>Stack<T>&Stack<T>:Delete(T&x) if (IsEm

25、pty()throw OutOfBounds(); x=top->data; SNode<T>*p=top; top=top->link; delete p; return *this;template<class T>void Stack<T>:OutPut() SNode<T>*p=top; while (p) cout<<p->data; p=p->link; if(p)cout<<"->" cout<<endl;Node.h#ifndef I_NODE_

26、H_ #define I_NODE_H_template<class T> class LinkedQueue;template <class T>class Node friend class LinkedQueue<T>public:protected:private: T data; Node<T> *link;#endiftreenode.h#ifndef I_TREENODE_H_ #define I_TREENODE_H_template<class T> class Tree;template<class T>

27、;class TreeNode friend class Tree<T>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<T> *first_child,*next_brother; int children_num;#endiftree.h#ifndef I_TREE_H_ #

28、define I_TREE_H_#include <iostream>#include <vector>#include "LinkedQueue.h"#include "stack.h"#include "treenode.h"using namespace std; template <class T>class Treepublic: Tree()root=0;floor=0; Tree() void InputTree(); void ShowTree(); void Show_Binary

29、Tree(); void ShowPath(); void Show_BPath(); void DeleteTree();protected:private: void DeleteNode(TreeNode<T>*p); void SearchPath(TreeNode<T>*p,Stack<T>&mystack); void Search_BPath(TreeNode<T>*p,Stack<T>&mystack); void Print_BNode(TreeNode<T> *p, int c, vec

30、tor<bool>& isend,bool RorL); void PrintNode(TreeNode<T> *p, int c, vector<bool>& isend); TreeNode<T> *root; int *floor;/析构函数/*template<class T>void Tree<T>:DeleteTree() cout<<"销毁所建的树:"<<endl<<endl; delete floor; Stack<TreeNod

31、e<T>*> node_stack; DeleteNode(root);template<class T>void Tree<T>:DeleteNode(TreeNode<T>*p) if (!p) return; if (!p->first_child&&!p->next_brother) cout<<"删除节点"<<p->data<<"!"<<endl; delete p; return; DeleteNode(p-

32、>first_child); p->first_child=0; DeleteNode(p->next_brother); p->next_brother=0; DeleteNode(p); p=0;/*/输入树/*template<class T>void Tree<T>:InputTree() LinkedQueue<TreeNode<T>*>Node_Q; T node_data=0; cout<<"请输入你要建立的树的高度："<<endl; int num; cin>

33、;>num; if (num=0) cout<<"空树!"<<endl; exit(1); if(num<0) throw OutOfBounds(); floor=new intnum+1; floor0=num; cout<<"请输入你要建立的树的根节点数据："<<endl; cin>>node_data; TreeNode<T>*now,*mid; root=new TreeNode<T>(node_data); TreeNode<T>*la

34、st=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<<"请输入节点"<<last->data<<"的子节点，并以#结束："<<endl; cin>>node_data; while (

35、node_data!='#') if (begin) now=new TreeNode<T>(node_data); last->first_child=now; begin=false; Node_Q.Add(now); else mid=new TreeNode<T>(node_data); now->next_brother=mid; now=mid; Node_Q.Add(now); last->children_num+; floori+; cin>>node_data; if (!Node_Q.IsEmpty()

36、 Node_Q.Delete(last); if(!Node_Q.IsEmpty()last=Node_Q.First(); begin=true; /*/输出树/*template<class T>void Tree<T>:ShowTree() cout<<"您输入的树是:"<<endl; if (!root) cout<<"空树!"<<endl; exit(1); TreeNode<T>*p=root; bool begin=true; vector<bool&

37、gt; bIsEnd; bIsEnd.push_back(0); cout<<"Root:"<<root->data<<endl; for(int i=1;i<=floor2;i+) if(i=floor2) bIsEnd0=1; if (begin) p=p->first_child; begin=false; else p=p->next_brother; PrintNode(p,1,bIsEnd); cout<<endl;template <class T>void Tree<T

38、>:PrintNode(TreeNode<T> *p, int c, vector<bool>& isend) for(int j=0;j<c;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<&l

39、t;"" if(p)cout<<" "<<p->data; cout<<endl; bool begin=true; int len=p->children_num; for(int i=1;i<=len;i+) if(isend.size()=c)isend.push_back(0); else isendc=0; if(i=len) if(isend.size()=c)isend.push_back(1); else isendc=1; if (begin) p=p->first_child

40、; begin=false; else p=p->next_brother; PrintNode(p,c+1,isend); /*/输出树的路径template<class T>void Tree<T>:ShowPath() cout<<"树的路径是:"<<endl; if(!root) cout<<root->data<<endl;return; Stack<T> mystack; mystack.Add(root->data); SearchPath(root->

41、first_child,mystack);template <class T>void Tree<T>:SearchPath(TreeNode<T>*p,Stack<T>&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_bro

42、ther,mystack);/*/输出二叉树/*template<class T>void Tree<T>:Show_BinaryTree() cout<<"转化成二叉树是:"<<endl; if (!root) cout<<"空树!"<<endl; exit(1); TreeNode<T>*p=root; vector<bool> bIsEnd; bIsEnd.push_back(0); cout<<"Root:"<&l

43、t;root->data<<endl; bIsEnd0=1; p=p->first_child; Print_BNode(p,1,bIsEnd,false); cout<<endl;template<class T>void Tree<T>:Print_BNode(TreeNode<T> *p, int c, vector<bool>& isend,bool RorL) if (!p) return; for(int j=0;j<c;j+) / if(isendj=0) if(j!=c-1)cou

44、t<<"" else cout<<"" else if(j!=c-1)cout<<" " else cout<<"" if(j!=c-1)cout<<" " else cout<<"" cout<<" "<<p->data; if (RorL) cout<<"R" else cout<<"L"

45、 cout<<endl; int len; if (p->first_child&&p->next_brother) len=2; else if (!p->first_child&&!p->next_brother) len=0; else len=1; for(int i=1;i<=len;i+) if(isend.size()=c)isend.push_back(0); else isendc=0; if(i=len) if(isend.size()=c)isend.push_back(1); else isend

46、c=1; if (len=2) if(i=1) Print_BNode(p->first_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); /*/输出二叉树路径/*

47、template<class T>void Tree<T>:Show_BPath() cout<<"二叉树的路径是:"<<endl; Stack<T>mystack; mystack.Add(root->data); Search_BPath(root->first_child,mystack);template<class T>void Tree<T>:Search_BPath(TreeNode<T>*p,Stack<T>&mystack) if

48、 (!p) return; mystack.Add(p->data); T mid; if (!p->first_child&&!p->next_brother) mystack.OutPut(); SNode<T> *now=mystack.TopAddress(); Search_BPath(p->first_child,mystack); while (mystack.TopAddress()!=now) mystack.Delete(mid); Search_BPath(p->next_brother,mystack);#end

49、ifmain3.cpp#include<iostream>using namespace std;#include<stdlib.h> #include<math.h> #define maxIsize 100#include "tree.h"#define LEN sizeof(struct btree) int maxI=1; typedef struct btree /二叉树节点结构体btree *lchild,*rchild; char data; *BiNode; typedef struct StackElemType/栈的结构体BiNode ptr;int flag;StackElemType;BiNode p ;/二叉树的建立BiNode stree_creat(char *a,int k) BiNode root; maxI+;if(ak='0'|k>maxIsize) return NULL; /判断树是否为空else root=(BiNode)malloc(LEN);/动态申请节点root->data=ak; root->lchild=stree_creat(a,2*k+1); /递归调用为左孩子赋值roo