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

非递归层次中要用到的的队列 */

#include using namespace std;

template class deque; template class Node {

private: T element; Node *next; public: Node() {next=NULL;} friend class deque; };

template class deque {

private: Node *head; Node *rear; protected: int n; //记录队列中元素个数 public: deque(); //构造一个队列 ~deque(); bool IsEmpty() const; //检查队列是否为空 bool Front(T &x) const; //返回第一个队列不删除该元素 T Dedeque(T &x); //返回该队列先进元素，并将其出列 bool Insert(T x); //插入一个元素 bool Delete(); //删除队列中先进的元素 void Clear(); //撤销一个队列 };

template deque::deque() { head=NULL; rear=NULL; n=0; }

template deque::~deque()

{ Clear(); }

template

bool deque::IsEmpty() const { return n==0; }

template

bool deque::Front(T &x) const { if(!head) return false; x=head->element; return true; }

template

T deque::Dedeque(T &x) { Front(x); Delete(); return x; }

template

bool deque::Insert(T x) { Node *p; p=new Node; p->element=x; if(n==0) { head=p; rear=p; } else { rear->next=p; rear=p; } n++; return true; }

template

bool deque::Delete()

{ if(n==0) return false; Node *p=head; head=head->next; delete p; n--; return true; }

template void deque::Clear() { Node *p=head; rear=NULL; while(p!=rear) { p=p->next; delete head; head=p; } head=NULL; delete rear;

}---------------------------------------------------------------------- /*

非递归前序与中序要用到的堆栈 */

#include #define SIZE 20 using namespace std; template class stack {

public: 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=-1;} // 清空桟内元素 private: int maxsize; int top;

T *s; };

template stack::stack(int m) { maxsize=m-1; s=new T[m]; top=-1; }

template

bool stack::Top(T &x) const { if(top==-1) { cout<<\"空栈不可返回元素：\"<template

bool stack::Push(T x) { if(IsFull()) { cout<<\"堆栈已满：\"<template bool stack::Pop() { if(IsEmpty()) { cout<<\"空堆栈不可删除\"<----------------------------------------------------------------------

/*

/*

***非递归中序遍历算法指导思想实现中序遍历需要使用一个工作桟S，巨鹿遍历中经过的节点。

桟中节点具有指向TreeNode 类的指针类型。

（1）在一颗二叉树上，中序遍历访问的第一个节点是该书上最左下方的叶子节点。 将当前指针current指向该节点（如果存在的话）。并将该路径上所有节点（除当前节点外一一进桟）。

（2）接下来就求下一个要访问的的节点，若当前节点有右节点，则下一个要访问的是当前右节点

的最左方的叶子节点，否则就是桟中的节点 */

#include \"LinkedDeque.h\" #include \"stack.h\"

template 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,TreeNode *l=NULL,TreeNode *r=NULL); friend class TowTree; };

template

TreeNode::TreeNode(T &x,TreeNode *l,TreeNode *r) { element=x; left=l; right=r; }

template

class TowTree //二叉树类 {

private: TreeNode *root; void Preorder(void (*Visit)(T &x),TreeNode *r); //前序遍历递归私有成员函数 void Inproder(void (*Visit)(T &x),TreeNode *r); //中序遍历递归私有成员函数 void Postorder(void (*Vist)(T &x),TreeNode *r); //后序遍历私有递归成员函数 protected: int Size(TreeNode *r); //利用后序遍历计算二叉树的节点总数 void Delete(TreeNode *r); //后序遍历释放二叉树的所有节点 TreeNode* Copy(TreeNode *r); //复制构造函数

public: TowTree() {root=NULL;} TowTree(TreeNode *r) {root=r;} //构造一颗空的二叉树 ~TowTree() {Delete(root);} //调用销毁函数 bool Root(T &x); //返回树根的元素 bool IsEmpty(); //判断一颗二叉树是否为空 bool MakeTree(T x,TowTree &l,TowTree &r); //构造一颗二叉树 bool DismantleTree(T &x,TowTree &l,TowTree &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 *t; t=Copy(root); cout<<\" 后序遍历复制二叉树\"; 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 TowTree::Root(T &x) { if(!Root) return false; x=root->element; return true;

}

template

bool TowTree::MakeTree(T x,TowTree &l,TowTree &r) //实现创建一颗二叉树 { if(root || &l == &r) return false; root=new TreeNode(x,l.root,r.root); l.root=r.root=NULL; //注意这一步骤要把左右子树的根节点置为空值 return 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; deque *> 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 TowTree::Preorder(void (*Visit)(T &x),TreeNode *r) //实现前序遍历递归算法 { if(r)

{ Visit(r->element); Preorder(Visit,r->left); Preorder(Visit,r->right); } }

template

void TowTree::Inproder(void (*Visit)(T &x),TreeNode *r) //实现中序遍历递归算法 { if(r!=NULL) { Inproder(Visit,r->left); Visit(r->element); Inproder(Visit,r->right); } }

template

void TowTree::Postorder(void (*Visit)(T &x),TreeNode *r) //实现后续遍历递归算法 { if(r) { Postorder(Visit,r->left); Postorder(Visit,r->right); Visit(r->element); } }

template

void TowTree::PreorderderTraverse(void (*Visit)(T &x)) //实现前序遍历的非递归算法 { TreeNode *p=root; stack *> 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); } }

template

void TowTree::InproderTraverse(void (*Visit)(T &x)) //实现中序遍历的非递归算法 { TreeNode *current=root; stack *> 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) //首先看右子树是否为空,若不为空下一个要访问的元素就是该右子树最左边的叶子节点 { 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); } else current=NULL; } }

template

int TowTree::Size(TreeNode *r) //计算节点数目 { if(!r) return 0; else return Size(r->left)+Size(r->right)+1; }

template

TreeNode* TowTree::Copy(TreeNode *r) //复制一颗二叉树 { if(!r) return NULL; TreeNode *p=new TreeNode(r->element); p->left=Copy(p->left); p->right=Copy(p->right); return p; }

template

void TowTree::Delete(TreeNode *r) { if(r) { Delete(r->left); Delete(r->right); delete r; } }

template void Visit(T &x) { cout<int main() { int n; TowTree a,b,c,x,y,z; y.MakeTree('E',a,b); z.MakeTree('F',a,b); x.MakeTree('C',y,z); y.MakeTree('D',a,b); z.MakeTree('B',y,x); cout<<\"前序遍历\"; z.Preorder(Visit); cout<//释放整个二叉树 cout<<\"二叉树的节点数为\"; n=z.Size(); cout<