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

一、思维导图:

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

二、重要概念:

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)要删除的结点有左、右两棵子树:用另一结点替代被删除结点:取右子树的最小元素或者左子树的最大元素(因为这两个元素一定不是有两个元素的结点)