注册 登录
编程论坛 → 数据结构与算法

树跟二叉树完整试用版

热情依然 发布于 2005-07-20 00:25， 21938 次点击
只有本站会员才能查看附件，请 登录

//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编辑过]

79 回复
#52
lcoal2006-09-04 23:29
哇,好期待终极版啊,这个2叉树看到我眼睛都花了!幸好有个文件!
#53
carencpp2006-09-05 18:00
ddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
ddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
ddddddddddd ddddddddddddddddd ddddddddddddd
ddddddddddddddddd ddddddddddddddddddddddddddddddd ddddddddddddddddddddddddd
ddddddddddddddddd dddddddddddddddddddddddddddddd dddddddddddddddddddddddddd
ddddddddddddddddd ddddddddddddddddddddddddddddd ddddddddddddddddddddddddddd
ddddddddddddddddd dddddddddddddddddddddddddddd dddddddddddddddddddddddddddd
ddddddddddddddddd ddddddddddddddddddddddddddd d dddddddddddddddd
ddddddddddddddddd dddddddddddddddddddddddddd dd ddd ddd dddddddddddddddd
ddddddddddddddddd ddddddddddddddddddddddddd ddd ddd ddd dddddddddddddddd
ddddddddddddddddd dddddddddddddddddddddddddddddd ddd ddd dddddddddddddddd
ddddddddddddddddd dddddddddddddddddddddddddddddd ddd ddd dddddddddddddddd
ddddddddddddddddd dddddddddddddddddddddddddddddd ddd ddd dddddddddddddddd
ddddddddddddddddd dddddddddddddddddddddddddddddd d dd d dddddddddddddddd
ddddddddddddddddd dddddddddddddddddddddddddddddddd dddd dddddddddddddddddd
ddddddddddd dddd ddddddddddddddddddddddddddddddd dddddd ddddddddddddddddd
ddddddddddddd dd dddddddddddddddddddddddddddddd dddddddd dddddddddddddddd
ddddddddddddddd ddddddddddddddddddddddddddddd dddddddddd ddddddddddddddd
ddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
ddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
ddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
ddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
#54
stnlcd2006-10-23 15:19
既然做成了template，那么就是想让下载的人当作通用模板在自己的工程中使用，但是否考虑到，如果用户Include了你的头文件只是用了里面几个函数功能而已，比如建树和遍历树，却要把那么大的一个文件包含进去，用户的代码量会大增，有可能原来的exe文件只有10k，但由于加入了你的文件就变成了100k甚至更多。一个树尚且如此，如果在加上链表，队列，栈，图那些，恐怕要很大喽。
既然要做成一个软件工具样式，标准的做法都要加上编译开关，可以让用户选择包含文件的大小
还有，建议把binarytree.h分成binarytree.h和binarytree.cpp两部分，原因是:1,很少有把那么多操作都放在.h内。2,楼主的.h文件内很难分清那些是接口和实现，不知道demo的时候，.h大类让人看了就打醋，这样还想用吗?把.h文件放置接口，把.cpp放置实现，是软件工程的需要，比如windows内大部分文件和mfc代码等
当然，必须承认：楼主的编程功底还是深厚的
#55
hc430078792006-10-25 11:49

很好。
#56
热情依然2006-10-27 13:07
以下是引用stnlcd在2006-10-23 15:19:00的发言：
既然做成了template，那么就是想让下载的人当作通用模板在自己的工程中使用，但是否考虑到，如果用户Include了你的头文件只是用了里面几个函数功能而已，比如建树和遍历树，却要把那么大的一个文件包含进去，用户的代码量会大增，有可能原来的exe文件只有10k，但由于加入了你的文件就变成了100k甚至更多。一个树尚且如此，如果在加上链表，队列，栈，图那些，恐怕要很大喽。
既然要做成一个软件工具样式，标准的做法都要加上编译开关，可以让用户选择包含文件的大小
还有，建议把binarytree.h分成binarytree.h和binarytree.cpp两部分，原因是:1,很少有把那么多操作都放在.h内。2,楼主的.h文件内很难分清那些是接口和实现，不知道demo的时候，.h大类让人看了就打醋，这样还想用吗?把.h文件放置接口，把.cpp放置实现，是软件工程的需要，比如windows内大部分文件和mfc代码等
当然，必须承认：楼主的编程功底还是深厚的

你说的不错,哈哈,我写这个代码的时候还是很弱的,这个是很久之前的代码吧,C++才学了几个月,那个时候<<c++ primer>>都没有看过,那个时候我是大二,现在出来工作了
#57
dndyh2006-10-30 15:25

求助!
什么是均衡二叉树?
#58
dndyh2006-10-30 15:28
回复帖子,请发到qq:599155530.
#59
homer2005nh2006-11-15 22:34
可以用不哟
#60
与寻2006-11-22 19:52
    呵呵  俺呀 一点都不懂  不过还知道是C++  呵呵   路还长着呢
#61
etilm2006-12-07 17:16
看的头晕,不要说叫我写了
#62
riyuelang2007-01-01 00:07
好长呀　感受到压力
#63
臥龍孔明2007-01-19 16:54
#64
huangjh6302007-01-21 16:34

好长 得花蛮多时间看``先顶下
#65
huangjh6302007-01-21 16:34
好长 得花蛮多时间看``先顶下
#66
huangjh6302007-01-21 16:35
不好意思 多发了一次````
#67
wjtpanda2007-02-02 19:12
lz强
#68
wenzenglin2007-03-09 23:11

下了那个RAR,解压后一运行,有一个错误

只有本站会员才能查看附件，请 登录
#69
热情依然2007-04-26 21:10

那个是VC 6.0的问题,你可以在之前加多个定义,VC 6.0不支持标准C++
#70
热情依然2007-04-26 21:13

请大家使用 支持标准C++的编译器来编译本程序
#71
kimiair2007-05-08 12:08
你们好强悍啊~在下佩服佩服~
#72
songyuyu2007-05-16 15:01
不错
#73
gangan2007-05-21 08:45

下了~看看~
#74
qqwuming2007-06-15 13:35
kankan
#75
jsxxyzx2007-06-19 08:23
好多高手啊，小弟是刚刚学编程的，现在遇到一个树的应用问题
要求：实现树和二叉树的转换，以及树的前序，后序的递归，层次序的递归算法的实现，应包含建树的实现
希望高手们帮帮忙，给个原代码，小弟不甚感激！！！！！！！！！！
#76
jsxxyzx2007-06-19 08:25
要求是用c或是c++实现
#77
lj落叶2007-06-21 13:31
请问该如何有c语言实现普通树的清空，构造，销毁以及初始化的基本操作，（用二叉链表实现），谢谢……
#78
maozhong892007-06-22 01:32
回复：（热情依然）树跟二叉树完整试用版

lz实在太强了，看的我晕了！！！问下有平衡二叉数的程序没呀？
#79
s7788992007-07-02 16:05
#80
ruguokeyi1102010-05-16 23:49
好厉害····
12
©2025, BC-CN.NET
电脑版