数据结构-树
数据结构-树
一、基础知识
树的定义
树的实现
树的遍历
先序遍历
中序遍历
后序遍历
二、二叉树
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 。
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点
二叉树定义
二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。
相关术语
**节点：**包含一个数据元素及若干指向子树分支的信息。
**节点的度：**一个节点拥有子树的数目称为节点的度。
**叶子节点：**也称为终端节点，没有子树的节点或者度为零的节点。
**分支节点：**也称为非终端节点，度不为零的节点称为非终端节点 。
**树的度：**树中所有节点的度的最大值 。
**节点的层次：**从根节点开始，假设根节点为第1层，根节点的子节点为第2层，依此类推，如果某一个节点位于第L层，则其子节点位于第L+1层 。
**树的深度：**也称为树的高度，树中所有节点的层次最大值称为树的深度 。
**有序树：**如果树中各棵子树的次序是有先后次序，则称该树为有序树。
**无序树：**如果树中各棵子树的次序没有先后次序，则称该树为无序树 。
**森林：**由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根节点删除，则该树就变成了一片森林，森林中的树由原来根节点的各棵子树构成 。
特殊类型
**满二叉树：**如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树 。
**完全二叉树：**深度为k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树。
完全二叉树的特点是叶子节点只可能出现在层序最大的两层上，并且某个节点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1
二叉树性质
**性质1：**二叉树的第i层上至多有 2^i-1^（i≥1）个节点。
**性质2：**深度为h的二叉树中至多含有2^h^-1个节点 。
**性质3：**若在任意一棵二叉树中，有n~0~个叶子节点，有n~2~个度为2的节点，则必有n~0~=n~2~+1 。
性质3证明：
设n~1~为二叉树T中度数为1的结点数,n为二叉树结点总数，则有: n=n~0~+n~1~+n~2~ ①。又因为二叉树中除根节点外每一个结点都对应一个分支,则分支数B=n-1,由于这些分支是由度为一和二的结点射出的，所以有B=n~1~+2n~2~, 所以有： n=n~1~+2n~2~+1 ②
联立①②可得 n~0~=n~2~+1
**性质4：**具有n个节点的满二叉树深为log~2~n+1。
证明：假设完全二叉树的深度为k,则根据性质2和完全二叉树的定义有2^(k-1)^ -1 < n <= 2^k^ -1由于n为整数，上式可变为: 2^(k-1)^ <= n < 2^k^两边同时取对数得：k-1 <= log~2~n < k因k为整数，即得k= log~2~n+1
**性质5：**若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点： [6]
当i=1时，该节点为根，它无双亲节点 [6] 。
当i>1时，该节点的双亲节点的编号为i/2 [6] 。
若2i≤n，则有编号为2i的左节点，否则没有左节点 [6] 。
若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点 [6] 。
三、二叉搜索树
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。
注意：二叉排序树并不平衡，在插入删除的时候，不需要考虑平衡性。
定义
一棵空树，或者是具有下列性质的二叉树：
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 左、右子树也分别为二叉排序树；
复杂度
不论哪一种操作，所花的时间都和树的高度成正比。因此，如果共有n个元素，那么平均每次操作需要O(logn)的时间。最坏的情况下，二叉排序树蜕变为单支树，其平均查找时间为(n+1)/2。最好的情况下，二叉树的形态是满二叉树或完全二叉树，其平均查找时间为log~2~n
实现
四、平衡二叉树
平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
4.1 应用
平衡二叉树的出现用于优化二叉树的查询效率。若我们给出一个有序数列，用其生成二叉树会生成一个斜树，使二叉树变成单链结构失去查询速度快的优势。所以出现了平衡二叉树，使任意节点的左子树与右子树的高度差不超过1，使得所有节点较为均匀的分布在二叉树的左右两边，提高了查询效率。
4.2 添加节点
添加节点比较简单，只需要比较添加的数据是大于还是小于当前节点的数据，然后递归执行，直到叶子节点处将数据添加进去。
4.3 删除节点
删除节点相对添加节点要复杂一点，删除节点用有3种情况。
- 第一种：最简单，需要删除的节点不存在孩子节点，直接删除该节点。
- 第二种：只有一个孩子节点，双亲节点与孩子节点交换，然后删除父节点。
- 第三种：拥有两个孩子节点，将右子树最左节点或者左子树最右节点与删除节点交换，然后删除节点。
4.4 平衡
平衡二叉树虽然提高了二叉树的查询效率，但是为了保证二叉树的平衡我们需要花费额外的资源。因此平衡二叉树的插入效率比普通二叉树慢。
当我们插入或删除一个节点时，我们需要更新该节点的所有上级节点的高度，并检查该节点与兄弟节点兄弟节点的高度差是否小于或等于1，若不满足条件将触发平衡二叉树的平衡。
平衡逻辑有4种：
- 第一种：若当前节点左子树比右子树高2且左孩子节点左子树高度大于或等于左孩子节点的右子树，则从当前节点右旋。
- 第二种：与第一种情况相反，右子树比左子树高2且右孩子节点右子树高度大于或等于右孩子节点的左子树，则从当前节点左旋。
- 第三种：若当前节点左子树比右子树高2且左孩子节点左子树高度小于左孩子节点的右子树，则先将左孩子节点左旋，然后从当前节点右旋。
- 第四种：与第三种情况相反，右子树比左子树高2且右孩子节点右子树小于右孩子节点的左子树，则先将右孩子节点右旋，然后从当前节点左旋。
4.5 代码实现
public class AvlBinaryTree{
private int value;
private AvlBinaryTree left;
private AvlBinaryTree right;
private int height = 0;
private AvlBinaryTree(){}
public AvlBinaryTree(int value){
this.value = value;
this.height++;
}
// 获取节点
public AvlBinaryTree get(int value){
if(this.value == value){
return this;
}else if(this.value<value){
return this.right.get(value);
}else{
return this.left.get(value);
}
}
/**
* 小于加入左子树，大于加入右子树，等于不添加
* @param value 数据
*/
public void add(int value){
if(this.height==0){
this.value = value;
this.height = 1;
return;
}
if(value<this.value){
if(Objects.nonNull(this.left)){
this.left.add(value);
}else{
this.left = new AvlBinaryTree(value);
}
}else if(value>this.value){
if(Objects.nonNull(this.right)){
this.right.add(value);
}else{
this.right = new AvlBinaryTree(value);
}
}
updateHeight();
balance();
}
private void updateHeight(){
this.height = Math.max(Objects.nonNull(this.left)?this.left.height:0,
Objects.nonNull(this.right)?this.right.height:0) + 1;
}
// 删除节点
public void delete(int value){
if(this.value<value){
this.right.delete(value);
}else if(this.value>value){
this.left.delete(value);
}else {
if (Objects.isNull(this.left) && Objects.isNull(this.right)) {
this.height = 0;
return;
} else if (Objects.nonNull(this.left) && Objects.isNull(this.right)) {
this.value = this.left.value;
this.height = 1;
this.left = null;
} else if (Objects.isNull(this.left)) {
this.value = this.right.value;
this.height = 1;
this.right = null;
} else {
AvlBinaryTree deleteNode = getMaxNode(this.left);
this.value = deleteNode.value;
this.left.delete(this.value);
}
}
updateHeight();
balance();
}
public int getValue(){
return this.value;
}
/**
* 中序遍历输出
* @return
*/
public String toString(){
return (Objects.nonNull(this.left)&&this.left.height!=0?this.left.toString():"") +
value +
(Objects.nonNull(this.right)&&this.right.height!=0?this.right.toString():"");
}
// 平衡方法1，交换数据平衡法，可用于平衡自己
public void balance(){
int leftHeight = Objects.nonNull(this.left)?this.left.height:0;
int rightHeight = Objects.nonNull(this.right)?this.right.height:0;
// 左高，右旋
if(leftHeight-rightHeight>1){
if(this.right!=null){
int childLeftHeight = Objects.nonNull(this.right.left)?this.right.left.height:0;
int childRightHeight = Objects.nonNull(this.right.right)?this.right.right.height:0;
if(childLeftHeight-childRightHeight<0) {
this.right = leftRotate(this.right);
}
}
int rootValue = this.left.value;
this.left.value = this.value;
this.value = rootValue;
AvlBinaryTree newRight = this.left;
AvlBinaryTree newLeft = this.left.left;
newRight.left = this.left.right;
newRight.right = this.right;
newRight.updateHeight();
this.left = newLeft;
this.right = newRight;
this.updateHeight();
}
// 右高，左旋
if(rightHeight-leftHeight>1){
if(this.left!=null){
int childLeftHeight = Objects.nonNull(this.left.left)?this.right.left.height:0;
int childRightHeight = Objects.nonNull(this.left.right)?this.right.right.height:0;
if(childRightHeight-childLeftHeight<0) {
this.right = rightRotate(this.right);
}
}
int rootValue = this.right.value;
this.right.value = this.value;
this.value = rootValue;
AvlBinaryTree newRight = this.right.right;
AvlBinaryTree newLeft = this.right;
newLeft.right = this.right.left;
newLeft.left = this.left;
newLeft.updateHeight();
this.left = newLeft;
this.right = newRight;
this.updateHeight();
}
}
/**
* 层序输出，用于观察平衡二叉树的结构
* @return
*/
public static String storeyOrder(List<AvlBinaryTree> trees){
List<String> str = new ArrayList<>();
List<AvlBinaryTree> treeList = new ArrayList<>();
for(AvlBinaryTree tree:trees){
if(Objects.nonNull(tree) && tree.height!=0){
str.add(String.valueOf(tree.getValue()));
treeList.add(tree.left);
treeList.add(tree.right);
}else{
str.add(null);
treeList.add(null);
treeList.add(null);
}
}
if(treeList.stream().anyMatch(Objects::nonNull)) {
return str + storeyOrder(treeList);
}else{
for(int i=str.size()-1;i>=0;i--){
if(Objects.isNull(str.get(i))){
str.remove(i);
}else{
break;
}
}
return str.toString();
}
}
// 平衡方法二，不能平衡自己，可用于平衡孩子节点
public static AvlBinaryTree balance(AvlBinaryTree tree){
int leftHeight = Objects.nonNull(tree.left)?tree.left.height:0;
int rightHeight = Objects.nonNull(tree.right)?tree.right.height:0;
// 左高，右旋
if(leftHeight-rightHeight>1){
if(Objects.nonNull(tree.right)){
int childLeftHeight = Objects.nonNull(tree.right.left)?tree.right.left.height:0;
int childRightHeight = Objects.nonNull(tree.right.right)?tree.right.right.height:0;
if(childLeftHeight-childRightHeight<0) {
tree.right = leftRotate(tree.right);
}
}
return rightRotate(tree);
}
// 右高，左旋
if(rightHeight-leftHeight>1){
if(Objects.nonNull(tree.left)){
int childLeftHeight = Objects.nonNull(tree.left.left)?tree.left.left.height:0;
int childRightHeight = Objects.nonNull(tree.left.right)?tree.left.right.height:0;
if(childRightHeight-childLeftHeight<0) {
tree.right = leftRotate(tree.right);
}
}
return leftRotate(tree.right);
}
return tree;
}
// 左旋
public static AvlBinaryTree leftRotate(AvlBinaryTree tree){
AvlBinaryTree newTree = tree.right;
tree.right = newTree.left;
tree.updateHeight();
newTree.left = tree;
newTree.updateHeight();
return newTree;
}
// 右旋
public static AvlBinaryTree rightRotate(AvlBinaryTree tree){
AvlBinaryTree newTree = tree.left;
tree.left = newTree.right;
tree.updateHeight();
newTree.right = tree;
newTree.updateHeight();
return newTree;
}
// 获得最大值节点
public static AvlBinaryTree getMaxNode(AvlBinaryTree tree){
if(Objects.isNull(tree.right) || tree.right.height==0){
return tree;
}else{
return getMaxNode(tree.right);
}
}
// 获得最小值节点
public static AvlBinaryTree getMinNode(AvlBinaryTree tree){
if(Objects.isNull(tree.left) || tree.left.height==0){
return tree;
}else{
return getMinNode(tree.left);
}
}
public static void main(String[] args){
AvlBinaryTree tree = new AvlBinaryTree(3);
tree.add(2);
tree.add(6);
tree.add(5);
tree.add(7);
tree.add(4);
tree.add(8);
tree.add(1);
tree.add(9);
tree.add(10);
tree.delete(3);
// tree = AvlBinaryTree.balance(tree);
System.out.println(tree);
System.out.println(AvlBinaryTree.storeyOrder(List.of(tree)));
}
}
五、红黑树
红黑树（Red Black Tree） 是一种自平衡二叉查找树，他的典型用途是实现数据的查找。它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。
红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。