平衡二叉树的 *** 作（高手进）

以前做的。
一、 需求分析
1． 本程序是是利用平衡二叉树实现一个动态查找表，实现动态查找表的三种基本功能：查找、插入和删除。
2． 初始，平衡二叉树为空树，可以按先序输入平衡二叉树，以输入0结束，中间以回车隔开，创建好二叉树后，可以对其查找，再对其插入，输入0结束插入，再可以对其删除，输入0结束，每次插入或删除一个结点后，更新平衡二叉树的显示。
3． 本程序以用户和计算机的对话方式执行，根据计算机终端显示：“提示信息”下，用户可由键盘输入要执行的 *** 作。
4． 测试数据（附后）
二、 概要设计
1． 抽象数据类型动态查找表的定义如下：
ADT DynamicSearchTable{
数据结构D：D是具有相同特性的数据元素的集合。各个数据元素含有类型相同，可惟一标识数据元素的关键字。
数据关系R：数据元素同属一个集合。
基本 *** 作P：
InitDSTable(&DT);
*** 作结果：构造一个空的动态查找表DT。
DestroyDSTable(&DT);
初试条件：动态查找表DT存在。
*** 作结果: 销毁动态查找表DT。
SearchDSTable(DT,key);
初试条件：动态查找表DT存在，key为和关键字类型相同的给定值。
*** 作结果: 若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或表中的位置，否则为“空”。
InsertDSTable(&DT,e);
初试条件：动态查找表DT存在，e为待插入的数据元素。
*** 作结果: 若DT中不存在其关键字等于e key的数据元素，则插入e到DT。
DeleteDSTable(&DT,key);
初试条件：动态查找表DT存在，key为和关键字类型相同的给定值。
*** 作结果: 若DT中存在其关键字等于key的数据元素，则删除之。
TraverseDSTable(DT,Visit());
初试条件：动态查找表DT存在，Visit()是结点 *** 作的应用函数。
*** 作结果: 按某种次序对DT的每个结点调用函数Visit()一次且至多
一次。一但Visit()失败，则 *** 作失败。
}ADT DynamicSearchTable
2． 本程序包含两个模块：
Void main(){
Do{
接受命令（根据提示输入终点城市和起点城市的序号）；
处理命令；
}while(“命令”=“退出”)；
}
3．本程序只有两个模块，调用关系简单
主程序模块
平衡二叉树的模块
三、 详细设计
1． 根据题目要求和查找的基本特点，其结点类型
typedef struct BSTnode{
int data;
int bf;
struct BSTnode lchild,rchild;
}BSTnode,bstree;
#define LH +1
#define EH 0
#define RH -1
/-----------------------------对平衡二叉树的 *** 作
bstree InsertAVL(bstree &T, int e)；
////////在平衡二叉树中插入结点。
int FindAVL(bstree p,int e)；
////////查找平衡二叉树中是否有结点e。
bstree DeleteAVL(bstree &T,int e)
////////删除平衡平衡二叉树的结点e，并保持平衡二叉树的性质。
int Preordertraverse(bstree T)
////////按先序遍历平衡二叉树。
/------------------------平衡二叉树的 *** 作的详细算法
bstree InsertAVL(bstree &T, int e)
{
bstree p;
//插入新结点，树长高置taller为TRUE
if(!T) {
T=(bstree)malloc(sizeof(BSTnode));
T->data=e;
T->lchild=T->rchild=NULL;
T->bf=EH;
taller=TRUE;
}
else {
//树中存在和e有相同关键字的结点则不再插入
if(e==T->data){
taller=FALSE;
return NULL;
}
//值小于则继续在树的左子树中搜索
if(e < T->data){
//插入到左子树且左子树长高
p=InsertAVL(T->lchild,e);
if(p){
T->lchild=p;
if(taller) {
switch(T->bf){ //检查T的平衡度
case LH: //原本左子树比右子树高，需要做左平衡处理
T=LeftBalance(T);
taller=FALSE;
break;
case EH: //原本左子树和右子树同高，现因左子树争高而使树增高
T->bf=LH;
taller=TRUE;
break;
case RH: //原本右子树比左子树高，现在左右子树等高
T->bf=EH;
taller=FALSE;
break;
}///////switch(T->bf)
}///////if(taller)
}/////if(p)
}///////if(e < T->data)
//继续在T的右子树中搜索
else{
//插入到右子树且使右子树长高
p=InsertAVL(T->rchild,e);
if (p){
T->rchild=p;
if(taller) {
switch(T->bf){ //检查T的平衡度
case LH: //原本左子树比右子树高，现在左右子树等高
T->bf=EH;
taller=FALSE;
break;
case EH: //原本左子树和右子树同高，现因右子树增高而使树增高
T->bf=RH;
taller=TRUE;
break;
case RH: //原本右子树比左子树高，需要做右平衡处理
T=RightBalance(T);
taller=FALSE;
break;
}//////switch(T->bf)
}/////if(taller)
}/////if (p)
}//////if(e > T->data)
}///////else
return T;
}
int Preordertraverse(bstree T){
if(T){
printf(" %d %d\n",T->data,T->bf);
Preordertraverse(T->lchild);
Preordertraverse(T->rchild);
}
return 1;
}
int FindAVL(bstree p,int e){
if(p==NULL)return NULL;
else if(e==p->data) return true;
else if(e<p->data){
p=p->lchild;
return FindAVL(p, e);
}////左子树上查找
else {
p=p->rchild;
return FindAVL( p, e);
}////右子树上查找
}
bstree DeleteAVL(bstree &T,int e){
//删除后要保证该二叉树还是平衡的
int n,m=0;/////标记
bstree q;
if(!T)return NULL;
else {
if(e==T->data) {////直接删除
n=Delete(T,e);
m=n;
if(m!=0) {
q=T;
DeleteAVL(T,m);
q->data=m;}
}
else {
if(e<T->data){////在左子树上寻找
DeleteAVL(T->lchild,e);
if(shorter){
switch(T->bf){
case LH:T->bf=EH;shorter=true;break;
case EH:T->bf=RH;shorter=false;break;
case RH:Delete_Rightbalance(T);shorter=true;break;
}////switch(T->bf)
}/////if(shorter)
}/////if(e<T->data)
else{ /////////在右子树上寻找
DeleteAVL(T->rchild,e);
if(shorter)
switch(T->bf){
case LH:Delete_Leftbalance(T);shorter=true;break;
case EH:T->bf=LH;shorter=false;break;
case RH:T->bf=EH;shorter=true;break;
}////////switch(T->bf)
}////////在右子数上寻找完
}////////在左右子上完
}///////////删除完
return T;
}
2． 主程序和其他伪码算法
void main(){
while(e!=0){
if(e!=0) InsertAVL(T,e);
}
while(d!=0){
if(d!=0) InsertAVL(T,d);
Preordertraverse(T);
}
c=FindAVL(T,t);
if(c==1)printf("有要查找的节点\n");
else printf("无要查找的节点\n");
do{
DeleteAVL(T,b);
Preordertraverse(T);
}while(b==1);
}
///右旋
bstree R_Rotate(bstree &p){
bstree lc;
lc=p->lchild;
p->lchild=lc->rchild;
lc->rchild=p;
p=lc;
return p;
}
////左旋
bstree L_Rotate(bstree &p){
bstree rc;
rc=p->rchild;
p->rchild=rc->lchild;
rc->lchild=p;
p=rc;
return p;
}
/////左平衡处理
bstree LeftBalance(bstree &T){
bstree lc,rd;
lc=T->lchild; //lc指向T的左子树根结点
switch(lc->bf) { //检查T的左子树平衡度，并做相应的平衡处理
case LH: //新结点插入在T的左孩子的左子树上，要做单右旋处理
T->bf=lc->bf=EH;
T=R_Rotate(T);
break;
case RH: //新结点插入在T的左孩子的右子树上，要做双旋处理
rd=lc->rchild; //rd指向T的左孩子的右子树根
switch(rd->bf){ //修改T及其左孩子的平衡因子
case LH:
T->bf=RH;
lc->bf=EH;
break;
case EH:
T->bf=lc->bf=EH;
break;
case RH:
T->bf=EH;
lc->bf=LH;
break;
}//////////switch(rd->bf)
rd->bf=EH;
T->lchild=L_Rotate(T->lchild); //对T的左孩子做左旋平衡处理
T=R_Rotate(T); //对T做右旋处理
}////////switch(lc->bf)
return T;
}
////右平衡处理
bstree RightBalance(bstree &T)
{
bstree rc,ld;
rc=T->rchild; //rc指向T的右子树根结点
switch(rc->bf) { //检查T的右子树平衡度，并做相应的平衡处理
case RH: //新结点插入在T的右孩子的右子树上，要做单右旋处理
T->bf=rc->bf=EH;
T=L_Rotate(T);
break;
case LH: //新结点插入在T的右孩子的左子树上，要做双旋处理
ld=rc->lchild; //ld指向T的右孩子的左子树根
switch(ld->bf){ //修改T及其右孩子的平衡因子
case LH:
T->bf=EH;
rc->bf=RH;
break;
case EH:
T->bf=rc->bf=EH;
break;
case RH:
T->bf=LH;
rc->bf=EH;
break;
}///switch(ld->bf)
ld->bf=EH;
T->rchild=R_Rotate(T->rchild); //对T的右孩子做右旋平衡处理
T=L_Rotate(T); //对T做左旋处理
}/////switch(rc->bf)
return T;
}
int Delete(bstree &T,int e){
//删除结点
bstree p,q;
e=0;
p=T;
if(!T->rchild) {//右子数为空需要重接它的左子数
T=T->lchild;
free(p);
shorter=true;
}
else if(!T->lchild) {//重接它的右子数
T=T->rchild;
free(p);
shorter=true;
}
else{ //左右子数均不空
q=T->lchild;
while(q->rchild!=NULL){//转左，然后向右到尽头
q=q->rchild;
}
e=q->data;
}
return e;
}
void Delete_Rightbalance(bstree &T){
///////////删除在左子树上的，相当于插入在右子树
bstree rc=T->rchild,ld;
switch(rc->bf){
case LH://///////双旋 ，先右旋后左旋
ld=rc->lchild;
rc->lchild=ld->rchild;
ld->rchild=rc;
T->rchild=rc->lchild;
rc->lchild=T;
switch(ld->bf) {
case LH:T->bf=EH;
rc->bf=RH;
break;
case EH:T->bf=rc->bf=EH;
break;
case RH:T->bf=LH;
rc->bf=EH;
break;
}
ld->bf=EH;
T=rc;
shorter=true;break;
case EH:///////删除在左子树，相当于插入在右子树，左单旋
T->rchild=rc->lchild;
rc->lchild=T;
rc->bf=LH;
T->bf=RH;
T=rc;
shorter=EH;break;
case RH:///////删除在左子树，相当于插入在右子树，左单旋
T->rchild=rc->lchild;
rc->lchild=T;
rc->bf=T->bf=EH;
T=rc;
shorter=true;break;
}
}
void Delete_Leftbalance(bstree &T)/////删除右子树上的，相当于插入在左子树上
{
bstree p1,p2;
p1=T->lchild;
switch(p1->bf) {
case LH:T->lchild=p1->rchild;//////右旋
p1->rchild=T;
p1->bf=T->bf=EH;
T=p1;
shorter=true;
break;
case EH:T->lchild=p1->rchild;///////右旋
p1->rchild=T;
p1->bf=RH;
T->bf=LH;
T=p1;
shorter=false;
break;
case RH:p2=p1->rchild;//////////右双旋
p1->rchild=p2->lchild;
p2->lchild=p1;
T->lchild=p2->rchild;
p2->rchild=T;
switch(p2->bf){
case LH:T->bf=RH;p1->bf=EH;break;
case EH:T->bf=EH;p1->bf=EH;break;
case RH:T->bf=EH;p1->bf=LH;break;
}
p2->bf=EH;
T=p2;
shorter=true;break;
}
}
3． 函数的调用关系图
Main
InsertAVL Preordertraverse FindAVL DeleteAVL
四、 调试分析
1． 在开始对平衡二叉树的插入后，再做平衡处理时，特别是在做双向旋转平衡处理后的更新时，费了一些时间；
2． 在做平衡二叉树的删除时，当删除结点左右孩子均在时，开始直接用左子树的最大数代替，然后直接删除结点，结果导致删除了将要删除的结点及其孩子均删除了，后来将要删除的结点用左子树的最大树代替后，对左子树的最大结点做好标记，然后再做对其做删除处理。
3． 本程序算法基本简单，没有多大困难，就是在分析做双旋平衡处理的更新时，开始思路有些混乱，后来就好了；
五、 用户手册
1 本程序的运行环境为DOS *** 作系统，执行文件为Balanced Treeexe。
2 进入演示程序后，按广度遍历输入平衡二叉树，中间以回车键隔开，输入0为结束；再输入要插入的结点，输入0结束，再输入要查找的结点，最后可以输入要删除的结点，输入0结束
六、 测试结果
先按广度遍历创建平衡二叉树（亦可一个一个的插入二叉树的结点）（50 20 60 10 30 55 70 5 15 25 58 90） ，输入0结束，然后可插入结点（39），其会显示插入后的二叉树，输入0，不再插入；输入要查找结点（6），输入要删除的结点（20），其显示如下：
七、 附录
Balance Treecpp

