二叉树

1、概念：
二叉树是由n（n>=0）个结点组成的有序集合，集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
2、性质：
二叉树中，第 i 层最多有 2i-1 个结点。
如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。
二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。
对于一个二叉树来说，除了度为 0 的叶子结点和度为 2 的结点，剩下的就是度为 1 的结点（设为 n1），那么总结点 n=n0+n1+n2。
同时，对于每一个结点来说都是由其父结点分支表示的，假设树中分枝数为 B，那么总结点数 n=B+1。而分枝数是可以通过 n1 和 n2 表示的，即 B=n1+2n2。所以，n 用另外一种方式表示为 n=n1+2n2+1。
两种方式得到的 n 值组成一个方程组，就可以得出 n0=n2+1。

二叉树类型

1、满二叉树
如果二叉树中所有分支结点的度数都为2，并且叶子结点都在统一层次上，则二叉树为满二叉树。

2、完全二叉树
如果一棵具有n个结点的高度为k的二叉树，树的每个结点都与高度为k的满二叉树中编号为1——n的结点一一对应，则二叉树为完全二叉树。
完全二叉树的特性：
A、同样结点数的二叉树，完全二叉树的高度最小
B、完全二叉树的叶子结点仅出现在最下边两层，并且最底层的叶子结点一定出现在左边，倒数第二层的叶子结点一定出现在右边。
C、完全二叉树中度为1的结点只有左孩子。

3、扩充二叉树

扩充二叉树是对已有二叉树的扩充，扩充后的二叉树的节点都变为度数为2的分支节点。也就是说，如果原节点的度数为2，则不变，度数为1，则增加一个分支，度数为0的叶子节点则增加两个分支。

4、平衡二叉树

又叫二叉排序树，简单而言就是左子树上所有节点的值均小于根节点的值，而右子树上所有结点的值均大于根节点的值，左小右大，并不是乱序，因此得名二叉排序树。

二叉树操作

1、 二叉树的存储结构

二叉树结点包含四个固定的成员：结点的数据域、指向父结点的指针域、指向左子结点的指针域、指向右子结点的指针域。结点的数据域、指向父结点的指针域从TreeNode模板类继承而来。

二叉树的存储方法主要有两种：链式存储法和线性存储法，它们分别对应着链表和数组。完全二叉树最好用数组存放，因为数组下标和父子节点之间存在着完美的对应关系，而且也能够尽最大可能的节省内存。

我们把根节点储存在下标为i=1的位置，那么左子节点储存在2i=2的位置，右子节点储存在下标为2i+1=2的位置。依此类推，完成树的存储。借助下标运算，我们可以很轻松的从父节点跳转到左子节点和右子节点或者从任意一个子节点找到它的父节点。如果X的位置为i，则它的两个子节点的下标分别为2i和2i+1,它的父节点的位置为i/2(这里结果向下取整)。

相比用数组存储数据，链式存储法则相应的更加灵活，我们使用自定义类型Node来表示每一个节点

class Node{int data;Node left,right;
}

每个节点都是一个Node对象，它包含我们所需要存储的数据，指向左子节点的引用，指向右子节点的引用，就像链表一样将整个树串起来。如果该节点没有左子节点，则Node.leftnull或者Node.rightnull，如图：

2、二叉树的遍历

二叉树的遍历有三种方法：前序遍历，中序遍历和后序遍历。

• 前序遍历：
  前序遍历过程是：访问根结点–>先序遍历左子树–>先序遍历右子树

• 中序遍历:
  对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。具体的代码是用递归实现的，比较容易理解。

public void inOrder(Node root){if(root==null) return;inOrder(root.left);System.out.println(root.data);inOrder(root.right);
}

• 后续遍历
  后序遍历过程是：后序遍历左子树–>后序遍历右子树–>访问根结点

3、二叉树的数据操作

数据表示：
完全等同于二叉树的链式存储法，我们定义一个节点类Node来表示二叉查找树上的一个节点，每个节点含有一个键，一个值，一个左链接，一个有链接。其中键和值是为了储存和查找，一般来说，给定键，我们能够快速的找到它所对应的值。

private class Node{private int key;//键private String value;//值，我这里把数据设为String，为了和key区分开private Node left,right;//指向子树的链接public Node(int key,String value);//Java中的构造函数
}

数据查询：
查找操作接受一个键值（key），返回该键值对应的值（value），如果找不到就返回 null。大致思路是：如果树是空的，则查找未命中，返回null；如果被查找的键和根节点的键相等，查找命中，返回根节点对应的值；如果被查找的键较小，则在左子树中继续查找；如果被查找的键较大，则在右子树中继续查找。我们用递归来实现这个操作，具体的代码如下：

public String find(int key){return find(root,key);
}
private String find(Node x,int key){//在以x为根结点的子树中查找并返回键key所对应的值//如果找不到，就返回nullif(x==null) return null;if(key<x.key) return find(x.left,key);else if(key>x.left) return find(x.right,key);else return x.value;
}
// 注意这里用了两个方法，一个私有一个公开，私有的用来递归，公开的对外开放

插入数据：
我们首先判断根节点是不是空节点，如果是空节点，就直接创建一个新的Node对象作为根节点即可；如果根节点非空，就通过while循环以及p.key和key的大小比较不断向下寻找。循环结束时肯定会找到 一个空位置，这时我们就创建一个新的Node对象并把它接在这里。当然还有一种情况，如果p.key==key,就更新这个键键对应的值，结束。
实现方法一（非递归实现）：

