数据结构-二叉树代码,Java代码库,德仔网

代码语言
代码分类
【Java】数据结构-二叉树
作者:冰辰之心 / 发布于2012/7/23/ 630
数据结构-二叉树
#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=p;
q.push(root);
a=q.front();
if(a!=NULL)
{
while(!q.empty())
{
if(a->lchild && a->lchild==p || a->right && a->right==p)
{
return a;
break;
}
else {
if(p->lchild!=NULL)
q.push(a);
if(p->right!=NULL)
q.push(a);
}
}
}
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());
}
试试其它关键字
　二叉树　
同语言下
可能有用的
冰辰之心贡献的其它代码(1)
.数据结构-二叉树