| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 21928 人关注过本帖, 1 人收藏
标题:树跟二叉树完整试用版
只看楼主 加入收藏
热情依然
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:715
专家分:0
注 册:2005-4-5
收藏(1)
 问题点数:0 回复次数:79 
树跟二叉树完整试用版
WRlw5zlq.rar (25.29 KB) 树跟二叉树完整试用版(功能会不断更新)


//brinarytree.h

#include<iostream>
#include<math.h>
#include<assert.h>
#include"stack.h"
#include"queue.h"
using namespace std;

struct Level{

int yLevel;

int xIndent;
};

template<typename T>class BinaryTree;

template<typename T>class BinaryTreeNode{

public:

BinaryTreeNode(T data){element=data; LeftChild=NULL; RightChild=NULL; lTag=0;rTag=0;}

friend class BinaryTree<T>;
private:

BinaryTreeNode<T> *LeftChild,*RightChild;

T element;

int lTag,rTag;
};

template<typename T>class BinaryTree
{
public:

BinaryTree(){root=NULL;}

~BinaryTree();

void MakeEmpty(){ MakeEmpty(root);} //清除二叉树

int Research(T data); //寻找结点

void CreatTree(T data); //建立二叉树

void PrintVTree(){ PrintVTree(root);} //打印图形二叉树

void PrinTree(){ PrinTree(root,0);} //用凹凸法打印图型二叉树

void PreOrder(){ PreOrder(root);} //非递归前序遍历

void InOrder(){InOrder(root);} //非递归中序遍历

void PostOrder(){PostOrder(root);} //非递归后序遍历

void COrder(){ COrder(root);} //层次遍历

void Countleaf(int &c){ Countleaf(root,c);} //计算叶结点个数

int Depth_queue(){ return Depth_queue(root);} //用队列求二叉树深度

int Depth_stack(){ return Depth_stack(root);} //用栈求二叉树深度

void PackOrder(){PackOrder(root);} //用括号遍历二叉树

void creatpackettree(char *str); //用括号建立二叉树

void m_creatbrinarytree(T *str,int n); //建立满二叉树

BinaryTreeNode<T>* pre_and_in_creatbinary(char *ppos,char * ipos,int n);//用中序周游跟前序周游建立二叉树

void InThread(){ InThread(root);} //中序线索二叉树

void In_thread_Order(){ In_thread_Order(root);} //中序线索周游二叉树

void FindNextinInorderTree(T data){ //中序线索中找指定结点在前序下的后续

BinaryTreeNode<T> *p;

p=FindNextinInorderTree(root,data);

if(p==NULL)

cout<<"\n该结点在前序下没有后续!"<<endl<<endl;

else{
cout<<endl;

cout<<"在中序线索二叉树中找指定结点在前序下的后缀:"<<p->element<<endl<<endl;
}
}

void FindBeforeinInorderTree(T data){ //中序线索中找指定结点在后序下的前驱

BinaryTreeNode<T> *p;

p=FindBeforeinInorderTree(root,data);

if(p==NULL)

cout<<"\n该结点在后序下没有前驱!"<<endl<<endl;

else{
cout<<endl;

cout<<"在中序线索中找指定结点在后序下的前驱:"<<p->element<<endl<<endl;
}
}
void Post_Thread_Order(){ Post_Thread_Order(root);} //后序周游中序线索二叉树

void Del_BinaryTreeNode(T data){ Del_BinaryTreeNode(root,data);}//排序二叉树删除结点

void Del_BinaryTreeNode_EX(T data){ Del_BinaryTreeNode_EX(root,data);}//改进的二叉树删除结点

void InsertNode_in_Inthread(T find_data,T insert_data){ InsertNode_in_Inthread(root,find_data,insert_data);}//在中序线索二叉树插入结点

void Ancestor(T data){ Ancestor(root,data);}//打印指定结点的祖先

void Closed_Ancestor(T data1,T data2){ Closed_Ancestor(root,data1,data2);}//打印指定两个结点的最近祖先

void PreOrder_Ex(){ PreOrder_Ex(root);}//改进的非递归前序遍历,这个遍历少了一个子循环,高效很多

private:

BinaryTreeNode<T> *root,*p;

void MakeEmpty(BinaryTreeNode<T> *t);

void PrintVTree(BinaryTreeNode<T> *t);

void PrinTree(BinaryTreeNode<T> *b,int level);

void PreOrder(BinaryTreeNode<T> *t);

void InOrder(BinaryTreeNode<T> *t);

void PostOrder(BinaryTreeNode<T> *t);

void COrder(BinaryTreeNode<T> *t);

void Countleaf(BinaryTreeNode<T> *t,int &c);

int Depth_queue(BinaryTreeNode<T> *t);

int Depth_stack(BinaryTreeNode<T> *t);

void PackOrder(BinaryTreeNode<T> *t);

void InThread(BinaryTreeNode<T> *t);

void In_thread_Order(BinaryTreeNode<T> *t);

BinaryTreeNode<T> *FindNextinInorderTree(BinaryTreeNode<T> *t,T data);

BinaryTreeNode<T> *FindBeforeinInorderTree(BinaryTreeNode<T> *t,T data);

void Post_Thread_Order(BinaryTreeNode<T> *t);

BinaryTreeNode<T>* Is_PostOrder_first_Node(BinaryTreeNode<T> *t);//判断是否后序周游中序线索二叉树的第一个结点

void Del_BinaryTreeNode(BinaryTreeNode<T> *t,T data);

void Del_BinaryTreeNode_EX(BinaryTreeNode<T> *t,T data);

void InsertNode_in_Inthread(BinaryTreeNode<T> *t,T find_data, T insert_data);

void Ancestor(BinaryTreeNode<T> *t,T data);

void Closed_Ancestor(BinaryTreeNode<T> *t,T data1,T data2);

void PreOrder_Ex(BinaryTreeNode<T> *t);

};

template<typename T>BinaryTree<T>::~BinaryTree()
{
MakeEmpty(root);
}

template<typename T>void BinaryTree<T>::MakeEmpty(BinaryTreeNode<T> *t)
{
if(t!=NULL)
{
if(t->lTag==0)

MakeEmpty(t->LeftChild);

if(t->rTag==0)

MakeEmpty(t->RightChild);

delete t;
}
}

template<typename T>int BinaryTree<T>::Research(T data)
{
BinaryTreeNode<T> *ptr=root;

p=NULL;

while(ptr)
{
if(ptr->element==data) {p=ptr; return 1;}

if(ptr->element>data)
{
p=ptr;

ptr=ptr->LeftChild;
}

else{
p=ptr;

ptr=ptr->RightChild;
}
}

return 0;
}
template<typename T> void BinaryTree<T>::CreatTree(T data)
{
BinaryTreeNode<T> *current;

if(Research(data)==0)
{

current=new BinaryTreeNode<T>(data);

if(p==NULL) root=current;

else if(p->element>data)

p->LeftChild=current;

else p->RightChild=current;
}
}

template<typename T>void BinaryTree<T>::PrintVTree(BinaryTreeNode<T> *t){

int screenWidth=64;

int dataWidth=2;

queue<BinaryTreeNode<T> *> Q;

queue<Level> QI;

BinaryTreeNode<T> *p;

Level s,s1,s2;

double offset,level=-1,i;

Q.EnQue(t);

s.xIndent=screenWidth/dataWidth;

s.yLevel=0;

QI.EnQue(s);

while(!Q.IsEmpty()&&!QI.IsEmpty())
{
s2=s;

p=Q.DeQue();

s=QI.DeQue();

if(s.yLevel!=level){

cout<<"\n\n第"<<s.yLevel<<"层";

level=s.yLevel;

for(i=0;i<s.xIndent-1;i++) cout<<" ";
}
else
for(i=0;i<s.xIndent-s2.xIndent;i++) cout<<" ";

cout<<p->element;

if(p->LeftChild!=NULL)
{
Q.EnQue(p->LeftChild);

s1.yLevel=s.yLevel+1;

offset=screenWidth/pow(dataWidth,s1.yLevel+1);

s1.xIndent=s.xIndent-offset;

QI.EnQue(s1);
}
if(p->RightChild!=NULL)
{

Q.EnQue(p->RightChild);

s1.yLevel=s.yLevel+1;

offset=screenWidth/pow(dataWidth,s1.yLevel+1);

s1.xIndent=s.xIndent+offset;

QI.EnQue(s1);
}
}
}

