树
1. 树的理解
专有名词解释:
结点
:树中的数据元素都称之为结点
根节点
:最上面的结点称之为根,一颗树只有一个根且由根发展而来,从另外一个角度来说,每个结点都可以认为是其子树的根
父节点
:结点的上层结点,如图中,结点K的父节点是E、结点L的父节点是G
子节点
:节点的下层结点,如图中,节点E的子节点是K节点、节点G的子节点是L节点
兄弟节点
:具有相同父节点的结点称为兄弟节点,图中F、G、H互为兄弟节点
结点的度数
:每个结点所拥有的子树的个数称之为结点的度,如结点B的度为3
树叶
:度数为0的结点,也叫作终端结点,图中D、K、F、L、H、I、J都是树叶
非终端节点(或分支节点)
:树叶以外的节点,或度数不为0的节点。图中根、A、B、C、E、G都是
结点的层数
:从根节点到树中某结点所经路径上的分支树称为该结点的层数,根节点的层数规定为1,其余结点的层数等于其父亲结点的层数+1
同代
:在同一棵树中具有相同层数的节点
2. 二叉树的基本概念
二叉树(Binary tree)是树形结构的一个重要类型。二叉树特点是每个结点最多只能有两棵子树,且有左右之分。许多实际问题抽象出来的数据结构往往是二叉树形式,二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。
3. 二叉树的遍历
public class TreeSearch {// 创建一个二叉树public TreeNode getTargetTree() {// 叶子节点TreeNode G = new TreeNode("G");TreeNode D = new TreeNode("D");TreeNode E = new TreeNode("E", G, null);TreeNode B = new TreeNode("B", D, E);TreeNode H = new TreeNode("H");TreeNode I = new TreeNode("I");TreeNode F = new TreeNode("F", H, I);TreeNode C = new TreeNode("C", null, F);// 构造根节点TreeNode root = new TreeNode("A", B, C);return root;}/*** 前序遍历*/public void preorderVistTreeNode(TreeNode node) {if (null != node) {System.out.print(node.value);if (null != node.leftchildren) {preorderVistTreeNode(node.leftchildren);}if (null != node.rightchildre) {preorderVistTreeNode(node.rightchildre);}}}public static void main(String[] args) {TreeSearch treeSearch = new TreeSearch();TreeNode tree = treeSearch.getTargetTree();System.out.print("前序遍历:");treeSearch.preorderVistTreeNode(tree);System.out.println(""); }
}
/**
* 中序遍历
*/
public void inorderVistTreeNode(TreeNode node){if(null != node){if(null != node.leftchildren){inorderVistTreeNode(node.leftchildren);}System.out.print(node.value);if(null != node.rightchildre){inorderVistTreeNode(node.rightchildre);}}
}public static void main(String[] args) {TreeSearch treeSearch = new TreeSearch();TreeNode tree= treeSearch.getTargetTree();System.out.print("中序遍历:");treeSearch.inorderVistTreeNode(tree);System.out.println("");
}
/*** 后序遍历*/
public void postorderVistTreeNode(TreeNode node){if(null != node){if(null != node.leftchildren){postorderVistTreeNode(node.leftchildren);}if(null != node.rightchildre){postorderVistTreeNode(node.rightchildre);}System.out.print(node.value);}
}public static void main(String[] args) {TreeSearch treeSearch = new TreeSearch();TreeNode tree= treeSearch.getTargetTree();System.out.print("后序遍历:");treeSearch.postorderVistTreeNode(tree);System.out.println("");
}
4. 经典二叉树
1、满二叉树
: 除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树。 第n层的结点数是2的n-1次方,总的结点个数是2的n次方-1
2、完全二叉树
: 叶结点只能出现在最底层的两层,且最底层叶结点均处于次底层叶结点的左侧。
3、二叉排序/查找/搜索树
:即为BST (binary search/sort tree)。满足如下性质:
(1)若它的左子树不为空,则左子树上所有结点的值均小于它的根节点的值;
(2)若它的右子树上所有结点的值均大于它的根节点的值;
(3)它的左、右子树也分别为二叉排序/查找/搜索树。
对二叉查找树进行中序遍历,得到有序集合。便于检索。
4、平衡二叉树
:(Self-balancing binary search tree,AVL)首先是二叉排序树,此外具有以下性质:
(1)它是一棵空树或它的左右两个子树的高度差的绝对值不超过1
(2)并且左右两个子树也都是一棵平衡二叉树
(3)不要求非叶节点都有两个子结点
平衡二叉树的目的是为了减少二叉查找树的层次,提高查找速度。平衡二叉树的常用实现有红黑树、AVL、替罪羊树、Treap、伸展树等。
5、红黑树
:即Red-Black Tree。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。
红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,它是在 1972 年由 Rudolf Bayer 发明的。红黑树是复杂的,但它的操作有着良好的最坏情况运行时间
,并且在实践中是高效的
:它可以在 O(log n)时间内做查找,插入和删除, 这里的 n 是树中元素的数目。
红黑树的特性:
-
每个节点是红色或者黑色
-
根节点是黑色
-
每个叶子节点(NIL)是黑色。(注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点)
-
每个红色节点的两个子节点都是黑色的。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
-
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点(确保没有一条路径会比其他路径长出2倍)
当我们插入或删除节点时,可能会破坏已有的红黑树,使得它不满足以上5个要求,那么此时就需要进行处理,使得它继续满足以上的5个要求:
1、recolor
:将某个节点变红或变黑
2、rotation
:将红黑树某些结点分支进行旋转(左旋或右旋)
红黑树可以通过红色节点和黑色节点尽可能的保证二叉树的平衡。主要是用它来存储有序的数据,它的时间复杂度是O(logN),效率非常之高。
5. 二叉树及其结点的表示
普通二叉树:
public class BinaryTree<E>{private TreeNode root; //二叉树的根结点private int total;//结点总个数private class TreeNode{//至少有以下几个部分TreeNode parent;TreeNode left;E data;TreeNode right;public TreeNode(TreeNode parent, TreeNode left, E data, TreeNode right) {this.parent = parent;this.left = left;this.data = data;this.right = right;}}
}
TreeMap红黑树:
public class TreeMap<K,V> {private transient Entry<K,V> root;private transient int size = 0;static final class Entry<K,V> implements Map.Entry<K,V> {K key;V value;Entry<K,V> left;Entry<K,V> right;Entry<K,V> parent;boolean color = BLACK;/*** Make a new cell with given key, value, and parent, and with* {@code null} child links, and BLACK color.*/Entry(K key, V value, Entry<K,V> parent) {this.key = key;this.value = value;this.parent = parent;}}
}