PTN是一种面向分组业务的传送网络和技术，它定位于城域网汇聚接入层，以分组交换为核心并提供多业务支持，既具备数据通信网组网灵活和统计复用传送的特性，又继承了传统光传送网面向连接、快速保护、OAM能力强等优点。

PTN通过标签交换机制实现面向连接的快速转发；通过PWE3技术实现各类非分组业务的端到端仿真；通过DiffServ模型实现端到端的QoS控制；通过CIR（保证带宽）和PIR（突发带宽）机制实现统计复用；通过同步以太网、IEEE 1588v2和ToP等技术提供精确的频率和时间同步；提供设备保护、线性复用段保护、MPLS Tunnel APS、LAG和FRR等丰富的保护方式和类似SDH的电信级的OAM能力。多种技术的融合为PTN高效、高质地承载3G基站和全业务奠定了良好的基础。

PTN在实现方式上有MPLS-TP和PBT两种技术标准，分别源自对MPLS技术和以太网技术的改进。本次杭州移动IP化传送项目试点使用的华为PTN系列设备采用的是MPLS-TP技术。

PTN和OTN都是传输网的，PTN是Packet Transport Network的缩写，其实感觉就是把交换机给光传输化了，然后用光纤连接起来，现在国内运营商正在部署阶段，是以后传输接入及汇聚的主要传输网络。OTN是OpticalTransportNetwork的缩写，是DWDM（密集波分技术）的应用，其传输容量大，是今后一段时间骨干传输网的主要网络，很多运营商都在大规模部署。