template<typename T>void BinaryTree<T>::PrinTree(BinaryTreeNode<T> *b,int level){
if(b!=NULL)
{
PrinTree(b->RightChild,level+1);
if(level!=0){
for(int i=0;i<6*(level-1);i++)cout<<" ";
cout<<"-----";
}
cout<<b->element<<endl;
PrinTree(b->LeftChild,level+1);
}
}


template<typename T>void BinaryTree<T>::PreOrder(BinaryTreeNode<T> *t)
{
stack<BinaryTreeNode<T>*> s;

BinaryTreeNode<T> *p=t;

while(!s.IsEmpty()||p!=NULL)
{
while(p)
{
s.Push(p);

cout<<p->element<<'\t';

p=p->LeftChild;
}
p=s.Pop();

p=p->RightChild;
}
}

template<typename T>void BinaryTree<T>::InOrder(BinaryTreeNode<T> *t)
{
stack<BinaryTreeNode<T>*> s;

BinaryTreeNode<T> *p=t;

while(!s.IsEmpty()||p!=NULL)
{
while(p)
{
s.Push(p);

p=p->LeftChild;
}
p=s.Pop();

cout<<p->element<<'\t';

p=p->RightChild;
}
}

template<typename T>void BinaryTree<T>::PostOrder(BinaryTreeNode<T> *t)
{
stack<BinaryTreeNode<T>*> s;

BinaryTreeNode<T> *p=t;

int tag[255],top=-1;

while(!s.IsEmpty()||p!=NULL)
{
while(p)
{
s.Push(p);

tag[++top]=0;

p=p->LeftChild;
}
if(top>-1)

if(tag[top]==1)

{
cout<<s.GetTop()->element<<'\t';

s.Pop();

top--;
}
else{

p=s.GetTop();

tag[top]=1;

p=p->RightChild;
}
}
}

template<typename T>void BinaryTree<T>::COrder(BinaryTreeNode<T> *t)
{

BinaryTreeNode<T> *p;

p=t;

queue<BinaryTreeNode<T> *> Q;

Q.EnQue(p);

while(!Q.IsEmpty())
{
p=Q.DeQue();

cout<<p->element<<"\t";

if(p->LeftChild!=NULL)

Q.EnQue(p->LeftChild);

if(p->RightChild!=NULL)

Q.EnQue(p->RightChild);
}

}
template<typename T>void BinaryTree<T>::Countleaf(BinaryTreeNode<T> *t,int &c)
{

stack<BinaryTreeNode<T>*> s;

BinaryTreeNode<T> *p=t;

int tag[255],top=-1;

while(!s.IsEmpty()||p!=NULL)
{
while(p)
{
s.Push(p);

tag[++top]=0;

p=p->LeftChild;
}
if(top>-1)

if(tag[top]==1)

{
if(s.GetTop()->LeftChild==NULL && s.GetTop()->RightChild==NULL)

c++;

s.Pop();

top--;
}
else{

p=s.GetTop();

tag[top]=1;

p=p->RightChild;
}
}
}

template<typename T>int BinaryTree<T>::Depth_queue(BinaryTreeNode<T> *t)
{
queue<BinaryTreeNode<T> *> Q;

queue<Level> QI;

int depth;

Level y,y1;

BinaryTreeNode<T> *p=t;

y.yLevel=1;

Q.EnQue(p);

QI.EnQue(y);

while(!Q.IsEmpty())
{
p=Q.DeQue();

y=QI.DeQue();

if(p->LeftChild!=NULL)
{
Q.EnQue(p->LeftChild);

y1.yLevel=y.yLevel+1;

QI.EnQue(y1);
}

if(p->RightChild!=NULL)
{
Q.EnQue(p->RightChild);

y1.yLevel=y.yLevel+1;

QI.EnQue(y1);
}
}

depth=y.yLevel;

return depth;
}

template<typename T>int BinaryTree<T>::Depth_stack(BinaryTreeNode<T> *t)
{
stack<BinaryTreeNode<T>*> S;

BinaryTreeNode<T> *p;

int tag[100],top=-1;

p=t;

stack<Level> s,s1; //s1是用来记录当前有左右孩子的结点的高读

Level y,y1,temp;

temp.yLevel=0;

y.yLevel;

while(p!=NULL||!S.IsEmpty()){

while(p!=NULL){

S.Push(p);

y.yLevel=0;

s.Push(y);

tag[++top]=0;

p=p->LeftChild;
}
if(top>-1)

if(tag[top]==1)
{


y=s.Pop();


if(S.GetTop()->LeftChild!=NULL&&S.GetTop()->RightChild!=NULL)
{
temp=s1.Pop();

if(temp.yLevel>y.yLevel)

s.Push(temp);

else{

y1.yLevel=y.yLevel+1;

s.Push(y1);

}

}
else{

y1.yLevel=y.yLevel+1;

s.Push(y1);

}



S.Pop();

top--;
}
else {

p=S.GetTop();

if(p->LeftChild!=NULL&&p->RightChild!=NULL)//当这个结点是它左孩子的后续并且这个结点有右孩子
{
y=s.Pop();

y1.yLevel=y.yLevel+1;

s1.Push(y1);

temp=y1;


}

tag[top]=1;

p=p->RightChild;


}
}

y=s.Pop();

return y.yLevel;
}


template<typename T>void BinaryTree<T>::creatpackettree(char *str)
{
BinaryTreeNode<T> *p;

stack<BinaryTreeNode<T> *> s;

int k,i=0;

char ch=str[i];

while(ch!='\0')
{
switch(ch)
{
case '(': s.Push(p); k=1; break;

case ')': s.Pop(); break;

case ',': k=2; break;

default:

p=new BinaryTreeNode<T>(ch);

if(root==NULL)

root=p;

else{

switch(k)
{
case 1: s.GetTop()->LeftChild=p; break;

case 2: s.GetTop()->RightChild=p; break;
}
}
}
i++;

ch=str[i];
}
}


[此贴子已经被作者于2006-7-13 21:32:25编辑过]



5vEcdW6y.rar (20.12 KB) 二叉树完整试用版(功能会不断更新)

搜索更多相关主题的帖子: 二叉树 试用版 
2005-07-20 00:25
热情依然
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:715
专家分:0
注 册:2005-4-5
收藏
得分:0 

template<typename T>void BinaryTree<T>::PackOrder(BinaryTreeNode<T> *t) { if(t!=NULL) { cout<<t->element;

if(t->LeftChild!=NULL||t->RightChild!=NULL) { cout<<"(";

PackOrder(t->LeftChild);

if(t->RightChild!=NULL)

cout<<",";

PackOrder(t->RightChild);

cout<<")"; } } }

template<typename T>void BinaryTree<T>::m_creatbrinarytree(T *str,int n)//根据满二叉树的性质,2i为左孩子,2i+1为右孩子 { queue<BinaryTreeNode<T>*> q;

BinaryTreeNode<T> *p,*p1;

int i=1;

p=new BinaryTreeNode<T>(str[i-1]);

root=p;

q.EnQue(root);

while(i<n) { p1=q.DeQue(); if(2*i-1<n) { p=new BinaryTreeNode<T>(str[2*i-1]);

p1->LeftChild=p;

q.EnQue(p1->LeftChild); } if(2*i<n) { p=new BinaryTreeNode<T>(str[2*i]);

p1->RightChild=p;

q.EnQue(p1->RightChild); } i++; } }

