排序二叉树删除节点

假设在二叉排序树上被删结点为*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的右子树即可。

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的左子树。 根节点的右子树就不多做分析了，原理类似。最后得出如下二叉树，最后再进行后序排列。