二叉树
定义：二叉树是最多只有两个节点的树，二叉树具有唯一根节点。
二叉树
二叉树的特点：
1、二叉树每个节点最多有两个孩子；
2、二叉树每个节点最多有一个父亲。
二分搜索树
二分搜索树
二分搜索树特点：
1、二分搜索树的每个节点的值，大于其左子树的所有节点的值；小于其右子树的所有节点的值；
2、每一颗子树也是二分搜索树。
源码分析：
二分搜索树结构
首先，二分搜索树的泛型必须是实现了 Comparable 的，即可以比较的。属性 Node 有三个变量，类似于LinkedList。记录着当前节点的值，左右节点。
向二分搜索树中添加元素 add(E e)：
add
采用递归方式——递归的终止条件：最后一步是递归到最后一个根元素 NULL，此时将新节点放入该位置；递归的步骤：这里要根据当前节点的值和 e 的大小，来判断走左右子树。然后递归函数add(node.left , e) 或者 add(node.right, e)。
查找元素 contains(E e):
contains
和 add 类似的递归操作，只是查找元素不需要赋值。
递归终止条件：1、走到最后一个节点 NULL，还没找到；2、找到了元素 E。
递归操作：依旧是根据当前节点的值和 e 的大小，来判断走左右子树的递归。
遍历二分搜索树——前序遍历
前序遍历
前序遍历（又称深度优先遍历，即会优先走完左子树，然后往回走）：先根节点，再左右分支。
递归终止条件：走到最后一个节点 NULL。
递归操作：分别从左右两边开始递归。
遍历二分搜索树——中序遍历
中序遍历
中序遍历：左分支——> 根节点 ——> 右分支。
遍历二分搜索树——后序遍历
后序遍历
后序遍历：左芬子——> 右分支——> 根节点。
遍历结果分析
只有中序遍历有明显的特征，即可以自然排序。
遍历分析
每个根节点都会遍历三次，图中 1,2,3 点。1 点代表该根节点第一次访问；2 点代表左子树走完之后（走到最后一步左 NULL 节点返回），再次访问该根节点；3 点表示右子树走完之后（走到最后一步右 NULL 节点返回），再次访问该节点。
对于前序遍历来说，走到1 点就会输出；中序遍历，走到2 点才会输出；后序遍历，走到 3点才会输出。并且，遍历的顺序是左子树到右子树。
二分搜索树遍历执行顺序
前序遍历结果：即执行1 号点的输出顺序，28 16 13 22 30 29 42；
中序遍历结果：即执行2 号点的输出顺序，13 16 22 28 30 29 42；
后序遍历结果：即执行3 号点的输出顺序，13 22 16 29 42 30 28；
二分搜索树其他遍历扩展：
二分搜索树的前序遍历（深度优先遍历），非递归实现：由于前序遍历的顺序是 根节点——> 左子树 ——> 右子树，并且输出是在第一次访问节点时。于是可以使用栈，来记录节点的访问顺序，因为栈是后进先出的，于是必须先压入右节点再压入左节点。
栈实现前序遍历
二分搜索树的层序遍历：按层遍历。
层序遍历
队列实现层序遍历
层序遍历的输出结果为： 28 16 30 13 22 29 42；
查找二分搜索树的最大值和最小值：
思路分析：因为二分搜索树的左子树是小于根节点的，右子树是大于跟节点的，于是最小值是在左子树的最左边节点（node.left == null）；最大值在右子树的最右边那个节点（node.right == null）。
二分搜索树最小值
二分搜索树最大值
删除二分搜索树的最小值或者最大值：
思路分析：删除最小值时，找到左子树的最左节点（最小值节点，node.left == null），然后让其上一个节点的左节点指向当前最小值节点的右子树，同时删除最小值节点（node.right = null）；删除最大值时，找到右子树的最右节点（最大值节点，node.right == null），然后让其上一个节点的右节点指向当前最大值节点的左子树，同时删除最大值节点（node.left = null）。
删除最小值节点
删除最大值节点
删除二分搜索树的任意节点：
思路分析：当删除的元素没有左子树（node.left == null）或者没有右子树（node.right == null），这个逻辑跟删除最小值和最大值时一样的；当删除的元素有左右子树，则需要采用后继或者前驱策略（本案例采用后继策略，前驱类似）。
后继：使用比当前需要删除的元素的值大的且最近的节点，替换当前需要删除的元素，即使用当前需要删除的节点的右子树的最小值；
前驱：使用比当前需要删除的元素的值小的且最近的节点，替换当前需要删除的元素，即使用当前需要删除的节点的左子树的最大值；
删除任意节点
时间复杂度分析：
对于链表结构，add、contains、remove操作都需要遍历元素，即是O(n)的时间复杂度；对于二分搜索树来说，如果是满二叉树的情况，上面的操作都是O(h)的时间复杂度，其中 h 为树的高度，并且 h = log n，所以时间复杂度为O(log n)；但是如果二叉树的元素在一边，即 h = n，则时间复杂度跟链表结构是一样的，为 O(n)。
二分搜索树和链表结构的时间复杂度分析
网友评论