排序二叉树删除节点

1. 排序二叉树删除节点

假设在二叉排序树上被删结点为*p(指向结点的指针为p)，其双亲结点为*f(结点指针为f)，且不失一般性，可设*p是*f的左孩子。
    下面分三种情况进行讨论：
    (1)若*p结点为叶子结点，即PL和PR均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。
    (2)若*p结点只有左子树PL或者只有右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树即可。显然，作此修改也不破坏二叉排序树的特性。
    (3)若*p结点的左子树和右子树均不空。图(b)可知，在删去*p结点之前，中序遍历该二叉树得到的序列为{…CLC…QLQSLSPPRF…}，在删去*p之后，为保持其它元素之间的相对位置不变，可以有两种做法：其一是令*p的左子树为*f的左子树，而*p的右子树为*s的右子树，如图(c)所示；其二是令*p的直接前驱(或直接后继)替代*p，然后再从二叉排序树中删去它的直接前驱(或直接后继)。如图(d)所示，当以直接前驱*s替代*p时，由于*s只有左子树SL，则在删去*s之后，只要令SL为*s的双亲*q的右子树即可。

2. 排序二叉树删除节点

1.答案：C
分析：根据性质“深度为K的二叉树至多有2k
-1个结点（k≥1）”可知，具有结点767是深度为10完全二叉树。前9层的结点有29-1=511个结点，在第10层的结点个数就为767-511=256，那么在第9层中具有两个子结点的结点数为256/2=128，则整个二叉树具有两个子结点的结点数为28
-1+128=384，又根据性质“对任何一棵二叉树，如果其叶子节点数为n0，具有两个子结点的结点数为n2，则
n0=n2+1”，叶子节点数为384+1=385.
2.答案：16
分析：根据性质“在二叉树的第i层上至多有2i-1个结点”，深度为5的满二叉树的叶子结点数即为
第5层的结点数25-1=16.
3.答案：dgebhfca
分析：排列的概念问题，就不多说了。从前序排列可以得出，树的根节点为a，根节点的左节点为b，再根据中序排列中从根节点a的左右分开分别为左右子树的结点，左子树为dbge，右子树为chf，再根据前序排列c为右子树第一个即为根节点的右结点。再根据中序排列中右边根节点的左边为d，即d为b的左子树且可以看出d没有左右子树，又在根据前序排列中e紧跟在b后面得出e为b右子树，再根据根据中序排列中g在e前得出g为e的左子树。
根节点的右子树就不多做分析了，原理类似。最后得出如下二叉树，最后再进行后序排列。

3. 二叉排序树的删除结点

在二叉排序树删去一个结点，分三种情况讨论：  若*p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则可以直接删除此子结点。  若*p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树（当*p是左子树）或右子树（当*p是右子树）即可，作此修改也不破坏二叉排序树的特性。  若*p结点的左子树和右子树均不空。在删去*p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：其一是令*p的左子树为*f的左/右(依*p是*f的左子树还是右子树而定)子树，*s为*p左子树的最右下的结点，而*p的右子树为*s的右子树；其二是令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的直接前驱（或直接后继）－即让*f的左子树(如果有的话)成为*p左子树的最左下结点(如果有的话)，再让*f成为*p的左右结点的父结点。在二叉排序树上删除一个结点的算法如下：  C代码  #defineStatusboolStatusDelete(BiTree*);//必须先声明StatusDeleteBST(BiTree&T,KeyTypekey){//若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素，并返回//TRUE；否则返回FALSEif(!T)returnfalse;//不存在关键字等于key的数据元素else{if(key==T->data.key){//找到关键字等于key的数据元素returnDelete(T);}elseif(keydata.key)returnDeleteBST(T->lchild,key);elsereturnDeleteBST(T->rchild,key);}returntrue;}StatusDelete(BiTree&p){//从二叉排序树中删除结点p，并重接它的左或右子树if(!p->rchild){//右子树空则只需重接它的左子树q=p;p=p->lchild;deleteq;}elseif(!p->lchild){//左子树空只需重接它的右子树q=p;p=p->rchild;delete(q);}else{//左右子树均不空q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}//转左，然后向右到尽头p->data=s->data;//s指向被删结点的“前驱”if(q!=p)//以上循环至少执行了一次q->rchild=s->lchild;elseq->lchild=s->lchild;//重接*q的左子树delete(s);}returntrue;}Java代码/***方法名称：delete()*方法描述：删除节点*@param采用递归的方式进行删除*@returnString*@Exception*/privatevoiddeleteNode(BinarySortTreep){//TODOAuto-generatedmethodstubif(p!=null){//如果节点有左子树/*1。若p有左子树，找到其左子树的最右边的叶子结点r，用该叶子结点r来替代p，把r的左孩子作为r的父亲的右孩子。2。若p没有左子树，直接用p的右孩子取代它。*/if(p.lChild!=null){BinarySortTreer=p.lChild;BinarySortTreeprev=p.lChild;while(r.rChild!=null){prev=r;r=r.rChild;}p.data=r.data;//若r不是p的左子树,p的左子树不变，r的左子树作为r的父节点的右孩子节点if(prev!=r){prev.rChild=r.lChild;}else{//若r是p的左子树，则p的左子树指向r的左子树p.lChild=r.lChild;}}else{p=p.rChild;}}}

4. 为什么删除二叉排序树中一个结点,再重新插入上去,不一定得到原来的二叉排序树

二叉排序树只要求每一个结点的左孩子小于它；右孩子大于等于它；
首先我们看看删除操作： 
“先将删除的节点与最后一个结点交换，交换之后，删除最后一个结点，然后重构二叉树。”
在这个过程中，如果你删除的是一个在根结点左边的结点，那么跟最后一个结点交换之后，为了保持二叉排序树的特性，最后一个结点会逐渐上移，很可能改变根结点的位置。

然后我们看看插入操作：
“直接跟根节点比较，如果比根结点小，插入左子树，一次递归下去，选择合适的结点,如果大于根结点，依次类推”
在这个过程中，不会改变根结点的位置。
所以得到的平衡二叉树很可能不一样。
建议你画一个图，尝试操作一下，加深对这个两个操作的理解就好办了！

5. 为什么删除二叉排序树中一个结点,再重新插入上去,不一定得到原来的二叉排序树？

二叉排序树只要求每一个结点的左孩子小于它；右孩子大于等于它；
首先我们看看删除操作： 
“先将删除的节点与最后一个结点交换，交换之后，删除最后一个结点，然后重构二叉树。”
在这个过程中，如果你删除的是一个在根结点左边的结点，那么跟最后一个结点交换之后，为了保持二叉排序树的特性，最后一个结点会逐渐上移，很可能改变根结点的位置。

然后我们看看插入操作：
“直接跟根节点比较，如果比根结点小，插入左子树，一次递归下去，选择合适的结点,如果大于根结点，依次类推”
在这个过程中，不会改变根结点的位置。
所以得到的平衡二叉树很可能不一样。
建议你画一个图，尝试操作一下，加深对这个两个操作的理解就好办了！