数据结构及算法--二叉排序树_给定一组关键字序列,如何构建二叉排序树

性质

二叉排序树，又称二叉查找树，其为空树，或具有以下性质的二叉树：
（1）若其左子树不为空，则左子树上的所有节点的值均小于它的根结点的值；
（2）若其右子树不为空，则右子树上的所有节点的值均大于它的根结点的值；
（3）左右子树又分别是二叉排序树。

作用：用于查找元素是否在某无序数组中。

如序列[62，58，88，47，73，99，35，51，93，29，37，49，56，36，48，50]可构造二叉排序树如下：

---

Python实现

节点

class Node:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None
1
2
3
4
5

搜索及插入

当二叉排序树不为空时：

• 将给定值与根结点的关键字比较，若相等，则查找成功；
• 若小于根结点的关键字值，递归查左子树；
• 若大于根结点的关键字值，递归查右子树；
• 若子树为空，查找不成功。

# 搜索
def search(self, node, parent, data):
    if node is None:
        return False, node, parent
    if data == node.data:
        return True, node, parent
    if data < node.data:
        return self.search(node.lchild, node, data)
    else:
        return self.search(node.rchild, node, data)

# 插入
def insert(self, data):
    flag, node, parent = self.search(self.root, self.root, data)
    if not flag:
        new_node = Node(data)
        if data > parent.data
            parent.rchild = new_node
        else:
            parent.lchild = new_node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

删除节点

删除操作主要分为以下3种情况：

• 如果待删除的节点是叶子节点，那么可以立即被删除；
• 如果节点只有一个儿子，则将此节点parent的指针指向此节点的儿子，然后删除节点；
• 如果节点有两个儿子，则将其右子树的最小数据代替此节点的数据，并将其右子树的最小数据删除。

# 删除
def delete(self, root, data):
    flag, n, p = self.search(root, root, data)
    if not flag:
        print '无该关键字，删除失败！'
    else:
        if n.lchild is None:
            if n == p.lchild:
                p.lchild = n.rchild
            else:
                p.rchild = n.rchild
            del n
        elif n.rchild is None:
            if n == p.lchild:
                p.lchild = n.lchild
            else:
                p.rchild = n.lchild
            del n
        else: # 左右子树均不为空
            pre = n.rchild
            if pre.lchild is None: # 若目标节点的右节点无左子树，则将目标节点替换为该节点
                n.data = pre.data
                n.rchild = pre.rchild
                del pre
            else: # 若目标节点的右节点有左子树，则往下搜索到达底部
                next = pre.lchild
                while next.lchild is not None:
                    pre = next
                    next = next.lchild
                n.data = next.data
                pre.lchild = next.rchild
                del next       
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

遍历

先序遍历

访问顺序如下：

• 访问根节点
• 先序遍历左子树
• 先序遍历右子树

# 先序遍历
def preOrderTraverse(self, node):
    if node is None:
        print node.data
        self.preOrderTraverse(node.lchild)
        self.preOrderTraverse(node.rchild)
1
2
3
4
5
6

中序遍历

访问顺序如下：

• 中序遍历左子树
• 访问根节点
• 中序遍历右子树

# 中序遍历
def inOrderTraverse(self, node):
    if node is None:
        self.inOrderTraverse(node.lchild)
        print node.data
        self.inOrderTraverse(node.rchild)
1
2
3
4
5
6

后序遍历

访问顺序如下：

• 后序遍历左子树
• 后序遍历右子树
• 访问根节点

# 后序遍历
def postOrderTraverse(self, node):
    if node is None:
        self.postOrderTraverse(node.lchild)
        self.postOrderTraverse(node.rchild)
        print node.data
1
2
3
4
5
6