打算就说说标题的方法，和介绍一下查找成功和非成功二叉树中结点的方法

关键字序列1,2,3,4,5构造而得的二叉排序树

ASL=（1,2,3,4,5）/5=3

按关键字3,1,2,5,4构造而得的二叉排序树

ASL=(1+2+2+3+3)/5=2.2

很明显第二种序列的ASL要快。至于二叉排序树怎么构成的其实就是根据它的性质（若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值，若它的右子树不空，则右子树上的所有结点的值均大于它的根结点的值）

ASL怎么求

分别分为成功和非成功的情况

成功

每个结点的深度相加除以结点个数

非成功

我拿个书上的例子把

首先，先补全二叉树，可以看到有12个非成功的结点，这里我假设每个非成功查找结点概率相同，然后深度为3的非成功结点有4个，深度为4的非成功结点有8个。所以是3*4+4*8

所以该图非成功的ASL=（3*4+4*8）/12

二叉排序树

  二叉排序树： 或者是一棵空树；或者是具有下列性质的二叉树：(1)若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；(2)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3)它的左、右子树也分别为二叉排序树。

 
 

二叉排序树插入

查询

  二叉排序树又称二叉查找树，根据上述定义的结构特点可见。即当二叉排序树不空时，首先将给定值和根结点的关键字比较，若相等，则查找成功，否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找。

Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p){
	//在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找成功 
	//则指针p指向该数据元素结点，并返回TRUE，否则指针p指向查找路径上访问的 
	//最后一个结点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL 
	if(!T){//查找不成功 
		p = f;
		return FALSE;
	}
	else if EQ(key, T->data.key){//查找成功 
		p = T;
		return TRUE;
	}
	else if LT(key, T->data.key)//在左子树中继续查找 
		return SearchBST(T->lchild, key, T, p);
	else	//在右子树中继续查找 
		return SearchBST(T->rchild, key, T, p);
}

查找分析

6 个记录的查找概率相等=1/6
(a)树平均查找长度：ASL_(a) = (1+2+2+3+3+3)/6 = 14/6
(b)树平均查找长度：ASL_(b) = (1+2+3+4+5+6)/6 = 21/6
所以含有 n 个结点的二叉排序树的平均平均查找长度和树的形态有关。
最差情况：二叉树排序树为单只树，平均查找长度与顺序查找相同 (n+1)/2
最好情况：与折半查找的判断树相同，平均查找长度与 log₂n 成正比

P(n) ≤ 2(1+1/n)ln n
 

插入

  树的结构不是一次生成的，而是在查找过程中，在树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功是查找路径上访问的最后一个一节点的左孩子或右孩子。

Status InsertBST(BiTree &T, ElemType e){
	//当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并返回TRUE 
	//否则返回FALSE 
	if(!SearchBST(T, e.key, NULL, p)){//查找不成功 
		s = (BiTree)malloc(sizeof(BiTNode));
		s->data = e;	s->lchild = s->rchild = NULL;
		if(!p)//被插结点*s为新的根结点 
			T = s;
		else if LT(e.key, p->data.key)//被插结点*s为左孩子 
			p->lchild = s;
		else//被插结点*s为右孩子 
			p->rchild = s;
		return TRUE;
	}
}

建立

  从空树出发，经历一系列的查找插入操作之后，可生成一棵二叉树。
  设查找序列为{45，24，53，45，12，24，90}，生成二叉排序树过程如下：

  可以看出，中序遍历二叉排序树可得到一个关键字的有序序列。
 
 

二叉排序树删除

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

Status DeleteBST(BiTree &T, KeyType key){
	//若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点 
	//并返回TRUE；否则返回FALSE 
	if(!T)//不存在关键字等于key的数据元素 
		return FALSE;
	else{
		if(EQ(key, T->data.key))//找到关键字等于key的数据元素 
			return Delete(T);
		else if(LT(key, T->data.key))
			return Delete(T->lchild, key);
		else
			return Delete(T->rchild, key);
	}
}

Status Delete(BiTree &p){
	//从二叉排序树中删除结点p，并重接它的左或右子树 
	if(!p->rchild){//右子树空则只需重接它的左子树 
		q = p;
		p = p->lchild;
		free(q);
	}
	else if(!p->lchild){//只需重接它的右子树 
		q = p;
		p = p->rchild;
		free(q);
	}
	else{//左右子树均不空 
		q = p;
		s = p->lchild;
		while(s->rchild){//转左，然后向右到尽头 
			q = s;
			s = s->rchild;
		}
		p->data = s->data;//s指向被删结点的“前驱” 
		if(q != p)//重接*q的右子树 
			q->rchild = s->lchild;
		else//重接*q的左子树 
			q->lchild = s->lchild;
		delete s;
	}
	return TRUE;
}

