c++二叉树的创建与遍历

1、对于前面上传的的部分汉字出现乱表示抱歉，所以从新上传一次 严非递归层次中要用到的的队列*/#includeviostreamusing namespace std;template class deque;templatevclass Tclass Nodeprivate:T element;NodevT *next;public:Node() next=NULL;friend class dequevT;template class dequeprivate:Node *head;Node *rear;protected:int n; 记录队列中元素个数public:deque(); 构造一

2、个队列deque();bool IsEmpty() const; 检查队列是否为空bool Front(T &x) const; 返回第一个队列不删除该元素T Dedeque(T & x); /返回该队列先进元素，并将其出列bool Insert(T x); 插入一个元素bool Delete(); 删除队列中先进的元素void Clear();撤销一个队列;template dequevT:deque()head=NULL;rear=NULL;n=0;template deque:deque()Clear();template vclass Tbool dequevT:IsEmpty() c

3、onst return n=0;template bool deque:Front(T &x) const if(!head)return false; x=head-element; return true;template T dequevT:Dedeque(T &x)Front(x);Delete();return x;template bool deque:Insert(T x)NodevT *p;p=new Node; p-element=x;if(n=0)head=p;rear=p;elserear-next=p; rear=p;n+;return true;template bo

4、ol deque:Delete()if(n=O)return false;NodevT *p=head; head=head-next;delete p;n-;return true;template vclass Tvoid dequevT:Clear()Node *p=head;rear=NULL;while(p!=rear)p=p-next; delete head;head=p;head=NULL;delete rear;严非递归前序与中序要用到的堆栈*/#includeviostream#define SIZE 20using namespace std;templatevclass

5、 Tclass stackpublic:stack(int m);stack() delete s;bool IsEmpty() const return top=-1; /判断堆栈是否为空 bool IsFull() const return top=maxsize; /判断堆栈是否为满 bool Top(T &x) const;/弹出栈顶元素bool Push(T x); /压入一个元素bool Pop(); 删除栈顶元素void Clear() top=-l; / 清空桟内元素private:int maxsize;int top;T *s;；template vclass T stac