从技术角度上看是可以承载的
从实际应用上，PTN接入环目前大部分是采用GE的速率，OLT上行也是一个G，容易出现在忙时PTN环网出现拥塞，导致OLT或者PTN上承载的业务中断，例如4G用户或者家宽用户无法上网。再我们这里出现过这些问题，后来OLT上行统一改成裸纤或者OTN承载

1、OTN（光传送网，OpticalTransportNetwork），是以波分复用技术为基础、在光层组织网络的传送网，是下一代的骨干传送网。

OTN是以波分复用技术为基础、在光层组织网络的传送网，是下一代的骨干传送网。OTN是通过G872、G709、G798等一系列ITU-T的建议所规范的新一代“数字传送体系”和“光传送体系”，将解决传统WDM网络无波长/子波长业务调度能力差、组网能力弱、保护能力弱等问题。

2、PTN（分组传送网，Packet Transport Network）是指这样一种光传送网络架构和具体技术：在IP业务和底层光传输媒质之间设置了一个层面，它针对分组业务流量的突发性和统计复用传送的要求而设计，以分组业务为核心并支持多业务提供，具有更低的总体使用成本（TCO），同时秉承光传输的传统优势，包括高可用性和可靠性、高效的带宽管理机制和流量工程、便捷的OAM和网管、可扩展、较高的安全性等。