public void insert(int key,String value) {//如果根节点为空节点if (root == null) {root = new Node(key,value);return;}//根节点不是空节点Node p = root;while (p != null) {if (key > p.key) { //向右走if (p.right == null) {p.right = new Node(key,value);return;}p = p.right;} else if { // key < p.key,向左走if (p.left == null) {p.left = new Node(key,value);return;}p = p.left;}else p.value=value;//如果原来树中就含有value键，则更新它的值}}

实现方法二（递归实现）：

public void insert(int key,String value){root=insert(root,key,value);
}
private Node insert(Node x,int key,String value){//如果key存在于以x为根节点的子树中则更新它的值；//如果不在就创建新节点插入到合适的位置；if(x==null) return new Node(key,value);if(key<x.key) x.left=insert(x.left,key,value);else if(key>x.key) x.right=insert(x.right,key,value);else x.value=value;return x;
}

查找最大值和最小值
根据二叉查找树的定义，最小值就是最左边的元素，直接从根节点一直向左查找即可。它也有两种实现方式，具体的代码如下：
实现一（递归实现）

public int min(){return min(root).value;
}
private Node min(Node x){if(x.left == null) return x;return min(x.left);
}

实现二（非递归实现）

public int min(){if(root==null) return -1; //表示不存在最小值Node x=root;//沿着左子树一直深入搜索下去，直到遇到左子树为空的节点，此时当前节点为最小值while(x.left!=null) x = x.left;return x.key;
}

查找前驱节点和后继节点
前驱节点指的是小于该键的最大键，后继节点指的是大于该键的最小键。你可以结合中序遍历理解，通过中序遍历，在得到的序列中位于该点左侧的就是前驱节点，右侧的就是后驱节点。

• 前驱节点

1. 若一个节点有左子树，那么该节点的前驱节点是其左子树中最大的节点（也就是左子树中最右边的那个节点）
2. 若一个节点没有左子树，那么判断该节点和其父节点的关系
   2.1 若该节点是其父节点的右子节点，那么该节点的前驱节点即为其父节点。
   2.2 若该节点是其父节点的左子节点，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的右子节点，那么Q就是该节点的后继节点

寻址代码如下：

public int get_prenode(int key){if (root==null)return -1;//-1表示找不到给定的节点if (root.key==key)return -1;Node p = root;Node pp = null;Node  first_parent=null;while (p != null) {if (key>p.key) {pp = p;first_parent=p;p = p.right;} else if (key<p.key) {pp = p; p = p.left;} else {break;}}if(p==null) return -1;else if(p.left!=null) return max(p.left).key;//对应了第1种情况，如果左子树不为空，则前驱一定是左子树的最大值，即小于p的最大值（左子树的值都小于p节点）//以下是左子树为空的情况2.1else if(pp.right==p) return pp.key;//以下是左子树为空的情况2.2else if(pp.left==p) return first_parent.key;return -1;}

向上取整和向下取整

向上取整是指大于等于该键的最小键，向下取整是指小于等于该键的最小值。
向下取整与前驱后继节点的区别在于查找前驱后继节点对应的参数是树中的某一个节点键，而向下取整则允许接受任意的键作为参数，另一方面，向下取整可以包含等于自己的键，是小于等于；

删除操作
1.如果要删除的节点没有子节点，此时的操作时十分容易的，我们只需要将父节点中指向该节点的链接设置为null就可以了。
2.如果要删除的节点只有一个子节点(只有左子节点或只有右子节点)，这种情况也不复杂。我们只需要更新父节点中的指向待删除结点的链接即可，让它指向待删除结点的子节点即可。
3.如果要删除的节点有两个子节点，这时就变得复杂了。你听我仔细描述一下这个过程：我们需要找到这个节点的右子树上的最小结点【记为H】（因为它没有左子节点），把【H】替换到我们计划删除的节点上；然后，再删除这个最小的节点【H】（因为它没有左子节点，所以可以转化成之前的两种情况之一），而且，你会发现，二叉查找树的性质被完美的保留了下来
具体代码：

public void delete(int key){//如果找到键为key的结点，就将它删除，找不到不做处理Node p=root;//p指向需要删除的结点，这里初始化为根节点Node pp=null;//pp记录的是p的父节点//通过while循环查找Key结点while(p!=null&&p.key!=Key){pp=p;if(Key>p.Key) p=p.right;else p=p.left;}if(p==null) return;//没有找到//情况一：要删除的结点有两个子结点if(p.left!=null&&p.right!=null){//查找右子树的最小结点Node minP=p.right;//minP是右子树的最小结点Node minPP=p;//minPP表示minP的父结点while(minP.left!=null){minPP=minP;minP=minP.left;}p.Key=minP.Key;p.val=minP.val;//替换p（将被删除的结点）的键和值//转化，以下问题只需要将minP删除即可//因为minP作为右子树最小的结点，肯定没有左子结点，可以转化为情况二处理p=minP;//使p指向右子树的最小结点pp=minPP;//使被删除结点的父结点指向右子树最小结点的父结点}//情况二：待删除结点是叶子结点（即没有子结点）或者仅有一个子结点Node child;//p的子结点if(p.left!=null) child=p.left;else if(p.right!=null) child=p.right;else child=null;//执行删除操作if(pp==null) root=child;//删除的是根结点else if(pp.left==p) pp.left=child;else pp.right=child;}

引用：https://maimai.cn/article/detail?fid=1502329788&efid=4oPFBA_9fa_8HpwLXZLrVQ&use_rn=1