数据结构中的各种树总结

虽然学习了数据结构，但是在平时学习中，发现自己对一些树的基本概念经常混淆，这里进行记录总结。这里只是总结一些基本的概念。

大顶堆和小顶堆

无论是大顶堆还是小顶堆，它的前提条件是：首先是一个完全二叉树

• 大顶堆：任意非叶子结点的值都大于等于子结点的值。 java中创建大顶堆

• 小顶堆：任意非叶子结点的值都小于等于子结点的值。

java中默认创建的是小顶堆。大顶堆创建如下：

//创建一个包含k个元素的大顶堆
Queue<Integer> heap = new PriorityQueue<>(k, (i1, i2) -> 
Integer.compare(i2, i1)); 
//创建一个包含k个元素的小顶堆
Queue<Integer> heap1 = new PriorityQueue<>(k); 

---

完全二叉树

一颗深度为k二叉树，有n个节点，对这棵树进行编号，如果所有的编号都和满二叉树对应，那么这棵树是完全二叉树。

上图是完全二叉树。以下图都不是完全二叉树。


以上图片来自https://blog.csdn.net/weixin_42096624

---

平衡二叉树

平衡二叉树，又称左AVL树。AVL树满足以下条件：

AVL树或者是一棵空树，或者是具有下列性质的非空二叉搜索树：

(1) 任一结点的左、右子树均为AVL树；

(2) 根结点左、右子树高度差绝对值不超过1。

注意：根据定义可以看到AVL树并不要求左右子树结点值和父结点结点值的大小关系。

---

二插搜索树

二叉搜索树，又称二叉排序树。英文为Binary Search Tree，Binary Sort Tree，简写为BST。它既然是搜索树，那肯定是为了提高查找效率而产生的。

BST的定义如下：

1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3. 任意节点的左、右子树也分别为二叉查找树。

4. 没有键值相等的结点。

这里要注意2点：

• BST树它是要求左右子树结点值和父结点值得大小符合上述规律的(可以这么理解：为了便于搜索)；
• 所有结点的键值都不重复。

---