template<typename T>BinaryTreeNode<T> * BinaryTree<T>::pre_and_in_creatbinary(char *ppos,char *ipos,int n) { char *rpos;

int k;

BinaryTreeNode<T> *p;

if(n<=0)

return NULL;

p=new BinaryTreeNode<T>(*ppos);

for(rpos=ipos;rpos<ipos+n;rpos++)

if(*rpos==*ppos)

break;

k=rpos-ipos;

p->LeftChild=pre_and_in_creatbinary(ppos+1,ipos,k);

p->RightChild=pre_and_in_creatbinary(ppos+k+1,rpos+1,n-1-k);

root=p; return p; } template<typename T>void BinaryTree<T>::InThread(BinaryTreeNode<T> *t) { BinaryTreeNode<T> *p=root,*temp=NULL;

stack<BinaryTreeNode<T> *> s;

while(1) { while(p!=NULL) { s.Push(p);

p=p->LeftChild; }

if(s.IsEmpty())

break; p=s.GetTop();

s.Pop(); if(temp!=NULL) { if(temp->RightChild==NULL) { temp->RightChild=p;

temp->rTag=1; }

if(p->LeftChild==NULL) { p->LeftChild=temp;

p->lTag=1; } }

temp=p;

p=p->RightChild; } }


c++/C + 汇编 = 天下无敌
2005-07-20 00:28
热情依然
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:715
专家分:0
注 册:2005-4-5
收藏
得分:0 

template<typename T>void BinaryTree<T>::In_thread_Order(BinaryTreeNode<T> *t) { BinaryTreeNode<T> *p=t;

if(p==NULL)

return;

while(p->LeftChild!=NULL)

p=p->LeftChild;

while(1) { cout<<p->element<<'\t';

if(p->RightChild==NULL)

break; if(p->rTag==1)

p=p->RightChild;

else{

p=p->RightChild;

while(p->lTag==0)

p=p->LeftChild; } } }

template<typename T> BinaryTreeNode<T> *BinaryTree<T>::FindNextinInorderTree(BinaryTreeNode<T> *t,T data) { BinaryTreeNode<T> *p=t,*temp=NULL;

if(p==NULL)

return NULL;

while(p->LeftChild!=NULL)

p=p->LeftChild;

while(1) { if(p->element==data)

break;

if(p->RightChild==NULL)

break; if(p->rTag==1)

p=p->RightChild;

else{

p=p->RightChild;

while(p->lTag==0)

p=p->LeftChild; } } if(p->LeftChild!=NULL&&p->lTag==0)

return p->LeftChild;

if(p->rTag==0&&p->RightChild==NULL) { cout<<"找不到!"<<endl<<endl;

return NULL; }

else

temp=p;

while(temp->rTag==1)

temp=temp->RightChild;

temp=temp->RightChild;

return temp; }

template<typename T> BinaryTreeNode<T>* BinaryTree<T>::Is_PostOrder_first_Node(BinaryTreeNode<T> *t) {

stack<BinaryTreeNode<T>*> s;

BinaryTreeNode<T> *p=t;

int tag[255],top=-1; while(!s.IsEmpty()||p!=NULL) { while(p) { s.Push(p); tag[++top]=0; if(p->lTag==0) p=p->LeftChild;

else p=NULL;

} if(top>-1)

if(tag[top]==1) return s.GetTop(); else{

p=s.GetTop();

tag[top]=1;

if(p->rTag==0)

p=p->RightChild;

else p=NULL; } } } template<typename T> BinaryTreeNode<T> *BinaryTree<T>::FindBeforeinInorderTree(BinaryTreeNode<T> *t,T data) { BinaryTreeNode<T> *p=t,*temp=NULL,*p1;

if(p==NULL)

return NULL;

while(p->LeftChild!=NULL) p=p->LeftChild;

while(1) { if(p->element==data)

break;

if(p->RightChild==NULL)

break; if(p->rTag==1)

p=p->RightChild;

else{

p=p->RightChild;

while(p->lTag==0)

p=p->LeftChild; } }

p1=Is_PostOrder_first_Node(t);

if(p1->element==p->element)

return NULL; if(p->RightChild!=NULL&&p->rTag==0) { temp=p;

temp=temp->RightChild;

if(temp->LeftChild!=NULL&&temp->lTag==1)

return temp; }

else if(p->LeftChild!=NULL) { temp=p;

temp=temp->LeftChild; if(temp->LeftChild==NULL) return p->LeftChild;

else { temp=temp->LeftChild; return temp; } } }


c++/C + 汇编 = 天下无敌
2005-07-20 00:29
热情依然
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:715
专家分:0
注 册:2005-4-5
收藏
得分:0 

template<typename T> void BinaryTree<T>::Post_Thread_Order(BinaryTreeNode<T> *t) { stack<BinaryTreeNode<T>*> s;

BinaryTreeNode<T> *p=t;

int tag[255],top=-1; while(!s.IsEmpty()||p!=NULL) { while(p) { s.Push(p); tag[++top]=0; if(p->lTag==0) p=p->LeftChild;

else p=NULL;

} if(top>-1)

if(tag[top]==1) { cout<<s.GetTop()->element<<'\t';

s.Pop();

top--; } else{

p=s.GetTop();

tag[top]=1;

if(p->rTag==0)

p=p->RightChild;

else p=NULL; } } }

template<typename T> void BinaryTree<T>::Del_BinaryTreeNode(BinaryTreeNode<T> *t,T data) { BinaryTreeNode<T> *temp=NULL,*p=t,*parent=NULL; while(p->element!=data) { parent=p;

if(p->element<data)

p=p->RightChild;

else p=p->LeftChild; }

if(p->LeftChild==NULL) { if(parent==NULL)

t=p->RightChild;

else if(parent->LeftChild==p)

parent->LeftChild=p->RightChild;

else parent->RightChild=p->RightChild; delete p;

p=NULL;

return; }

else { temp=p->LeftChild;

while(temp->RightChild!=NULL)

temp=temp->RightChild;

temp->RightChild=p->RightChild;

if(parent==NULL)

t=p->LeftChild;

else if(parent->LeftChild==p)

parent->LeftChild=p->LeftChild;

else parent->RightChild=p->LeftChild;

delete p;

p=NULL;

return; } }

template<typename T>void BinaryTree<T>::Del_BinaryTreeNode_EX(BinaryTreeNode<T> *t,T data) { BinaryTreeNode<T> *temp=NULL,*p=t,*parent=NULL,*tempparent=NULL; while(p->element!=data) { parent=p;

if(p->element<data)

p=p->RightChild;

else p=p->LeftChild; }

if(p->LeftChild==NULL) { if(parent==NULL)

t=p->RightChild;

else if(parent->LeftChild==p)

parent->LeftChild=p->RightChild;

else parent->RightChild=p->RightChild; delete p;

p=NULL;

return; }

else{ temp=p->LeftChild;

while(temp->RightChild!=NULL) { tempparent=temp;

temp=temp->RightChild; }

if(tempparent==NULL)

p->LeftChild=temp->LeftChild;

else tempparent->RightChild=temp->RightChild;

if(parent==NULL)

t=temp;

else if(parent->LeftChild==p)

parent->LeftChild=temp;

else parent->RightChild=temp;

temp->LeftChild=p->LeftChild;

temp->RightChild=p->RightChild;

delete p;

p=NULL; } }


c++/C + 汇编 = 天下无敌
2005-07-20 00:35
热情依然
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:715
专家分:0
注 册:2005-4-5
收藏
得分:0 

tree.h template<typename T>class Tree;

/*定义树结点类*/ template<typename T>class TreeNode { public:

TreeNode(T value); virtual~TreeNode(){}; T value(); friend class Tree<T>;

private:

T m_Value; TreeNode<T> * pChild; TreeNode<T> *pSibling;

};

template<typename T>TreeNode<T>::TreeNode(T value) { m_Value = value; pChild = NULL; pSibling = NULL; }

