void insert node( Bitree& TBTNode*Sy/把树结点S插入到T的合适位置上 if(S→data>T->data if(!T->rchild) T->rchild=S else Insert Node(T->rchild, S) else if(S->data<T->data) if(!T->lchild )T->lchild=S else Insert Node(T->lchild, S) S->lchild=NULL;/插入的新结点必须和原来的左右子树断绝关系 S→ achild=NULL;∥香则会导致树结构的混乱 g//nsert Node 分析这是一个与课本上不同的插入算法在合并过程中,并不释放或新建任何结 点而是采取修改指针的方式来完成合并这样就必须按照后序序列把一棵树中 的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱 9.39 void BSTree Split( BiTree&T,Bire&A,Bire&B,intx)把二叉排序树T分裂为 两棵二叉排序树A和B,其中A的元素全部小于等于xB的元素全部大于x if(T->lchild)BSTree Split(T->lchild, A, B, x) if(T-> rchild) BSTree Split(T> rchild,A,B,x),∥分裂左右子树 if(T->data<=x)Insert Node(, T) else insert node(B,T);∥将元素结点插入合适的树中 3//BSTree Split void insert node( Bitree e&T, BTNode*Sy把树结点S插入到T的合适位置上 if(TT=S,∥考虑到刚开始分裂时树A和树B为空的情况 else if(S→>data>T>data)∥/其余部分与上一题同 if(T->rchild)T-rchild=S else Insert Node(T->rchild, S); else if(S->data<T->data) if(!T->lchild )T->lchild=S else Insert Node(T->lchild, S) S->lchild=NULL:void Insert_Node(Bitree &T,BTNode *S)//把树结点 S 插入到 T 的合适位置上 { if(S->data>T->data) { if(!T->rchild) T->rchild=S; else Insert_Node(T->rchild,S); } else if(S->data<T->data) { if(!T->lchild) T->lchild=S; else Insert_Node(T->lchild,S); } S->lchild=NULL; //插入的新结点必须和原来的左右子树断绝关系 S->rchild=NULL; //否则会导致树结构的混乱 }//Insert_Node 分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结 点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中 的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱. 9.39 void BSTree_Split(BiTree &T,BiTree &A,BiTree &B,int x)//把二叉排序树 T分裂为 两棵二叉排序树 A 和 B,其中 A 的元素全部小于等于 x,B 的元素全部大于 x { if(T->lchild) BSTree_Split(T->lchild,A,B,x); if(T->rchild) BSTree_Split(T->rchild,A,B,x); //分裂左右子树 if(T->data<=x) Insert_Node(A,T); else Insert_Node(B,T); //将元素结点插入合适的树中 }//BSTree_Split void Insert_Node(Bitree &T,BTNode *S)//把树结点 S 插入到 T 的合适位置上 { if(!T) T=S; //考虑到刚开始分裂时树 A 和树 B 为空的情况 else if(S->data>T->data) //其余部分与上一题同 { if(!T->rchild) T->rchild=S; else Insert_Node(T->rchild,S); } else if(S->data<T->data) { if(!T->lchild) T->lchild=S; else Insert_Node(T->lchild,S); } S->lchild=NULL;