引言

• 如何更加高效的完成对数据的查询和添加操作，例如↓↓↓

  给你一个数列 (7, 3, 10, 12, 5, 1, 9)，要求能够高效的完成对数据的查询和添加。

• 已有解决方案的优缺点

• 树结构解决方案：
  二叉排序树

1、定义

\quad \quad 二叉排序树又称二叉搜索树、二叉查找树。

\quad \quad 二叉排序树或是空树，或是满足以下性质的二叉树：

（1）若其左子树非空，则左子树上所有结点的值小于根结点的值；

（2）若其右子树非空，则右子树上所有结点的值均大于等于根结点的值；

（3）其左右子树本身又各是一棵二叉排序树。

\quad \quad 总结起来就是根据结点的值有：左子树<根结点<右子树

\quad \quad 如下图就是一棵二叉排序树：

\quad \quad 它的中序遍历：8、10、11、12、13、15、16、17、18、19、22、25，刚好是排好序的。

2、性质

\quad \quad 中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序序列。

3、操作

3.1 查找

【算法思想】——递归

• 若二叉排序树为空，则查找失败，返回空指针
• 若二叉排序树非空，将给定值与根结点值比较：

  • 若查找的关键字等于根结点，则查找成功，返回根结点地址

  • 否则

    • 若小于根结点，则进一步查其左子树
    • 若大于根结点，则进一步查其右子树

【代码实现】

def BST_serach(root, value):
    if not root: # 遇到空节点，未找到
        return False
    if root.value == value: # 找到
        return True
    elif value < root.value: # 若值小于根节点值，继续从左子树中查找
        return BST_serach(root.left, value)
    else: # 否则，该值大于根节点的值，从右子树中查找
        return BST_serach(root.right, value)

\quad \quad 二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径：

• 比较的关键次数=此结点所在曾次数
• 最多的比较次数=树的深度

\quad \quad 含有n个结点的二叉排序树的平均查找长度ASL和树的形态有关

如何提高形态不均衡的二叉排序树的查找效率？
做平衡化处理，尽量让二叉树的形状均衡，转换成平衡二叉树。

3.2 插入

\quad \quad 从根结点开始逐个与关键字进行比较，遇键值较大者就向左，遇键值较小者就向右，一直到尾端，记为插入点。
【算法思想】—递归

• 若二叉排序树为空，则插入结点作为根结点插入到空树中；

• 否则，继续在左、右树上查找

  • 树中已有，不再插入

  • 树中没有

    • 查找直至某个叶子节点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子。

【代码实现】

def BST_insert(root, value):
    if not root: # 遇到空节点，即为插入位置
        root = Node(value)
        return
    if root.value == value: # 若该值已存在于二叉树中，插入失败
        print("Existed!!!")
        return
    elif value < root.value: # 若值小于根节点值，继续从左子树中查找插入位置
        if not root.left: # 如果根结点没有左子树，则插入到左子树中
            root.left = Node(value)
            return
        BST_insert(root.left, value)
        # 注：以上四句不可用 return self.BST_insert(root.right, value)代替，
        # 会出现节点无法插入的问题
    else: # 否则，该值大于根节点的值，从右子树中查找插入位置
        if not root.right:
            root.right = Node(value)
            return
        BST_insert(root.right, value)

\quad \quad 插入的元素一定在叶结点上。

3.3 生成

\quad \quad 从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树。

例：设查找的关键字序列为{45，24，53，45，24，12，37，93}

\quad \quad 容易看出，每次插入新的结点都是二叉排序树上的叶子结点，则在插入时，不必移动其他结点，只需改动某个结点的指针，由空变为非空即可。结点的插入操作与二叉排序树的定义紧密相关，即左<根<右，新插入一个关键字时，从根结点开始比较，直到找到合适的插入位置为止。还有一种情况就是一个序列中可能有两个相同的关键字，对于这种情况，向树中插入关键字时遇到相同关键字时，什么都不做，不进行重复插入操作。

【代码实现】
方法一：连续使用插入的方法生成二叉排序树

#调用上面的插入函数创建二叉排序树
def createTree(NodeList):
    """创建二叉排序树, NodeList为待插入数据的列表"""
    T = None
    for i in range(len(NodeList)):
        T = BST_insert(T, NodeList[i])
    return T

方法二：使用添加节点的方法创建二叉排序树

