| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2107 人关注过本帖
标题:平衡二叉树[原创]
只看楼主 加入收藏
kings169524
Rank: 1
等 级:新手上路
帖 子:17
专家分:0
注 册:2005-5-5
收藏
 问题点数:0 回复次数:9 
平衡二叉树[原创]

这个东东就是要花一点时间画图研究。 以下是我的代码。 写得差请见谅 #include <status.h>

typedef struct BT{ int data; struct BT* l; struct BT* r; int bl; BT(int d); }BT;

BT::BT(int d){ l=r=NULL; data=d; bl=0; }

void clear(BT* p){ if(p){ clear(p->l); clear(p->r); delete(p); } }

void print(BT* p){ cout<<"data="<<p->data<<'\t'<<"bl="<<p->bl<<endl; }

void f_p(BT* T){ if(T!=NULL){ print(T); f_p(T->l); f_p(T->r); } }

void m_p(BT* T){ if(T!=NULL){ m_p(T->l); print(T); m_p(T->r); } }

void Trans(BT* T){ cout<<"\nfront trans:\n"; f_p(T); cout<<endl; cout<<"\nmid trans:\n"; m_p(T); cout<<endl; }

void Rotate_1(BT* &p){ BT* T=p->l; p->bl=0; T->bl=0; p->l=T->r; T->r=p; p=T; }

void Rotate_2(BT* &p){ BT* T=p->l->r; if(T->bl==0){ p->l->bl=p->bl=0; } else{ if(T->bl==1){ p->bl=-1; } else{ p->l->bl=1; } } p->l->r=T->l; T->l=p->l; p->l=T->r; T->r=p; p=T; }

void Rotate_3(BT* &p){ BT* T=p->r; p->bl=T->bl=0; p->r=T->l; T->l=p; p=T; }

void Rotate_4(BT* &p){ BT* T=p->r->l; if(T->bl==0){ p->r->bl=p->bl=0; } else{ if(T->bl==1){ p->r->bl=-1; } else{ p->bl=1; } } p->r->l=T->r; T->r=p->r; p->r=T->l; T->l=p; p=T; }

void Avl_Tree(BT* &p){ if(p->bl==2){ if(p->l->bl==1) Rotate_1(p); else Rotate_2(p); } else{ //p->bl==-2 if(p->r->bl==-1) Rotate_3(p); else Rotate_4(p); } }

status _Insert(int d,BT* &p,short int &f,short int &af){ if(!p){ p=new BT(d); f=SUCCESS; return TRUE; } else{ if(d>p->data){ if(_Insert(d,p->l,f,af)){ if(!p->r) af=TRUE; else{ af=FALSE; p->bl++; } } if(af==TRUE){ p->bl++; if(p->bl==2){ Avl_Tree(p); af=FALSE; } } } else if(d<p->data){ if(_Insert(d,p->r,f,af)){ if(!p->l) af=TRUE; else{ af=FALSE; p->bl--; } } if(af==TRUE){ p->bl--; if(p->bl==-2){ Avl_Tree(p); af=FALSE; } } } else{ f=FAILE; } return FALSE; } }

status Insert(int d,BT* &p){ short int f=SUCCESS; short int af=FALSE; _Insert(d,p,f,af); return f; }

void t1(){ BT* p=NULL; int d=1; cout<<"insert data="; cin>>d; while(d!=0){ if(Insert(d,p)) cout<<"\tInsert success"<<endl; else cout<<"\tInsert failed"<<endl; cout<<"insert data="; cin>>d; } Trans(p); getch(); clear(p); }

void main(){ t1(); }

搜索更多相关主题的帖子: 二叉树 
2005-05-06 15:09
玩偶
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2005-3-9
收藏
得分:0 
楼主的头文件是自己写的吧??

程序认识我,我不认识程序!
2005-09-15 11:30
witchery
Rank: 1
来 自:西安
等 级:新手上路
帖 子:205
专家分:0
注 册:2005-8-6
收藏
得分:0 
什么是"二叉树" , 讲解一下吧. 初学者 不太了解
2005-09-16 20:18
slp001002
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2005-12-8
收藏
得分:0 
&lt;status.h&gt;

2005-12-08 12:26
slp001002
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2005-12-8
收藏
得分:0 
&lt;status.h&gt;是个头文件吧,在Visual C++执行中应该写清楚&lt;status.h&gt;原代码吧

2005-12-08 12:28
ElfDN
Rank: 4
等 级:贵宾
威 望:11
帖 子:291
专家分:0
注 册:2005-11-13
收藏
得分:0 

晕,怎么不用递归?
斑竹,一起来帮忙优化


2005-12-09 14:32
benter
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2005-12-11
收藏
得分:0 
楼主上传一下头文件塞
2005-12-11 18:10
nqq622
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2006-1-4
收藏
得分:0 
2006-05-17 10:58
ltxbs81
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2010-4-23
收藏
得分:0 
诸位好,小弟遇到了一道难题:
已知某排序平衡二叉树T具有下列特点:
(1)结点的关键字均在1到9范围为内;
(2)在T中存在一个关键字为n1的叶结点,若删去该结点,立即插入一个关键字为n1的结点,得到的平衡树与原T不同;
(3)在T中存在一个关键字为n2的非叶结点,若删去该结点,立即插入n2结点,得到与原T相同的平衡树;
(4)在T中插入某n3结点并立即删去它,得到的平衡树与原T不同。
试通过程序输出具有上述特点的最简单(结点个数最少)的平衡二叉树T,并写明n1,n2,n3分别等于几?
恳请大家帮忙解决,谢谢!
2010-05-06 00:38
菜鸟,求帮忙
Rank: 4
等 级:业余侠客
帖 子:197
专家分:267
注 册:2015-7-11
收藏
得分:0 
二叉树哪位讲解一下
2015-07-15 15:49
快速回复:平衡二叉树[原创]
数据加载中...
 
   



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

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