树、二叉树、查找算法总结

一、思维导图：

二、重要概念：

1、二叉树的五种基本形态：

2、前、中、后序遍历：

1.1前序遍历
根节点->左子树->右子树

void preorder_traverse(const struct bi_tree *tree) 
{
    if (tree) {
        /* 访问根节点*/
        access(tree->data);
 
        if (tree->left) {
            /* 访问左节点 */
            preorder_traverse(tree->left);
        }
 
        if (tree->right) {
            /* 访问右节点 */
            preorder_traverse(tree->right);
        }
    }
}

1.2中序遍历

左子树>根节点->右子树

void midorder_traverse(const struct bi_tree *tree)
{
    if (tree->left) {
        midorder_traverse(tree->left);
    }
    access(tree->data);
    if (tree->right) {
        midorder_traverse(tree->right);
    }
}

1.3后序遍历

左子树->右子树->根节点

void lastorder_traverse(const struct bi_tree *tree)
{
    if (tree->left) {
        lastorder_traverse(tree->left);
    }
    if (tree->right) {
        lastorder_traverse(tree->right);
    }
    access(tree->data);
}

2、ASL计算：
如图所示的二叉排序树，其成功的平均查找长度是 ； 不成功的平均查找长度是 。

ASLs = (1×1+2×2+2×3+1×4)/6 = 15/6
ASLus= (2×2+3×3+2×4)/7 = 21/7=3

3、B树的插入与删除：
分裂的规则是该结点分成两半，将中间的关键字进行提升，加入到父亲结点中，但是这又可能存在父亲结点也满员的情况，则不得不向上进行回溯，甚至是要对根结点进行分裂，那么整棵树都加了一层。

插入：
以一个3阶的B树为例：

（1）如果该结点的关键字个数没有到达2个，那么直接插入即可；
（2）如果该结点的关键字个数已经到达了2个，那么根据B树的性质显然无法满足，需要将其进行分裂

删除：
可以这样处理：被删关键字为该结点中第i个关键字key[i]，则可从指针son[i]所指的子树中找出最小关键字Y，代替key[i]的位置，然后在叶结点中删去Y。 因此，把在非叶结点删除关键字k的问题就变成了删除叶子结点中的关键字的问题了，

那么B树的删除操作就变成了删除叶子结点中的关键字问题了。

（1）被删关键字Ki所在结点的关键字数目不小于ceil(m/2)，则只需从结点中删除Ki和相应指针Ai，树的其它部分不变

2）被删关键字Ki所在结点的关键字数目等于ceil(m/2)-1，则需调整。

（3）被删关键字Ki所在结点和其相邻兄弟结点中的的关键字数目均等于ceil(m/2)-1，假设该结点有右兄弟，且其右兄弟结点地址由其双亲结点指针Ai所指。则在删除关键字之后，它所在结点的剩余关键字和指针，加上双亲结点中的关键字Ki一起，合并到Ai所指兄弟结点中（若无右兄弟，则合并到左兄弟结点中）。如果因此使双亲结点中的关键字数目少于ceil(m/2)-1，则依次类推。

三、

疑难问题：
二叉搜索树的插入与删除
解决方法：
可以先写算法即思路再敲代码
插入：
(1)树为空，则直接插入，返回true
(2)树不为空，按二叉搜索树性质查找插入的位置，插入新节点
代码：

BinSearchTree* Insert(BinSearchTree* root,int x)
{
	if(!root){
		root=(BinSearchTree*)malloc(sizeof(TreeNode));
		root->data=x;
		root->lchild=root->rchild=NULL;
	}
	else 
		if(x>root->data){
			root->rchild=Insert(root->rchild,x);
		}else if(x<root->data){
			root->lchild=Insert(root->lchild,x);
		}
	return root;
}

删除：
(1)要删除的是叶结点：直接删除，并修改其父结点指针（置为NULL）
(2)要删除的结点只有一个孩子结点：将其父结点的指针指向要删除结点的孩子结点
(3)要删除的结点有左、右两棵子树：用另一结点替代被删除结点：取右子树的最小元素或者左子树的最大元素（因为这两个元素一定不是有两个元素的结点）