# 添加结点
def add(self, val):  
    node = TreeNode(val)
    if self.root is None:
        self.root = node
        return
    queue = [self.root]
    while queue:
        temp_node = queue.pop(0)
        # 判断传入结点的值和当前子树结点的值关系
        if node.val < temp_node.val:
            if temp_node.left is None:
                temp_node.left = node
                return
            else:
                queue.append(temp_node.left)
        if node.val >= temp_node.val:
            if temp_node.right is None:
                temp_node.right = node
                return
            else:
                queue.append(temp_node.right)

\quad \quad 一个无序序列可通过构造二叉排序树而变成一个有序序列。构造树的过程就是对无序序列进行排序的过程。

注意：关键字的输入顺序不同，生成的二叉排序树形态不同。

3.4 删除

\quad \quad 从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，只能删除该结点，并且还应保证删除后所得的二叉树仍然满足二叉排序树的性质不变。

\quad \quad 由于中序遍历二叉排序树可以得到一个递增有序的序列。那么，在二叉排序树中删去一个结点相当于删去有序序列中的一个结点。

• 将因删除结点而断开的二叉链表重新连接起来；

• 防止重新链接后树的高度增加。

删除方法考虑以下几个情况：

1、 删除节点为叶子节点
\quad \quad 删除的节点没有左子树也没有右子树，也就是删除的节点为叶子节点。有两种情况：
 1. 该叶子节点为二叉排序树的根结点，也就是二叉排序树中只有一个结点，只需要将root的指针置为空即可
 2. 该叶子节点有父节点，将父节点的连接该删除节点的指针置为空即可。

思路
(1) 需求先去找到要删除的结点 targetNode
(2) 找到targetNode 的 父结点 parent
(3) 确定 targetNode 是 parent的左子结点 还是右子结点
(4) 根据前面的情况来对应删除
左子结点 parent.left = null
右子结点 parent.right = null;

2、删除的节点只有左子树或者只有右子树

\quad \quad 删除节点后，将父节点指针指向子树即可

• 若结点T的左子树为空，则用T的右子树替代T，即为删除了T结点

• 若结点T的右子树为空，则用T的左子树替代T，即为删除了T结点

思路：

(1) 需求先去找到要删除的结点 targetNode
(2) 找到targetNode 的 父结点 parent
(3) 确定targetNode 的子结点是左子结点还是右子结点
(4) targetNode 是 parent 的左子结点还是右子结点
(5) 如果targetNode 有左子结点
5. 1 如果 targetNode 是 parent 的左子结点
parent.left = targetNode.left;
5.2 如果 targetNode 是 parent 的右子结点
parent.right = targetNode.left;
(6) 如果targetNode 有右子结点
6.1 如果 targetNode 是 parent 的左子结点
parent.left = targetNode.right;
6.2 如果 targetNode 是 parent 的右子结点
parent.right = targetNode.right

3、删除的节点同时存在左右子树
\quad \quad 如果同时存在左右子树，则可以将二叉排序树进行中序遍历，取将要被删除的节点的前驱或者后继节点替代这个被删除的节点的位置。【前驱是左子树中最大的结点；后继是右子树中最小的结点】

思路
(1) 需求先去找到要删除的结点 targetNode
(2) 找到targetNode 的 父结点 parent
(3) 从targetNode 的右子树找到最小的结点
(4) 用一个临时变量，将 最小结点的值保存 temp = 11
(5) 删除该最小结点
(6) targetNode.value = temp

【代码实现】

