一、树：
A节点是B节点的父节点， B节点是A节点的子节点。 B、 C、 D这三个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。没有父节点的节点叫作根节点，也就是图中的节点E。没有子节点的节点叫作叶子节点或者叶节点，比如图中的G、 H、 I、 J、 K、 L都是叶子节点。
节电的高度：节点到叶子节点的最长路径（边数）。A的高度为：2
节点的深度：根节点到该节点所经历的边的个数。 A的深度为：1
节点的层数：节点的深度 + 1。A的层数为：2
树的高度：根节点的高度。树的高度为：3
二、二叉树：
1、概念：
每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。
2、特殊二叉树：
<1>、满二叉树：
叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树。如①。
<2>、完全二叉树：
叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。如②。
三、二叉树的存储：
1、基于指针或者引用的二叉链式存储法：
<1>、存储方法：
每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式我们比较常用。大部分二叉树代码都是通过这种结构来实现的。
<2>、图示：
![]()
二叉链式存储
2、基于数组的顺序存储法：
<1>、存储方法：
把根节点存储在下标i = 1的位置，左子节点存储在下标2 * i = 2的位置，右子节点存储在2 * i + 1 = 3的位置。如果节点X存储在数组中下标为i的位置，下标为2 * i 的位置存储的就是左子节点，下标为2 * i + 1的位置存储的就是右子节点。反过来，下标为i/2的位置存储就是它的父节点。通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为1的位置），这样就可以通过下标计算，把整棵树都串起来。
<2>、图示：
![]()
顺序存储
四、二叉树的遍历：
1、前序遍历：
<1>、概念：
对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
<2>、递归的递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
<3>、算法：
void preOrder(Node* root) {
if (root == null) return;
print root // 此处为伪代码，表示打印root节点
preOrder(root->left);
preOrder(root->right);
}
2、中序遍历：
<1>、概念：
对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
<2>、递归的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
<3>、算法：
void inOrder(Node* root) {
if (root == null) return;
inOrder(root->left);
print root // 此处为伪代码，表示打印root节点
inOrder(root->right);
}
3、后序遍历：
<1>、概念：
对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。
<2>、递归的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r
<3>、算法：
void postOrder(Node* root) {
if (root == null) return;
postOrder(root->left);
postOrder(root->right);
print root // 此处为伪代码，表示打印root节点
}
4、二叉树遍历的时间复杂度是O(n)。
五、二叉查找树（Binary Search Tree）：
1、概念：
在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。
2、图示：
![]()
二叉查找树
3、二叉查找树的操作;
1、查找操作：
<1>、二叉查找树中查找一个节点的方法：
先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。
<2>、图示：
![]()
二叉查找树的查找
<3>、算法：
public class BinarySearchTree {
private Node tree;
public Node find(int data) {
Node p = tree;
while (p != null) {
if (data < p.data) p = p.left;
else if (data > p.data) p = p.right;
else return p;
}
return null;
}
public static class Node {
private int data;
private Node left;
private Node right;
public Node(int data) {
this.data = data;
}
}
}
2、插入操作：
<1>、二叉查找树中插入一个节点的方法：
新插入的数据一般都是在叶子节点上，所以只需要从根节点开始，依次比较要插入的数据和节点的大小关系。如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。
<2>、图示：
![]()
二叉查找树的插入
<3>、算法：
public void insert(int data) {
if (tree == null) {
tree = new Node(data);
return;
}
Node p = tree;
while (p != null) {
if (data > p.data) {
if (p.right == null) {
p.right = new Node(data);
return;
}
p = p.right;
} else { // data < p.data
if (p.left == null) {
p.left = new Node(data);
return;
}
p = p.left;
}
}
}
3、删除操作：
<1>、二叉查找树中删除一个节点的方法：
针对要删除节点的子节点个数的不同，分三种情况来处理。
第一种情况是，如果要删除的节点没有子节点，只需要直接将父节点中，指向要删除节点的指针置为null。比如图中的删除节点55。
第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图中的删除节点13。
第三种情况是，如果要删除的节点有两个子节点，需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，可以应用上面两条规则来删除这个最小节点。比如图中的删除节点18。
<2>、图示：
![]()
二叉查找树的删除
<3>、算法：
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null){
return null;
}
TreeNode node=root;
TreeNode lastNode=root;
if(key < node.val){
//删除节点的值小于当前节点，删除节点在左子树上
root.left=deleteNode(root.left,key);
}else if(key > node.val){
//删除节点的值大于当前节点，删除的节点在右子树上
root.right= deleteNode(root.right,key);
}else{
if(root.left ==null || root.right == null){
//无子节点或仅有一个子节点
root= root.left == null ? root.right:root.left;
}else{
//同时有左节点和右节点
TreeNode cur = root.right;
while (cur.left !=null) {
//找到右分支的最小值
cur = cur.left;
}
root.val = cur.val;
root.right = deleteNode(root.right, cur.val);
}
}
return root;
}
}
4、中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是O(n)。
5、如果存储的两个对象键值相同时，解决方法：
①、通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。
②、每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，就将这个要插入的数据放到这个节点的右子树，也就是说，把这个新插入的数据当作大于这个节点的值来处理。当要查找数据的时候，遇到值相同的节点，我们并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来。对于删除操作，也需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除。