/*定义树类,用动态左孩子/右孩子表示法来建立树*/ template<typename T>class Tree { public: Tree(){ root=current=NULL; } ~Tree(){ MakeEmpty(root);} int Root(); int FirstChild(); int NextSibling(); void InsertChild(T value); void DeleteSubTree(TreeNode<T> *&t); void DisplayTree(); void MakeEmpty(TreeNode<T> *&t);

private: TreeNode<T> *root, *current; //定义根结点根当前指针

TreeNode<T> * GetParent(TreeNode<T> *t,TreeNode<T> *c); TreeNode<T> * PrevSibling1(TreeNode<T> *t,TreeNode <T> *current); TreeNode<T> * PrevSibling2(TreeNode<T> *t,TreeNode <T> *current); int Current(TreeNode<T> *&t); void RootFistTraverse(TreeNode<T> *t); void RootLastTraverse(TreeNode<T> *t); void WidthTraverse(TreeNode<T> *t); void PrintVTree(TreeNode<T> *t);

};

/*清空已t为跟结点的树*/ template<typename T>void Tree<T>::MakeEmpty(TreeNode<T> *&t) { if(t!=NULL) { MakeEmpty(t->pChild); MakeEmpty(t->pSibling); delete t; } }

/*确定当前结点*/ template<typename T>int Tree<T>::Current(TreeNode<T> *&t) { if(t == NULL) { current = NULL; return 0; }

else { current = t; return 1; } }

/*定位根结点*/ template<typename T>int Tree<T>::Root() { if(root == NULL) { current = NULL; return 0; }

return Current(root); }

/*查找父母结点*/ template<typename T>TreeNode<T>* Tree<T>::GetParent(TreeNode<T> *t,TreeNode<T> *c) { if(t == NULL || t->pChild == NULL && t->pSibling == NULL) return NULL;

if(t->pChild == c || t->pSibling == c) return root; TreeNode<T> *p;

p = GetParent(t->pChild, c); if(p != NULL) return p; p = GetParent(t->pSibling, c); if(p != NULL) return p; }

/*定位于最左孩子*/ template<typename T>int Tree<T>::FirstChild() { if(current == NULL || current->pChild == NULL) return 0; else { current = current->pChild; return Current(current); } }

/*定位于右兄弟*/ template<typename T>int Tree<T>::NextSibling() { if(current == NULL || current->pSibling == NULL) return 0;

else { current = current->pSibling; return Current(current); } }

template<typename T>void Tree<T>::InsertChild(T value) { TreeNode<T> *newNode;

newNode = new TreeNode<T>(value); if(root == NULL) root = current = newNode; else{ if(current->pChild == NULL) current->pChild = newNode; else{ TreeNode<T> *p; p = current->pChild; while(p->pSibling != NULL) p = p->pSibling; p->pSibling = newNode; } } Current(newNode); }

/*遍历的时候虽然是遍历转换后二叉树,但是结果仍然是树的遍历*/ template<typename T>void Tree<T>::RootFistTraverse(TreeNode<T> *t) { stack<TreeNode<T>*> s; TreeNode<T> *p = t; s.Push(NULL); while(p != NULL) { cout<<p->m_Value<<'\t'; if(p->pSibling != NULL) s.Push(p); if(p->pChild != NULL) p = p->pChild; else { p = s.Pop(); if(p != NULL) p = p->pSibling; } } }

/*遍历的时候虽然是遍历转换后二叉树,但是结果仍然是树的遍历, 不要看成是二叉树的中序遍历*/ template<typename T>void Tree<T>::RootLastTraverse(TreeNode<T> *t) { stack<TreeNode<T>*> s; TreeNode<T> *p = t; while(p!=NULL || !s.IsEmpty()) { while(p!=NULL) { s.Push(p); p=p->pChild; }

p = s.Pop(); cout<<p->m_Value<<'\t'; p = p->pSibling; } }

/*层次遍历树*/ template<typename T>void Tree<T>::WidthTraverse(TreeNode<T> *t) { queue<TreeNode<T> *> Q; TreeNode<T> *p = root; if(p != NULL) { Q.EnQue(p); while(!Q.IsEmpty()) { p=Q.DeQue(); cout<<p->m_Value<<'\t'; while(p->pSibling != NULL) { if(p->pChild!=NULL) Q.EnQue(p->pChild); p = p->pSibling; cout<<p->m_Value<<'\t'; } if(p->pChild != NULL) Q.EnQue(p->pChild); } } }

/*查找当前结点前一个邻居结点的第一种方法*/ template<typename T>TreeNode<T> * Tree<T>::PrevSibling1(TreeNode<T> *t,TreeNode<T> *current) { queue<TreeNode<T> *> Q; TreeNode<T> *p = root,*prev = NULL; if((t == NULL) || (current == p) || (current == NULL)) //当前结点是根结点或者是最左孩子时,没有邻居结点 return NULL;

if(p != NULL) { Q.EnQue(p); while(!Q.IsEmpty()) { prev=NULL; p=Q.DeQue(); while(p->pSibling != NULL) { if(p->pChild!=NULL) Q.EnQue(p->pChild); prev = p; p = p->pSibling; if(p == current) return prev; } if(p->pChild != NULL) Q.EnQue(p->pChild); } } }