6、kvT:stack(int m)maxsize=m-l;s=new Tm;top=-1;templatevclass Tbool stack:Top(T &x) constif(top=-1)coutvv空栈不可返回元素：vvendl; return false;x=stop;return true;templatevclass Tbool stackvT:Push(T x)if(IsFull()coutvv堆栈已满：vvendl; return false;s+top=x;return true;templatevclass Tbool stackvT:Pop()if(IsEmpty()co

7、utvv空堆栈不可删除vvendl; return false;top-;return true;/* *非递归中序遍历算法指导思想实现中序遍历需要使用一个工作桟S,巨鹿遍历中经过的 节点。桟中节点具有指向TreeNodevT类的指针类型。在一颗二叉树上，中序遍历访问的第一个节点是该书上最左下方的叶子节点。将当前指针current指向该节点(如果存在的话)。并将该路径上所有节点(除当前节点外一 一进桟)。接下来就求下一个要访问的的节点，若当前节点有右节点，则下一个要访问的是当前 右节点的最左方的叶子节点，否则就是桟中的节点*/#include LinkedDeque.h#include sta

8、ck.htemplate vclass T class TowTree;template class TreeNode 二叉树的节点类public:T element;TreeNode *left,*right;TreeNode() left=right=NULL;TreeNode(const T &x) element=x;left=right=NULL;TreeNode(T & x,TreeNodevT *l=NULL,TreeNodevT *r=NULL);friend class TowTreevT;templatevclass TTreeNodevT:TreeNode(T & x,T

9、reeNodevT *l,TreeNodevT *r)element=x;left=l;right=r;template class TowTree 二叉树类private:TreeNode *root;void Preorder(void (*Visit)(T & x),TreeNodevT *r);前序遍历递归私有成员函数void Inproder(void (*Visit)(T &x),TreeNode *r); 中序遍历递归私有成员函数 void Postorder(void (*Vist)(T & x),TreeNodevT *r); /后序遍历私有递归成员函数 protected:

10、int Size(TreeNodevT *r);利用后序遍历计算二叉树的节点总数void Delete(TreeNode *r); /后序遍历释放二叉树的所有节点TreeNode* Copy(TreeNodevT *r); 复制构造函数public:TowTree() root=NULL;TowTree(TreeNodevT *r) root=r; /构造一颗空的二叉树TowTree() Delete(root); 调用销毁函数bool Root(T & x); 返回树根的元素bool IsEmpty(); 判断一颗二叉树是否为空bool MakeTree(T x,TowTreevT &l,T

11、owTreevT &r);构造一颗二叉树bool DismantleTree(T &x,TowTree &l,TowTreevT &r); 把一颗二叉树拆分为三部 分void Traverse(void (*Visit)(T &x);非递归成员函数层次遍历二叉树void PreorderderTraverse(void (*Visit)(T &x); 非递归先序遍历二叉树void InproderTraverse(void (*Visit)(T & x); /非递归中序遍历二叉树int Size()return Size(root);void Copy() 调用复制构造函数 TreeNode

12、*t; t=Copy(root);void Copy() 调用复制构造函数 TreeNode *t; t=Copy(root);coutvv后序遍历复制二叉树Postorder(Visit); Delete(t);void Preorder(void (*Visit)(T & x) Preorder(Visit,root);void Inproder(void (*Visit)(T & x) Inproder(Visit,root);void Postorder(void (*Visit)(T & x) Postorder(Visit,root);template bool TowTreevT

13、:Root(T &x)if(!Root)return false;x=root-element;return true;调用私有成员函数前序遍历二叉树调用私有成员函数中序遍历二叉树调用私有成员函数后序遍历二叉树template vclass Tbool TowTreevT:MakeTree(T x,TowTreevT &l,TowTreevT &r) 实现创建一颗二叉树if(root II &l = &r)return false;root=new TreeNodevT(x,l.root,r.root);l.root=r.root=NULL; 注意这一步骤要把左右子树的根节点置为空值retur

14、n true;template bool TowTree:DismantleTree(T &x,TowTree &l,TowTree &r) 拆分二叉树if(!root | &l = &r)return false;x=root-element;l.root=root-left;r.root=root-right;delete root;root=NULL;return true;template void TowTree:Traverse(void (*Visit)(T &x) 利用队列的先进先出，从左到右一次遍历二叉树的节点TreeNode *t=root;dequevTreeNodevT

15、 * d;if(t)d.Insert(t);while(!d.IsEmpty() 如果队列为空则退出循环t=d.Dedeque(t);Visit(t-element);if(t-left) d.Insert(t-left);if(t-right) d.Insert(t-right);template void TowTreevT:Preorder(void (*Visit)(T &x),TreeNode *r) 实现前序遍历递归算法if(r)Visit(r-element);Preorder(Visit,r-left);Preorder(Visit,r-right);template vcla

16、ss Tvoid TowTreevT:Inproder(void (*Visit)(T &x),TreeNodevT *r) 实现中序遍历递归算法if(r!=NULL)Inproder(Visit,r-left);Visit(r-element);Inproder(Visit,r-right);template void TowTreevT:Postorder(void (*Visit)(T &x),TreeNode *r) 实现后续遍历递归算法 if(r)Postorder(Visit,r-left);Postorder(Visit,r-right);Visit(r-element);tem

17、plate void TowTreevT:PreorderderTraverse(void (*Visit)(T &x) 实现前序遍历的非递归算法 TreeNode *p=root;stackvTreeNodevT * s(SIZE);s.Push(p);if(!p)exit(0);while(!s.IsEmpty()s.Top(p);s.Pop();Visit(p-element);if(p-right) s.Push(p-right);if(p-left) s.Push(p-left);void TowTreevT:InproderTraverse(void (*Visit)(T & x)

18、实现中序遍历的非递归算法TreeNodevT *current=root;stackvTreeNodevT * s(SIZE);s.Push(current); while(current-left!=NULL) 首先是指针current指向第一个要访问的元素 s.Push(current-left); s.Top(current);Visit(current-element); 访问第一个要访问的元素 s.Pop();弹出第一个访问的元素while(current)访问下一个要访问的元素if(current-right!=NULL) 首先看右子树是否为空，若不为空下一个要访问的元素 就是该右

19、子树最左边的叶子节点s.Push(current-right); 将右子树压入桟中s.Top(current); 指向该右子树 while(current-left!=NULL) 将该右子树到最左边的叶子节点路径上所有节 点压入桟中s.Push(current-left);s.Top(current); 该最左边的叶子节点即为将要访问的元素else if(!s.IsEmpty() 如果右子树为空则下一个要访问的是桟中元素，显示并弹出 该元素s.Top(current);s.Pop();Visit(current-element);elsecurrent=NULL;template int To

20、wTree:Size(TreeNode *r) 计算节点数目if(!r) return 0;else return Size(r-left)+Size(r-right)+l;TreeNodevT* TowTreevT:Copy(TreeNodevT *r) /复制一颗二叉树 if(!r) return NULL;TreeNodevT *p=new TreeNodevT(r-element); p-left=Copy(p-left);p-right=Copy(p-right);return p;template vclass Tvoid TowTreevT:Delete(TreeNodevT *r) 释放整个二叉树if