- #include<iostream>
- #include<stack>
- #include<queue>
- using namespace std;
- static int i=0;
- enum Tags{Left,Right};
- template<typename T>struct node
- {
- T data;
- node<T> *lchild,*right;
- };
- template<typename T>struct elem{
- node<T> *q;
- Tags Flags;
- };
- template<typename T>class Tree{
- private:
- node<T> *root;
- public:
- Tree();
- Tree(string s);
- node<T> *create();
- node<T> *create(string s);
- ~Tree();
- void Release(node<T> *root);
- node<T> *getRoot();
- void preTraverse(node<T> *root); //非递归先序遍历二叉树1
- void PreTraverse(node<T> *root); //非递归先序遍历二叉树2
- void midTraverse(node<T> *root); //非递归中序遍历二叉树
- void posTraverse(node<T> *root); //非递归后序遍历二叉树
- void levTraverse(node<T> *root); //按层次遍历二叉树
- int getDepth(node<T> *root); //获得二叉树的高度
- node<T> *getParent(node<T> *p); //获得二叉树某个节点的父节点
- bool deleteChild(node<T> *p,bool LR); //删除二叉树某个节点的孩子节点,LR=0删除左子树,LR=1删除又子树;
- };
- template<typename T>
- Tree<T>::Tree()
- {
- root=create();
- }
- template<typename T>
- Tree<T>::Tree(string s)
- {
- root=create(s);
- }
- template<typename T>
- node<T> *Tree<T>::create()
- {
- node<T> *root;
- T e;
- cout<<"输入数据:";
- cin>>e;
- if(e=='#')
- root=NULL;
- else {
- root=new node<T>;
- root->data=e;
- root->lchild=create();
- root->right=create();
- }
- return root;
- }
- template<typename T>
- node<T> *Tree<T>::create(string s)
- {
- node<T> *root;
- if(s[i]=='#')
- {
- root=NULL;
- i++;
- }
- else {
- root=new node<T>;
- root->data=s[i];
- i++;
- root->lchild=create(s);
- root->right=create(s);
- }
- return root;
- }
- template<typename T>
- Tree<T>::~Tree()
- {
- Release(root);
- }
- template<typename T>
- void Tree<T>::Release(node<T> *root)
- {
- if(root!=NULL)
- {
- Release(root->lchild);
- Release(root->right);
- delete root;
- }
- }
- template<typename T>
- node<T> *Tree<T>::getRoot()
- {
- return root;
- }
- template<typename T>
- int Tree<T>::getDepth(node<T> *root)
- {
- int i,j;
- if(root==NULL)
- return 0;
- else {
- i=getDepth(root->lchild);
- j=getDepth(root->right);
- return i>j?i+1:j+1;
- }
- }
- template<typename T>
- void Tree<T>::PreTraverse(node<T> *root)
- {
- stack<node<T> *> s;
- node<T> *p=root;
- while(p!=NULL || !s.empty())
- {
- while(p!=NULL)
- {
- cout<<p->data<<" ";
- s.push(p);
- p=p->lchild;
- }
- p=s.top();
- s.pop();
- p=p->right;
- }
- cout<<endl;
- }
- template<typename T>
- void Tree<T>::preTraverse(node<T> *root)
- {
- node<T> *p=root;
- stack<node<T> *> s;
- s.push(NULL);
- while(p!=NULL)
- {
- cout<<p->data<<" ";
- if(p->right!=NULL)
- s.push(p->right);
- if(p->lchild!=NULL)
- p=p->lchild;
- else {
- p=s.top();
- s.pop();
- }
- }
- cout<<endl;
- }
- template<typename T>
- void Tree<T>::midTraverse(node<T> *root)
- {
- node<T> *p=root;
- stack<node<T> *> s;
- while(p!=NULL || !s.empty())
- {
- while(p!=NULL)
- {
- s.push(p);
- p=p->lchild;
- }
- p=s.top();
- s.pop();
- cout<<p->data<<" ";
- p=p->right;
- }
- cout<<endl;
- }
- template<typename T>
- void Tree<T>::posTraverse(node<T> *root)
- {
- elem<T> se;
- stack<elem<T> > s;
- node<T> *p=root;
- while(!s.empty() || p!=NULL)
- {
- while(p!=NULL)
- {
- se.q=p;
- se.Flags=Left;
- s.push(se);
- p=p->lchild;
- }
- se=s.top();
- s.pop();
- p=se.q;
- if(se.Flags==Left)
- {
- se.Flags=Right;
- s.push(se);
- p=p->right;
- }
- else {
- cout<<p->data<<" ";
- p=NULL;
- }
- }
- cout<<endl;
- }
- template<typename T>
- void Tree<T>::levTraverse(node<T> *root)
- {
- queue<node<T> *> q;
- node<T> *p=root;
- q.push(root);
- while(!q.empty())
- {
- p=q.front();
- q.pop();
- cout<<p->data<<" ";
- if(p->lchild!=NULL)
- q.push(p->lchild);
- if(p->right!=NULL)
- q.push(p->right);
- }
- }
- template<typename T>
- node<T>* Tree<T>::getParent(node<T> *p)
- {
- queue<node<T>* > q;
- node<T> *a;
- if(root!=NULL)
- {
- q.push(root);
- while(!q.empty())
- {
- a=q.front();
- q.pop();
- if(a->lchild && a->lchild==p || a->right && a->right==p)
- return a;
- else {
- if(a->lchild!=NULL)
- q.push(a->lchild);
- if(a->right!=NULL)
- q.push(a->rchild);
- }
- }
- }
- return NULL;
- }
- template<typename T>
- bool Tree<T>::deleteChild(node<T> *p,bool LR)
- {
- if(p!=NULL)
- {
- if(!LR)
- {
- Release(p->lchild);
- p->lchild=NULL;
- }
- else
- {
- Release(p->right);
- p->right=NULL;
- }
- }
- else return false;
- }
- int main()
- {
- Tree<char> T;
- //Tree<char> T("ABD##E##CF##GH###");
- T.preTraverse(T.getRoot());
- T.PreTraverse(T.getRoot());
- T.midTraverse(T.getRoot());
- T.posTraverse(T.getRoot());
- T.levTraverse(T.getRoot());
- cout<<T.getParent(T.getRoot()->lchild)->data<<endl;
- cout<<T.getDepth(T.getRoot())<<endl;
- T.deleteChild(T.getRoot(),0);
- T.levTraverse(T.getRoot());
- }
- //该片段来自于http://www.codesnippet.cn/detail/090820135062.html
来源: http://www.codesnippet.cn/detail/090820135062.html