扩展资料：

OTN和PTN联系：

应该说OTN与PTN是完全不同的两种技术，从技术上来说应该说没有联系。

OTN是光传送网，是从传统的波分技术演进而来，主要加入了智能光交换功能，可以通过数据配置实现光交叉而不用人为跳纤。大大提升了波分设备的可维护性和组网的灵活性。同时，新的OTN网络也在逐渐向更大带宽，更大颗粒，更强的保护演进。

PTN是包传送网，是传送网与数据网融合的产物。主要协议是TMPLS，较网络设备少IP层而多了开销报文。可实现环状组网和保护。是电信级的数据网络（传统的数据网是无法达到电信级要求的）。PTN的传送带宽较OTN要小。一般PTN最大群路带宽为10G，OTN单波10G，群路可达400G-1600G，最新的技术可达单波100G。是传送网的骨干。

参考资料来源：百度百科-OTN

参考资料来源：百度百科-PTN

满意答案ぎ抱影无眠い4级2011-10-17 3G的分组域业务的发展是IP化业务的主要发展动力，PS域业务将呈现逐步发展的趋势，现有的MSTP网络通过扩容改造便可实现IP业务的传送。PTN的引入将会是一个渐进的过程，MSTP网络在很长一段时间内仍将用于承载大量的TDM业务，PTN建网初期将主要用于IP化业务的承载，随着业务网IP化进程的深入，TDM接口将逐渐减少，最终实现MSTP网络向PTN的完全演进。图2为PTN设备在电信网络中的应用。
无论是IP城域网还是高质量的城域PTN，核心层采用路由器组织IP/MPLS网络可以满足各种IP化业务当前和未来QoS要求，路由器一般采用GE/10GE组网，传送层面只需要提供大量带宽透明传送通道即可，因此应采用IP over OTN/WDM技术，在城域核心节点部署OTN/WDM设备，OTN设备可以实现GE、10GE等业务的汇聚和保护，是今后城域WDM系统的发展方向。
汇聚层和接入层应采用自上而下的PTN引入策略。首先在汇聚层引入PTN，接入层层充分利用现有MSTP网络。PTN设备单独组织第二传送平面，采用10GE环网保护，在汇聚节点原有MSTP设备和PTN设备采用POS或GE接口实现互通，PTN从MSTP汇聚节点分流3G分组域的数据业务，解决汇聚层MSTP的汇聚收敛压力，采用同厂家的PTN可实现MSTP和PTN的统一网管和维护。随着PTN技术的逐步成熟，逐步在接入层采用PTN替换MSTP设备，从而实现网络的完全演进。

---