解决动态查找问题

目录

一、二叉搜索树 

二、查找Find()

 三、插入Insert()

四、删除delete()

五、课后习题

一、二叉搜索树 

 

二、查找Find()

 

 

 都是尾递归&＃xff0c;效率不高

 //平衡二叉树

 三、插入Insert()

 //原树为空&＃xff0c;返回修改后的下个BST&＃xff1b;原树不为空&＃xff0c;返回未修改的下个BST。

四、删除delete()

 

左子树的最大值或者右子树的最小值一定不是有两个儿子的结点&＃xff0c;

且替代其也不会破坏二叉搜索树的结构&＃xff08;可以替代根结点&＃xff09;。

 

1.找到右子树最小Tmp&＃xff0c;填进要删除的结点

2.在右子树中递归删除右子树最小

&＃xff08;    递归找到要删除的结点【最后一个if】【if、else if、else if】&＃xff0c;

        删除该结点【最后一个else】&＃xff09;

 【最后一个else】&＃xff1a;

Tmp&＃61;要删除的结点地址BST

BST&＃61;左孩子地址、右孩子地址、NULL【相当于其父结点指向左孩子、右孩子或NULL】

free(Tmp)&＃xff1a;释放要删除结点&＃xff08;Tmp仍为其地址&＃xff09;

五、课后习题

 

 

若为完全二叉树&＃xff0c;则只可能在最后一行【有左子树没有右子树】&＃xff0c;或者【左右子树都有】&＃xff0c;

而不可能【有右子树没有左子树】。

因此最小结点一定是叶节点&＃xff0c;最大结点则可以是【有左子树没有右子树】的结点。