二叉树BT与二叉查找树BST概览
1、树
分析HashMap源码的时候，看到JDK8中链表的节点个数超过了泊松分布计算得出的8个节点时，链表将会被转化为红黑树，所以，在分享HaspMap的源码分析文章前，先来分享一下树的数据结构的相关知识。
| 概念 | 英文 |
|---|---|
| 树 | tree |
| 节点 | node |
| 边 | edge |
| 儿子 | child |
| 父亲 | parent |
| 根 | root |
| 树叶 | leaf |
| 兄弟 | siblings |
| 祖父 | grandparent |
| 孙子 | grandchild |
| 祖先 | ancestor |
| 后裔 | descendant |
| 真祖先 | proper ancestor |
| 真后裔 | proper descendant |
| 概念 | 英文 | 解释 |
|---|---|---|
| 节点到节点的路径 | path | 节点到节点间所有节点组成的序列 |
| 路径的长 | length | 路径的长是路径上所有边的条数 |
| 节点的深度 | depth | 从根到节点的唯一路径的长 |
| 节点的高 | height | 节点到一片树叶最长路径的长 |
| 对数 |
|---|
| 对数是对求幂的逆运算 |
如果a的x次方等于N（a>0，且a不等于1），那么数x叫做以a为底N的对数（logarithm），记作x=logaN。其中，a叫做对数的底数，N叫做真数。1.1、树的实现
将每个节点的所有儿子都放在树节点的链表中。
| 树的实现 | 箭头方向 | 英文 |
|---|---|---|
| 向下箭头 | 第一儿子 | firstChild |
| 水平箭头 | 下一兄弟 | nextSibling |
1.2、树的应用-文件目录
| 目录 | 树 |
|---|---|
| 文件名 | 节点 |
| / | 边 |
| 遍历 | 解释 | 英文 |
|---|---|---|
| 先序遍历 | 对节点的处理工作在节点的所有儿子被处理之前进行 | preorder traversal |
| 后续遍历 | 对节点的处理工作在节点的所有儿子被处理之后进行 | postorder traversal |
2、二叉树-BT
| 概念 | 英文 |
|---|---|
| 二叉树 | binary tree |
| 平均/平衡二叉树 | Balanced Binary Tree |
| 二叉排序/查找/搜索树 | binary search/sort tree |
二叉树
每个节点都不能多于2个儿子的树2.1、二叉树的实现
节点是由element元素的信息，加上两个到其他节点的引用left和right组成的结构。
class BinaryNode{Object element;BinaryNode left;BinaryNode right;}
2.2、二叉树的应用-表达式树
表达式树expression tree的树叶是操作数operand，其他的节点为操作符operator。
中序遍历：左、节点、右。
构造表达式树 输入：a b + c d e + * *
输出：
3、二叉查找树 BST
查找树的ADT/Abstract Data Type/抽象数据类型，二叉排序/查找/搜索树。
二叉排序/查找/搜索树
空树或（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树；（4）没有键值相等的结点。平均深度，O(log N)
二叉查找树实现：
public class BinarySearchTree<T extends Comparable<T>> {//二叉查找树根节点private BinaryNode<T> root;//二叉树节点定义private static class BinaryNode<T extends Comparable<T>> {T element; //节点值BinaryNode<T> left; //左节点BinaryNode<T> right; //右节点public BinaryNode(T key) {this(key, null, null);}public BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {this.element = element;this.left = left;this.right = right;}}}
查找是否存在：
/*** 查找是否存在** @param search* @param root* @return*/private boolean contains(T search, BinaryNode<T> root) {if (root == null) {return false;}int compareResult = search.compareTo(root.element);if (compareResult < 0) {return contains(search, root.left);} else {return contains(search, root.right);}}
查找最小值：
/*** 查找最小值** @param root* @return*/private BinaryNode<T> findMin(BinaryNode<T> root) {if (root == null) {return null;}if (root.left == null) {return root;}return findMin(root.left);}
查找最大值：
/*** 查找最大值** @param root* @return*/private BinaryNode<T> findMax(BinaryNode<T> root) {if (root == null) {return null;}if (root.right == null) {return root;}return findMax(root.right);}
插入值：
/*** 插入值** @param insert* @param root* @return*/private BinaryNode<T> insert(T insert, BinaryNode<T> root) {if (root == null) {return new BinaryNode<T>(insert, null, null);}int compareResult = insert.compareTo(root.element);if (compareResult < 0) {root.left = insert(insert, root.left);} else if (compareResult > 0) {root.right = insert(insert, root.right);}return root;}
删除值：
/*** 删除值* 如果是树叶，直接删除* 如果有一个儿子：该节点在其父节点调整自己的链以绕过该节点后被删除* 如果有两个儿子：用该节点右子树的最小的数据代替该节点的数据，并递归地删除该节点** @param remove* @param root* @return*/private BinaryNode<T> remove(T remove, BinaryNode<T> root) {if (root == null) {return root;}int compareResult = remove.compareTo(root.element);if (compareResult < 0) {root.left = remove(remove, root.left);} else if (compareResult > 0) {root.left = remove(remove, root.right);} else if (root.left != null && root.right != null) {//两个儿子root.element = findMin(root.right).element;root.right = remove(root.element, root.right);} else {root = (root.left != null) ? root.left : root.right;}return root;}
前序遍历：
/*** 前序遍历* @param node 待遍历二叉查找树BST根节点*/private void preOrder(BinaryNode<T> node) {if (node != null) {System.out.print(node.key + " ");preOrder(node.left);preOrder(node.right);}}
中序遍历：
/*** 中序遍历* @param node 待遍历BST根节点*/private void midOrder(BinaryNode<T> node) {if (node != null) {midOrder(node.left);System.out.print(node.key + " ");midOrder(node.right);}}
后序遍历：
/*** 后序遍历* @param node 待遍历BST根节点*/private void postOrder(BinaryNode<T> node) {if (node != null) {postOrder(node.left);postOrder(node.right);System.out.print(node.key + " ");}}
4、AVL树
平均二叉/平衡二叉/AVL树
空树或每个节点的左右两子树高度差绝对值<=1的二叉查找树，每个节点的左右两子树都是平衡二叉树。AVL树/Adelson-Velskii和Landis树是带有平衡条件的二叉查找树。空树的高度定义为-1。平衡条件必须要容易保持，它保证了树的深度须是平均深度，O(根号N)
待续……
下一次树的分享将继续讲AVL树、伸展树、B树以及红黑树的相关知识……