class TreeNode(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


class BinarySortTree(object):
    def __init__(self):
        self.root = None

    # 添加结点
    def add(self, val):  
        node = TreeNode(val)
        if self.root is None:
            self.root = node
            return
        queue = [self.root]
        while queue:
            temp_node = queue.pop(0)
            # 判断传入结点的值和当前子树结点的值关系
            if node.val < temp_node.val:
                if temp_node.left is None:
                    temp_node.left = node
                    return
                else:
                    queue.append(temp_node.left)
            if node.val >= temp_node.val:
                if temp_node.right is None:
                    temp_node.right = node
                    return
                else:
                    queue.append(temp_node.right)

    # 中序遍历
    def in_order(self, node):
        if node is None:
            return
        self.in_order(node.left)
        print(node.val, end=" ")
        self.in_order(node.right)

    # 删除节点
    def del_node(self, node, val):
        '''
        :param node: 传入根结点
        :param val: 传入要删除结点的值
        :return:
        '''
        if node is None:
            return
        # 先去找到要删除的结点
        target_node = self.search(node, val)
        if target_node is None:  # 如果没有找到要删除的结点
            return
        # 如果发现当前这棵二叉排序树只有一个结点
        if node.left is None and node.right is None:
            self.root = None # 根结点直接置空
            return
        # 去找到target_node的父结点
        parent = self.parent(node, val)
        
        # 删除的结点是叶子结点
        if target_node.left is None and target_node.right is None:
            # 判断target_node 是父结点的左子结点，还是右子结点
            if parent.left and parent.left.val == val:  # target_node 是左子结点
                parent.left = None
            elif parent.right and parent.right.val == val:  # target_node 是右子结点
                parent.right = None
        elif target_node.left and target_node.right:  # 删除有两颗子树的结点
            min_val = self.del_right_tree_min(target_node.right)
            target_node.val = min_val
        
        # 删除只有一颗子树的结点
        else:  
            if target_node.left:  # 如果要删除的结点target_node有左子结点
                if parent: # 如果target_node有父结点
                    if parent.left.val == val:  # target_node是parent左子结点
                        parent.left = target_node.left
                    else:  # parent.right.val == val,即是target_node是parent右子结点
                        parent.right = target_node.left
                else:
                    self.root = target_node.left
            else:  # 如果要删除的结点target_node有右子结点
                if parent: # 如果target_node有父结点
                    if parent.left.val == val:
                        parent.left = target_node.right
                    else:  # parent.right.val == val,即是target_node是parent右子结点
                        parent.right = target_node.right
                else:
                    self.root = target_node.right

    # 查找结点
    
    def search(self, node, val):
        '''
        :param node: 传入根结点
        :param val: 传入要查找的值
        :return: 找到返回该值，没找到返回None
        '''
        if node is None:
            return None
        if node.val == val:
            return node
        if val < node.val:
            return self.search(node.left, val)
        else:
            return self.search(node.right, val)

    

    # 查找结点的父结点
    def parent(self, node, val):
        '''
        :param node: 传入根结点
        :param val: 传入要找的父结点的值
        :return: 如果找到返回该父结点，如果没有返回None
        '''
        if node is None:  # 如果要找的值遍历完二叉树还不存在，由此退出并返回None
            return None
        if self.root.val == val:  # 根结点没有父结点
            return None
        # 如果当前结点的左子结点或者右子结点存在，并且值就是要要找的，直接返回它的父结点
        if (node.left and node.left.val == val) or (node.right and node.right.val == val):
            return node
        else:
            # 如果要找的结点值小于父结点且它的左子结点存在，向左递归
            if val < node.val and node.left:
                return self.parent(node.left, val)
            # 如果要找的结点值大于父结点且它的右子结点存在，向左递归
            elif node.val < val and node.right:
                return self.parent(node.right, val)

    def del_right_tree_min(self, node):
    	# 从target_node的右子树出发，查找它的左边最小结点，并返回删除结点的值
    	# 作用1：返回以node为根结点的二叉排序树的最小结点
    	# 作用2：删除 node 为根结点的二叉排序树的最小结点
        temp_node = node
        # 循环的查找左结点，直到找到最小值
        while temp_node.left:
            temp_node = temp_node.left
        # 这时 target就指向了最小结点
        # 调用删除方法，删除最小结点
        self.del_node(self.root, temp_node.val) # 注意传入的还是跟结点，从根结点开始查找
        return temp_node.val


if __name__ == '__main__':
    t = BinarySortTree()
    note_array = [7, 3, 10, 12, 5, 1, 9, 2]
    for item in note_array:
        t.add(item)
    '''# 测试：删除叶子结点
    t.del_node(t.root, 2)
    t.del_node(t.root, 5)
    t.del_node(t.root, 9)
    t.del_node(t.root, 12)
    t.in_order(t.root) # 1 3 7 10
    '''

    '''# 测试：删除只有一颗子树的结点
    t.del_node(t.root, 1)
    t.in_order(t.root) # 2 3 5 7 9 10 12 
    '''
    # 测试：删除有两颗子树的结点
    # t.del_node(t.root, 7)
    # t.in_order(t.root) # 1 2 3 5 9 10 12
    # t.del_node(t.root, 10)
    # t.in_order(t.root)  # 1 2 3 5 7 9 12
    # t.in_order(t.root)

    # 连续删除任意结点测试：
    t.del_node(t.root, 2)
    t.del_node(t.root, 5)
    t.del_node(t.root, 9)
    t.del_node(t.root, 12)
    t.del_node(t.root, 7)
    # t.del_node(t.root, 3)
    # t.del_node(t.root, 10)
    # t.del_node(t.root, 1)
    t.in_order(t.root)