/*查找当前结点前一个邻居结点的第二种方法*/ template<typename T>TreeNode<T>* Tree<T>::PrevSibling2(TreeNode<T> *t,TreeNode <T> *current) { TreeNode<T> *p = root, *Prev = NULL ; queue<TreeNode<T> *> Q;

if((t == NULL) || (current == p) || (current == NULL)) return NULL;

while(p != NULL) { if(p == current) return Prev; Q.EnQue(p); Prev = p; p = p->pSibling; }

while(!Q.IsEmpty()) { Prev = NULL; p = Q.DeQue(); p = p->pChild; while(p != NULL) { if(p == current) return Prev; Q.EnQue(p); Prev = p; p = p->pSibling; }//end while }//end while }

/*删除以current为根结点的子树*/ template<typename T>void Tree<T>::DeleteSubTree(TreeNode<T> *&t) { TreeNode<T> *p = PrevSibling1(root,t); if(p == NULL) { p = GetParent(root,t); if(p!=NULL) { p->pChild = t->pSibling; t->pSibling = NULL; } else { root= t->pChild; t->pChild = NULL; } } else{ p->pSibling = t->pSibling; t->pSibling = NULL; } MakeEmpty(t); }

/*用图形显示树*/ template<typename T>void Tree<T>::PrintVTree(TreeNode<T> *t){ int screenWidth=64; int dataWidth=2; queue<TreeNode<T> *> Q; queue<Level> QI; TreeNode<T> *p; Level s,s1,s2; double offset,level=-1,i; Q.EnQue(t); s.xIndent=screenWidth/dataWidth; s.yLevel=0; QI.EnQue(s); while(!Q.IsEmpty()&&!QI.IsEmpty()) { s2=s; p=Q.DeQue(); s=QI.DeQue(); if(s.yLevel!=level) { cout<<"\n\n第"<<s.yLevel<<"层"; level=s.yLevel; for(i=0;i<s.xIndent-1;i++) cout<<" "; } else for(i=0;i<s.xIndent-s2.xIndent;i++) cout<<" "; cout<<p->m_Value; if(p->pChild!=NULL) { Q.EnQue(p->pChild); s1.yLevel=s.yLevel+1; offset=screenWidth/pow(dataWidth,s1.yLevel+1); s1.xIndent=s.xIndent-offset; QI.EnQue(s1); } if(p->pSibling!=NULL) { Q.EnQue(p->pSibling); s1.yLevel=s.yLevel+1; offset=screenWidth/pow(dataWidth,s1.yLevel+1); s1.xIndent=s.xIndent+offset; QI.EnQue(s1); } } }

template<typename T>void Tree<T>::DisplayTree() { cout<<"打印树:"<<endl; PrintVTree(root); cout<<endl<<endl; cout<<"按先根遍历树显示的结点次序为:"<<endl<<endl; RootFistTraverse(root); cout<<endl<<endl;

cout<<"按后根遍历树显示的结点次序为:"<<endl<<endl; RootLastTraverse(root); cout<<endl;

cout<<"按层次遍历树显示的结点次序为:"<<endl<<endl; WidthTraverse(root); cout<<endl;

Root(); FirstChild(); NextSibling(); NextSibling(); cout<<"显示当前结点的前一个邻居结点:"<<endl<<endl; cout<<"当前结点是:"<<current->m_Value<<endl<<endl; TreeNode<T> *p; p = PrevSibling1(root,current); cout<<"前一个邻居结点是:"<<endl; cout<<p->m_Value<<endl;

cout<<"删除当前结点为根结点的子树:"<<endl<<endl; Root(); FirstChild(); NextSibling(); cout<<"要删除以这个结点为根的子树的结点是:"<<endl; cout<<current->m_Value<<endl; DeleteSubTree(current); PrintVTree(root); cout<<endl<<endl; }

[此贴子已经被作者于2005-7-23 11:03:40编辑过]


c++/C + 汇编 = 天下无敌
2005-07-20 00:52
激情依旧
Rank: 1
等 级:新手上路
威 望:2
帖 子:524
专家分:0
注 册:2005-4-4
收藏
得分:0 
无话好说了。我写的差远了

生是编程人!!!!死是编程鬼!!!!颠峰人生!!!焚尽编程!!! 爱已严重死机!情必须重新启动!情人已和服务器断开连接!网恋也需要重新拨号!-----激情依旧
2005-07-22 09:04
激情依旧
Rank: 1
等 级:新手上路
威 望:2
帖 子:524
专家分:0
注 册:2005-4-4
收藏
得分:0 
这个是我写的。有兴趣的看看。功能当然比不上师傅写的
我把主要的算法发了出来。具体的大家下载那个rar文件来运行!!
template&lt;typename T&gt;class BTree
{private:
  BTreeNode&lt;T&gt; *root;
  void InOrder(BTreeNode&lt;T&gt; *);
  void PostOrder(BTreeNode&lt;T&gt; *);
  void PreOrder(BTreeNode&lt;T&gt; *);
  void NoReInOrder(BTreeNode&lt;T&gt; *);
  void NoRePreOrder(BTreeNode&lt;T&gt; *);
  void NoRePostOrder(BTreeNode&lt;T&gt; *);
  void LevelOrder(BTreeNode&lt;T&gt; *);
  void MakeEmpty(BTreeNode&lt;T&gt; *);
  void CountLeaf(BTreeNode&lt;T&gt; *,int &amp;);
  void NoReCountLeaf(BTreeNode&lt;T&gt; *);
  int Depth(BTreeNode&lt;T&gt; *);
 
public:
 BTree();
 ~BTree();
 BTreeNode&lt;T&gt;* Search(T &amp;);
 void InsertNode(T &amp;);
 void DeNode(T &amp;);
 void LevelOrder(){LevelOrder(root);}
 void InOrder(){InOrder(root);}
 void PostOrder(){PostOrder(root);}
 void PreOrder(){PreOrder(root);}
 void NoReInOrder(){NoReInOrder(root);}
 void NoRePreOrder(){NoRePreOrder(root);}
 void NoRePostOrder(){NoRePostOrder(root);}
 void CountLeaf();
 void NoReCountLeaf();
 int Depth(){return Depth(root);}
};
template&lt;typename T&gt;BTree&lt;T&gt;::BTree()
{
 root=NULL;
}
template&lt;typename T&gt;BTree&lt;T&gt;::~BTree()
{
 cout&lt;&lt;"析构函数执行!用非递归后序遍历删除所有节点:"&lt;&lt;endl;
 MakeEmpty(root);
}
template&lt;typename T&gt;BTreeNode&lt;T&gt;* BTree&lt;T&gt;::Search(T &amp; x)/*查找是否存在已插入节点*/
{
    BTreeNode&lt;T&gt; *p;
 p=root;
 while(p!=NULL&amp;&amp;p-&gt;data!=x)
 {
   if(p-&gt;data&gt;x)
   p=p-&gt;lchild;
  else
   p=p-&gt;rchild;
 }
 if(p==NULL)
  return NULL;
 else
  return p;
}
template&lt;typename T&gt;void BTree&lt;T&gt;::InsertNode(T &amp; x)/*生成二叉排序树*/
{
 BTreeNode&lt;T&gt; *p,*ptr=NULL;
 p=root;
 if(Search(x)==NULL)
 {
   while(p!=NULL)
     {
    ptr=p;
     if(p-&gt;data&gt;x)
     p=p-&gt;lchild;
    else
     p=p-&gt;rchild;
 }
     p=new BTreeNode&lt;T&gt;(x,NULL,NULL);
     if(p==NULL)
       {
        cout&lt;&lt;"内存不足!"&lt;&lt;endl;
         exit(1);
    }
     if(ptr==NULL)
     root=p;
     else if(ptr-&gt;data&gt;x)
     ptr-&gt;lchild=p;
     else
     ptr-&gt;rchild=p;
 }
 else
  cout&lt;&lt;x&lt;&lt;"已经存在,重复插入!"&lt;&lt;endl;
}
template&lt;typename T&gt;void BTree&lt;T&gt;::InOrder(BTreeNode&lt;T&gt; *root)/*中序递归遍历*/
{
 if(root!=NULL)
 {
  InOrder(root-&gt;lchild);
        cout&lt;&lt;root-&gt;data&lt;&lt;" ";
     InOrder(root-&gt;rchild);
 }
}
template&lt;typename T&gt;void BTree&lt;T&gt;::PreOrder(BTreeNode&lt;T&gt; *root)/*递归前序遍历*/
{
 if(root!=NULL)
 {
  cout&lt;&lt;root-&gt;data&lt;&lt;" ";
  PreOrder(root-&gt;lchild);
  PreOrder(root-&gt;rchild);
 }
}
template&lt;typename T&gt;void BTree&lt;T&gt;::PostOrder(BTreeNode&lt;T&gt; *root)/*递归后序遍历*/
{
 if(root!=NULL)
 {
  PostOrder(root-&gt;lchild);
  PostOrder(root-&gt;rchild);
  cout&lt;&lt;root-&gt;data&lt;&lt;" ";
 }
}
template&lt;typename T&gt;void BTree&lt;T&gt;::DeNode(T &amp; x)/*删除节点*/
{
 BTreeNode&lt;T&gt; *p,*ptr,*q;
    p=Search(x);
 if(p==NULL)
  cout&lt;&lt;"你要删除的节点不存在!"&lt;&lt;endl;
 else
 {
  p=root;
  ptr=root;
  while(p-&gt;data!=x)
  {
            ptr=p;
   if(p-&gt;data&gt;x)
    p=p-&gt;lchild;
   else
    p=p-&gt;rchild;
  }
  if(p-&gt;lchild==NULL&amp;&amp;p-&gt;rchild==NULL)
  {
   if(p-&gt;data&gt;ptr-&gt;data)
    ptr-&gt;rchild=NULL;
   else
    ptr-&gt;lchild=NULL;
   delete p;
  }
  else if(p-&gt;lchild!=NULL&amp;&amp;p-&gt;rchild==NULL)
  {
   if(p-&gt;data&gt;ptr-&gt;data)
    ptr-&gt;rchild=p-&gt;lchild;
   else
    ptr-&gt;lchild=p-&gt;lchild;
   delete p;
  }
  else if(p-&gt;lchild==NULL&amp;&amp;p-&gt;rchild!=NULL)
  {
   if(p-&gt;data&gt;ptr-&gt;data)
    ptr-&gt;rchild=p-&gt;lchild;
   else
    ptr-&gt;lchild=p-&gt;rchild;
   delete p;
  }
  /*else                                //要删除的节点存在左右孩子的时候。此为第1种删法
  {
   ptr=root;
   q=p-&gt;rchild;
   while(q-&gt;lchild!=NULL)
    q=q-&gt;lchild;
   p-&gt;data=q-&gt;data;
   p=p-&gt;rchild;
   while(p-&gt;lchild!=q)
    p=p-&gt;lchild;
   if(q-&gt;rchild!=NULL)
    p-&gt;lchild=q-&gt;rchild;
   else
       p-&gt;lchild=NULL;
   delete q;
  }*/
  else                             /*此为第2种删法*/
  {
   ptr=root;
   q=p-&gt;rchild;
   while(q-&gt;lchild!=NULL)
    q=q-&gt;lchild;
   q-&gt;lchild=p-&gt;lchild;
   p-&gt;lchild=NULL;
   q=root;
   while(q!=p)
   {
    ptr=q;
    if(q-&gt;data&gt;p-&gt;data)
     q=q-&gt;lchild;
    else
     q=q-&gt;rchild;
   }
   if(ptr-&gt;data==p-&gt;data)
   {
    root=p-&gt;rchild;
    p-&gt;rchild=NULL;
   }
   else if(ptr-&gt;data&gt;p-&gt;data)
    ptr-&gt;lchild=p-&gt;rchild;
   else
    ptr-&gt;rchild=p-&gt;rchild;
   p-&gt;rchild=NULL;
   delete p;
  }
 }
}
template&lt;typename T&gt;void BTree&lt;T&gt;::NoReInOrder(BTreeNode&lt;T&gt; *root)/*非递归中序遍历*/
{
 Stack&lt;BTreeNode&lt;T&gt; *&gt;S;
 BTreeNode&lt;T&gt; *p;
 p=root;
 while(p!=NULL||!S.IsEmpty())
 {
  while(p!=NULL)
  {
   S.Push(p);
   p=p-&gt;lchild;
  }
  p=S.GetTop();
     cout&lt;&lt;p-&gt;data&lt;&lt;" ";
  S.Pop();
  p=p-&gt;rchild;
 }
 cout&lt;&lt;endl;
}
template&lt;typename T&gt;void BTree&lt;T&gt;::NoRePreOrder(BTreeNode&lt;T&gt; *root)/*非递归前序遍历*/
{
 Stack&lt;BTreeNode&lt;T&gt; *&gt;S;
 BTreeNode&lt;T&gt; *p;
 p=root;
 while(p||!S.IsEmpty())
 {
  while(p!=NULL)
  {
   cout&lt;&lt;p-&gt;data&lt;&lt;" ";
   S.Push(p);
   p=p-&gt;lchild;
  }
  p=S.GetTop();
  S.Pop();
  p=p-&gt;rchild;
 }
 cout&lt;&lt;endl;
}
template&lt;typename T&gt;void BTree&lt;T&gt;::NoRePostOrder(BTreeNode&lt;T&gt; *root)/*非递归后序遍历*/
{
 Stack&lt;BTreeNode&lt;T&gt; *&gt;S;
 BTreeNode&lt;T&gt; *p;
 int tag[100],top=-1;
 p=root;
 do
 {
  while(p!=NULL)
  {
   S.Push(p);
   tag[++top]=0;
   p=p-&gt;lchild;
  }
  if(top&gt;-1)
   if(tag[top]==1)
   {
    cout&lt;&lt;S.GetTop()-&gt;data&lt;&lt;" ";
    S.Pop();
    top--;
   }
   else
   {
    p=S.GetTop();
    if(top&gt;-1)
    {
     p=p-&gt;rchild;
     tag[top]=1;
    }
   }
 }while(p!=NULL||top!=-1);
 cout&lt;&lt;endl;
}
template&lt;typename T&gt;void BTree&lt;T&gt;::LevelOrder(BTreeNode&lt;T&gt; *root)/*层次遍历*/
{
 BTreeNode&lt;T&gt; *p;
 Queue&lt;BTreeNode&lt;T&gt; *&gt;Q;
 p=root;
 Q.EnQueue(p);
 while(!Q.IsEmpty())
 {
  p=Q.DeQueue();
  cout&lt;&lt;p-&gt;data&lt;&lt;" ";
  if(p-&gt;lchild!=NULL) Q.EnQueue(p-&gt;lchild);
  if(p-&gt;rchild!=NULL) Q.EnQueue(p-&gt;rchild);
  
 }
 cout&lt;&lt;endl;
}
template&lt;typename T&gt;int BTree&lt;T&gt;::Depth(BTreeNode&lt;T&gt; *root)/*递归求二叉树的深度*/
{
 int depthleft,depthright,depthval;
 if(root==NULL)
  return 0;
 else
 {
  depthleft=Depth(root-&gt;lchild);
  depthright=Depth(root-&gt;rchild);
  depthval=1+(depthleft&gt;depthright?depthleft:depthright);
 }
 return depthval;
}
template&lt;typename T&gt;void BTree&lt;T&gt;::MakeEmpty(BTreeNode&lt;T&gt; *root)/*用非递归后序遍历来删除所有节点*/
{
 int tag[50],top=-1;
 BTreeNode&lt;T&gt; *p,*q,*temp;
 Stack&lt;BTreeNode&lt;T&gt; *&gt;S;
 p=root;
 do
 {
  while(p!=NULL)
  {
   S.Push(p);
   tag[++top]=0;
   p=p-&gt;lchild;
  }
  if(top&gt;-1)
   if(tag[top]==1)
   {
    q=S.GetTop();
    S.Pop();
    top--;
    if(!S.IsEmpty())
    {
     temp=S.GetTop();
        if(temp-&gt;lchild==q)
      temp-&gt;lchild=NULL;
        else
         temp-&gt;rchild=NULL;
     cout&lt;&lt;q-&gt;data&lt;&lt;" ";
        delete q;
    }
    else
    {
     cout&lt;&lt;q-&gt;data&lt;&lt;" ";
     delete root;
    }
   }
   else
   {
    p=S.GetTop();
    if(top&gt;-1)
    {
     p=p-&gt;rchild;
     tag[top]=1;
    }
   }
 }while(p!=NULL||top!=-1);
 cout&lt;&lt;endl;
}
template&lt;typename T&gt;void BTree&lt;T&gt;::CountLeaf()/*调用CountLeaf(root,count)函数*/
{
 int count=0;
 cout&lt;&lt;"叶节点为:"&lt;&lt;endl;
 CountLeaf(root,count);
 cout&lt;&lt;endl;
 cout&lt;&lt;"叶节点的个数为:"&lt;&lt;count&lt;&lt;endl;
}
template&lt;typename T&gt;void BTree&lt;T&gt;::CountLeaf(BTreeNode&lt;T&gt; *root,int &amp;count)/*递归求叶节点个数*/
{
 if(root!=NULL)
 {
  CountLeaf(root-&gt;lchild,count);
  CountLeaf(root-&gt;rchild,count);
  if(root-&gt;lchild==NULL&amp;&amp;root-&gt;rchild==NULL)
  {
   count++;
   cout&lt;&lt;root-&gt;data&lt;&lt;" ";
  }
 }
}
template&lt;typename T&gt;void BTree&lt;T&gt;::NoReCountLeaf()
{
 cout&lt;&lt;"叶节点为:"&lt;&lt;endl;
 NoReCountLeaf(root);
}
template&lt;typename T&gt;void BTree&lt;T&gt;::NoReCountLeaf(BTreeNode&lt;T&gt; *root)
{
 Stack&lt;BTreeNode&lt;T&gt; *&gt;S;
 BTreeNode&lt;T&gt; *p,*temp;
 int tag[100],top=-1,count=0;
 p=root;
 do
 {
  while(p!=NULL)
  {
   S.Push(p);
   tag[++top]=0;
   p=p-&gt;lchild;
  }
  if(top&gt;-1)
   if(tag[top]==1)
   {
    temp=S.GetTop();
    S.Pop();
    top--;
    if(temp-&gt;lchild==NULL&amp;&amp;temp-&gt;rchild==NULL)
    {
     cout&lt;&lt;temp-&gt;data&lt;&lt;" ";
     count++;
    }
   }
   else
   {
    p=S.GetTop();
    if(top&gt;-1)
    {
     p=p-&gt;rchild;
     tag[top]=1;
    }
   }
 }while(p!=NULL||top!=-1);
 cout&lt;&lt;endl;
 cout&lt;&lt;"叶节点的个树为:"&lt;&lt;count&lt;&lt;endl;
}

HGk6D87o.rar (13.06 KB) 二叉树完整试用版(功能会不断更新)


生是编程人!!!!死是编程鬼!!!!颠峰人生!!!焚尽编程!!! 爱已严重死机!情必须重新启动!情人已和服务器断开连接!网恋也需要重新拨号!-----激情依旧
2005-07-22 09:08
热情依然
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:715
专家分:0
注 册:2005-4-5
收藏
得分:0 
明天我会更新这个文件,加入树的建立跟遍历,动态左孩子/右孩子表示法,还有删除当前结点为根结点的子树。

c++/C + 汇编 = 天下无敌
2005-07-22 22:40
热情依然
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:715
专家分:0
注 册:2005-4-5
收藏
得分:0 

#include "binarytree.h" #include "tree.h"

void main() { BinaryTree<int> b;

BinaryTree<char>b1;

Tree<char> t;

int change; while(1) { cout<<"请选择:"<<endl<<endl; cout<<"(1)建立二叉树:"<<endl<<endl;

cout<<"(2)建立二树:"<<endl<<endl;

cout<<"(3)帮助:"<<endl<<endl;

cout<<"(4)退出:"<<endl<<endl;

cin>>change;

if(change == 4)

break;

switch(change) { case 1:

while(1) { cout<<endl;

cout<<"选择建立二叉树的方法:"<<endl<<endl; cout<<"(1)用嵌套括号表示法建立二叉树:"<<endl<<endl;

cout<<"(2)建立满二叉树:"<<endl<<endl;

cout<<"(3)建立排序二叉树:"<<endl<<endl;

cout<<"(4)用中序周游跟前序周游建立二叉树:"<<endl<<endl; cout<<"(5)帮助:"<<endl<<endl; cout<<"(6)退出:"<<endl<<endl;

cin>>change;

cout<<endl;

if(change==6)

break;

char str[255]; int c=0,depth,i,j=0,k=0,sum=0,z=0,end[255],flag;

switch(change) {

case 1:

cout<<"输入字符以等号结束:"<<endl;

for(i=0;i<255;i++) { cin>>str[i]; if(str[i]==''='') break; } str[i]=''\0''; flag=1; b1.creatpackettree(str); break;

case 2: cout<<"输入数字以等号结束:"<<endl;

for(i=0;i<255;i++) { cin>>str[i]; if(str[i]==''='') break; } str[i]=''\0''; i=0; while(str[k]!=''\0'') { if(str[j]=='',''||str[j]==''\0'') { for(k=i;k<j;k++) sum=sum*10+str[k]-''0''; end[z++]=sum; sum=0; i=j+1; } if(str[j]!=''\0'') j++; } end[z]=''\0''; flag=2; b.m_creatbrinarytree(end,z); break; case 3:

cout<<"输入数字以等号结束:"<<endl;

for(i=0;i<255;i++) { cin>>str[i]; if(str[i]==''='') break; } str[i]=''\0''; i=0;

while(str[k]!=''\0'') { if(str[j]=='',''||str[j]==''\0'') { for(k=i;k<j;k++) sum=sum*10+str[k]-''0''; end[z++]=sum; sum=0; i=j+1; } if(str[j]!=''\0'') j++; } end[z]=''\0''; flag=3; for(j=0;j<z;j++) b.CreatTree(end[j]); break;

case 4:

char pre[255],in[255];

int i;

cout<<"输入前序周游:"<<endl<<endl;

cout<<"输入字符以等号结束:"<<endl<<endl;

for(i=0;i<255;i++) { cin>>pre[i]; if(pre[i]==''='') break; } pre[i]=''\0''; cout<<"输入中序周游:"<<endl<<endl;

cout<<"输入字符以等号结束:"<<endl<<endl;

for(i=0;i<255;i++) { cin>>in[i]; if(in[i]==''='') break; } in[i]=''\0'';

flag=1; b1.pre_and_in_creatbinary(pre,in,strlen(pre));

break;

case 5: cout<<"帮助:"<<endl<<endl;

cout<<"当你选择用嵌套括号表示法建立二叉树时,只能输入英文字符."<<endl<<endl; cout<<"输入格式:例如 a(b,c)="<<endl<<endl;

cout<<"当你选择排序二叉树或者满二叉树时,只能输入数字字符."<<endl<<endl; cout<<"输入格式:例如 12,3,2,6,7,="<<endl<<endl;

cout<<"当你选择用中序周游跟前序周游建立二叉树时,只能输入英文字符."<<endl<<endl;

cout<<"输入格式:例如:前序:a,b,c,= 中序:b,a,c,= "<<endl<<endl;

cout<<"注意:注意只有选择建立排序二叉树才可以进行删除."<<endl<<endl;

continue;

break; } while(1) { cout<<endl; cout<<"请选择:"<<endl<<endl; cout<<"(1)打印二叉树:"<<endl<<endl;

cout<<"(2)凹凸表示法:"<<endl<<endl; cout<<"(3)嵌套扩号表示法:"<<endl<<endl;

cout<<"(4)非递归前序周游:"<<endl<<endl;

cout<<"(5)非递归中序周游:"<<endl<<endl;

cout<<"(6)非递归后序周游:"<<endl<<endl;

cout<<"(7)非递归层次周游:"<<endl<<endl;

cout<<"(8)二叉树叶结点个数:"<<endl<<endl;

cout<<"(9)用队列求二叉树深度"<<endl<<endl;

cout<<"(10)用栈求二叉树深度:"<<endl<<endl;

cout<<"(11)中序线索二叉树:"<<endl<<endl;

cout<<"(12)排序二叉树删除指定结点:"<<endl<<endl;

cout<<"(13)改进的二叉排序树删除结点:"<<endl<<endl;

cout<<"(14)打印指定结点的全部祖先:"<<endl<<endl; cout<<"(15)打印指定两个结点的最近祖先和彼此之间的距离:"<<endl<<endl;

cout<<"(16)改进的非递归前序遍历:"<<endl<<endl; cout<<"(17)退出"<<endl<<endl; cin>>change;

if(change==17)

break;

switch(change) { case 1:

if(flag==2||flag==3){

cout<<"\n"<<"打印二叉树:"<<endl<<endl; b.PrintVTree(); } else if(flag==1){

cout<<"\n"<<"打印二叉树:"<<endl<<endl; b1.PrintVTree(); } cout<<endl<<endl;

break; case 2:

if(flag==2||flag==3){

cout<<"\n"<<"凹凸表示法:"<<endl<<endl; b.PrinTree(); } else if(flag==1){

cout<<"\n"<<"凹凸表示法:"<<endl<<endl;

b1.PrinTree(); } cout<<endl<<endl; break;

case 3:

if(flag==2||flag==3){

cout<<"\n"<<"嵌套扩号表示法:"<<endl<<endl;

b.PackOrder(); } if(flag==1){

cout<<"\n"<<"嵌套扩号表示法:"<<endl<<endl;

b1.PackOrder(); } cout<<endl<<endl; break;

case 4:

if(flag==2||flag==3){

cout<<"\n"<<"非递归前序周游:"<<endl<<endl;

b.PreOrder(); } if(flag==1){

cout<<"\n"<<"非递归前序周游:"<<endl<<endl; b1.PreOrder(); } cout<<endl<<endl;

break;

case 5:

if(flag==2||flag==3){

cout<<"\n"<<"非递归中序周游:"<<endl<<endl;

b.InOrder(); } if(flag==1){

cout<<"\n"<<"非递归中序周游:"<<endl<<endl;

b1.InOrder(); } cout<<endl<<endl;

break;

case 6:

if(flag==2||flag==3){

cout<<"\n"<<"非递归后序周游:"<<endl<<endl;

b.PostOrder(); } if(flag==1){

cout<<"\n"<<"非递归后序周游:"<<endl<<endl;

b1.PostOrder(); } cout<<endl<<endl;

break;

case 7:

if(flag==2||flag==3){

cout<<"\n"<<"非递归层次周游:"<<endl<<endl;

b.COrder(); } if(flag==1){ cout<<"\n"<<"非递归层次周游:"<<endl<<endl; b1.COrder(); } cout<<endl<<endl; break;

case 8:

if(flag==2||flag==3){

cout<<"\n"<<"二叉树叶结点个数:"<<endl<<endl;

b.Countleaf(c);

cout<<c; } if(flag==1){ cout<<"\n"<<"二叉树叶结点个数:"<<endl<<endl;

b1.Countleaf(c);

cout<<c; } cout<<endl<<endl;

break;

case 9:

if(flag==2||flag==3){

cout<<"\n"<<"用队列求二叉树深度"<<endl<<endl;

depth=b.Depth_queue(); } if(flag==1){

cout<<"\n"<<"用队列求二叉树深度"<<endl<<endl;

depth=b1.Depth_queue(); } cout<<depth<<endl<<endl;

break; case 10:

if(flag==2||flag==3){

cout<<"\n"<<"用栈求二叉树深度"<<endl<<endl;

depth=b.Depth_stack();

} if(flag==1){

cout<<"\n"<<"用栈求二叉树深度"<<endl<<endl;

depth=b1.Depth_stack(); } cout<<depth<<endl<<endl;

break;

case 11:

if(flag==2||flag==3) b.InThread();

if(flag==1)

b1.InThread();

while(1) {

cout<<"请选择:"<<endl<<endl;

cout<<"(1)中序线索周游二叉树:"<<endl<<endl;

cout<<"(2)在中序线索二叉树中找指定结点在前序下的后缀:"<<endl<<endl;

cout<<"(3)在中序线索二叉树中找指定结点在后序下的前驱:"<<endl<<endl;

cout<<"(4)后序周游中序线索二叉树:"<<endl<<endl;

cout<<"(5)在中序线索二叉树中插入结点:"<<endl<<endl; cout<<"(6)退出:"<<endl<<endl; cin>>change;

if(change==6) { if(flag==2||flag==3)

b.MakeEmpty();

if(flag==1)

b1.MakeEmpty();

exit(1); }

switch(change) { case 1: if(flag==2||flag==3) { cout<<"中序线索周游二叉树:"<<endl<<endl;

b.In_thread_Order();

cout<<endl<<endl; } if(flag==1) { cout<<"中序线索周游二叉树:"<<endl<<endl;

b1.In_thread_Order();

cout<<endl<<endl; }

break; case 2: if(flag==2||flag==3) { cout<<"在中序线索二叉树中找指定结点在前序下的后缀:"<<endl<<endl; int data; cout<<"输入指定的结点:"<<endl<<endl; cin>>data; b.FindNextinInorderTree(data); } if(flag==1) { cout<<"在中序线索二叉树中找指定结点在前序下的后缀:"<<endl<<endl; char data; cout<<"输入指定的结点:"<<endl<<endl; cin>>data; b1.FindNextinInorderTree(data); } break; case 3: if(flag==2||flag==3) { cout<<"在中序线索二叉树中找指定结点在后序下的前驱:"<<endl<<endl; int data; cout<<"输入指定的结点:"<<endl<<endl; cin>>data; b.FindBeforeinInorderTree(data); } if(flag==1) { cout<<"在中序线索二叉树中找指定结点在后序下的前驱:"<<endl<<endl; char data; cout<<"输入指定的结点:"<<endl<<endl; cin>>data; b1.FindBeforeinInorderTree(data); } break; case 4:

if(flag==2||flag==3) { cout<<"后序周游中序线索二叉树:"<<endl<<endl;

b.Post_Thread_Order();

cout<<endl<<endl; } if(flag==1) { cout<<"后序周游中序线索二叉树:"<<endl<<endl;

b1.Post_Thread_Order();

cout<<endl<<endl; }

break; case 5:

if(flag==2||flag==3) { cout<<"在中序线索二叉树中插入结点:"<<endl<<endl;

int find_data,insert_data;

cout<<"输入线索二叉树中任意一个存在结点的值:"<<endl;

cin>>find_data;

cout<<"输入新插入结点的值:"<<endl;

cin>>insert_data;

b.InsertNode_in_Inthread(find_data,insert_data); }

if(flag==1) { cout<<"在中序线索二叉树中插入结点:"<<endl<<endl;

char find_data,insert_data;

cout<<"输入线索二叉树中任意一个存在结点的值:"<<endl;

cin>>find_data;

cout<<"输入新插入结点的值:"<<endl;

cin>>insert_data;

b1.InsertNode_in_Inthread(find_data,insert_data); }

break; }

} break; case 12: if(flag==3) { cout<<"输入指定结点:"<<endl;

int del_data;

cin>>del_data;

b.Del_BinaryTreeNode(del_data);

cout<<"显示删了结点的二叉树"<<endl;

b.PrintVTree();

cout<<endl; }

if(flag==1||flag==2) { cout<<"不可以进行删除"<<endl; } break; case 13: if(flag==3) { cout<<"输入指定结点:"<<endl;

int del_data;

cin>>del_data;

b.Del_BinaryTreeNode_EX(del_data);

cout<<"显示删了结点的二叉树"<<endl;

b.PrintVTree();

cout<<endl; }

if(flag==1||flag==2) { cout<<"不可以进行删除"<<endl; } break;

case 14:

if(flag==2||flag==3) { cout<<"输入指定结点:"<<endl;

int ancestor_data;

cin>>ancestor_data;

b.Ancestor(ancestor_data);

}

if(flag==1) { cout<<"输入指定结点:"<<endl;

char ancestor_data;

cin>>ancestor_data;

b1.Ancestor(ancestor_data);

} break;

case 15:

if(flag==2||flag==3) { cout<<"输入两个指定结点(要从左子树输如,否则不能正确找出):"<<endl;

int ancestor_data1,ancestor_data2;

cin>>ancestor_data1>>ancestor_data2;

b.Closed_Ancestor(ancestor_data1,ancestor_data2);

}

if(flag==1) { cout<<"输入两个指定结点(要从左子树输如,否则不能正确找出):"<<endl;

char ancestor_data1,ancestor_data2;

cin>>ancestor_data1>>ancestor_data2;

b1.Closed_Ancestor(ancestor_data1,ancestor_data2); } break;

case 16:

if(flag==2||flag==3) { cout<<"改进的非递归前序遍历:"<<endl;

b.PreOrder_Ex();

}

if(flag==1) { cout<<"改进的非递归前序遍历:"<<endl;

b1.PreOrder_Ex();

}

break; } } } break; case 2: t.InsertChild(''A''); for(int i=0;i<3;i++) { t.Root(); t.InsertChild(''B''+i); } for(i=0;i<2;i++) { t.Root(); t.FirstChild(); t.InsertChild(''E''+i); } t.DisplayTree(); break;


c++/C + 汇编 = 天下无敌
2005-07-23 11:31
热情依然
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:715
专家分:0
注 册:2005-4-5
收藏
得分:0 

} } } break; case 2: t.InsertChild('A'); for(int i=0;i<3;i++) { t.Root(); t.InsertChild('B'+i); } for(i=0;i<2;i++) { t.Root(); t.FirstChild(); t.InsertChild('E'+i); } t.DisplayTree(); break;

case 3: cout<<endl; cout<<"说明:"<<endl; cout<<"由于本人水平问题,导致建立树(动态左孩子/右孩子)表示法不能动态输入,"<<endl<<endl; cout<<"只能在程序中调用Root(),FirstChild()等函数来移动指针。希望其他高手"<<endl<<endl; cout<<"可以帮我改进.二叉树可以动态的输入,大家可以放心的使用."<<endl<<endl;

break;

} } }


c++/C + 汇编 = 天下无敌
2005-07-23 11:32
快速回复:树跟二叉树完整试用版
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.028592 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved