前言
这里说的树不是日常生活中所见的木本植物,而是一种非线性数据结构
,把它叫做“树”是因为它看起来像一棵颠倒的树,也就是说它是根朝上,而叶朝下的。
在生活中,有很多逻辑关系并不是简单的线性关系,在实际场景中,常常存在着一对多、多对多的情况。例如,企业的上下级关系、家谱族谱图(Family tree),字典的目录,计算机文件目录......
树的基础知识
树(tree
),是包含 n(n ≥ 1)个节点,(n-1) 条边的有限集(注意:当 n=0 时,树是空树)。在任意一个非空树中,它具有以下的特点:
- 有且仅有一个特定的点称为
根节点
; - 当 n > 1 时,除根结点之外,的其余数据元素被分为 m(m ≥ 0)个互不相交的有限集,其中每一个集合本身也是一棵树,被称作原树的子树(subtree)。
如果要把一个节点和边的集合定义为树,那么从根节点到其他任意一个节点都必须有且只有一条
路径。
树的常用术语
根节点(root)
:最顶层的节点,或者说,没有父节点的节点;父节点(parent)
:若一个节点含有子节点,则这个节点称为其子节点的父节点;子节点(child)
:一个节点含有的子树的根节点称为该节点的子节点;兄弟节点(sibling)
:具有相同父节点的节点互称为兄弟节点;叶节点(leaf)
:度为 0 的节点,或者说,没有子节点的点;节点的度
:一个节点含有的子树的个数称为该节点的度;节点的层次
:从根节点开始定义起,根节点为第 1 层,它的子节点为第 2 层,以此类推;树的度
:一棵树中,最大的结点的度称为树的度;树的高度或深度
:树的最大层次数;
......
树的种类
- 无序树:树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树;
- 有序树:树中任意节点的子节点之间有顺序关系,这种树称为有序树;
二叉树:每个节点最多含有两个子树的树称为二叉树;
完全二叉树:对于一颗二叉树,假设其深度为d(d > 1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树;
- 满二叉树:所有叶节点都在最底层的完全二叉树;
- 平衡二叉树(AVL树):当且仅当任何节点的两棵子树的高度差不大于1的二叉树;
- 排序二叉树(Binary Search Tree):也称二叉搜索树、二叉查找树、有序二叉树;
- 霍夫曼树:带权路径最短的二叉树称为哈夫曼树或最优二叉树;
- B树:一种对读写操作进行优化的自平衡的二叉查找树,能够保持数据有序,拥有多于两个子树。
二叉树
- 二叉树(
Binary Tree
):是每个节点最多只有两个
分支(可能只有一个,或者没有)的有序树。它的两个分支,被称作“左子树(left child
)”,“右子树(right child
)”,左子树和右子树又同样都是二叉树。二叉树的分支具有左右次序,不能随意颠倒。 - 满二叉树(
Full Binary Tree
):一棵深度为 k,且有 (2 k − 1) 个节点的二叉树。 - 完全二叉树(
Complete Binary Tree
):在一颗二叉树中,若除最后一层外的其余层都是满的,并且最后一层要么是满的,要么在右边缺少连续若干节点,则此二叉树为完全二叉树。
满二叉树要求所有分支都是满的,而完全二叉树只需要保证最后一个节点之前的节点都齐全即可。
二叉树作为典型的有序树,许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。
二叉树的实现
二叉树的每一个节点都包含三个成员变量:存储数据的变量 val、左子节点 left、右子节点 right。
class TreeNode {
// 节点值
int val;
// 左子节点
TreeNode left;
// 右子节点
TreeNode right;
TreeNode(int x) { val = x; }
}
二叉树属于逻辑结构,也可以使用数组
和链表
实现。
当使用数组实现时,按照层级顺序把二叉树的节点放进数组中对应的位置上,如果某一个节点没有左子节点或右子节点,那么数组对应的位置也会空缺,所以对于一个稀疏的二叉树来说,用数组实现是非常浪费空间的;满二叉树紧凑排列才能不浪费空间。\r\n假设某节点的索引值为 i,那么它左子节点的索引是 (2 i + 1),它右子节点的索引是 (2 i + 2),而它的父节点(如果有)索引则为 (i - 1)/2 。
当使用链表实现时,需要指向子节点的指针,所以实例化每个节点后,需要构建各节点的引用指向。使用链表能避免数组存储浪费空间的问题,算法和结构相对简单,但使用二叉链表,由于缺乏父链的指引,在找回父节点时需要重新扫描树得知父节点的节点地址。
// 实例化节点,n1为根节点
TreeNode n1 = new TreeNode(9);
TreeNode n2 = new TreeNode(6);
TreeNode n3 = new TreeNode(8);
TreeNode n4 = new TreeNode(3);
TreeNode n5 = new TreeNode(4);
// 构建引用指向
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
二叉搜索树
在树中查找数据项的速度和在有序数组中查找一样快,并且插入、删除数据项的速度和链表的一样快。基于这个特点,二叉树最主要的应用在于查找操作
和维持相对顺序
这两个方面。
在查找操作方面,二叉搜索树更合适。它具有以下性质:
- 若任意节点的左子树不空,则左子树上所有节点的值均 < 它的根节点的值;
- 若任意节点的右子树不空,则右子树上所有节点的值均 ≥ 它的根节点的值;
- 任意节点的左、右子树也分别为二叉查找树;
对于一个节点分布相对均衡的二叉搜索树来说,如果节点总数为 N,那么搜索节点的时间复杂度是O(log N)
,更准确来说,是O(log2 N)
,最坏情况下为O(N)
(数列有序时,树退化成线性表),但也有在二叉搜索树基础上改良的平衡树,如 AVL 树,红黑树,可以使树的高度总是得到平衡,时间复杂度在最坏情况下也能达到O(log N)
。
基本操作
// 节点类
class Node{
public int iData;
public Node leftChild;
public Node rightChild;
public void display(){
System.out.print('【');
System.out.print(iData);
System.out.print(',');
System.out.print('】');
}
}
// 树类
class Tree{
// 根节点
private Node root;
public Tree(){ root = null; }
// 搜索节点
public Node find(int key){
Node current = root;
while(current.iData != key){
if (key < current.iData){
current = current.leftChild;
}else {
current = current.rightChild;
}
if (current == null){
return null;
}
}
return current;
}
// 插入节点:必须确定新节点的插入位置
public void insert(int key){
Node newNode = new Node();
newNode.iData = key;
if (root == null){
root = newNode;
}else{
Node current = root;
Node parent;
while(true){
parent = current;
if (key < current.iData){
current = current.leftChild;
if (current == null){
parent.leftChild = newNode;
return ;
}
}else {
current = current.rightChild;
if (current == null){
parent.rightChild = newNode;
return ;
}
}
}
}
}
// 删除节点
public boolean delete(int key){
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while(current.iData != key){
parent = current;
if (key < current.iData){
isLeftChild = true;
current = current.leftChild;
}else {
isLeftChild = false;
current = current.rightChild;
}
if (current == null){
return false;
}
// 删除没有子节点的节点
if (current.leftChild == null && current.rightChild == null){
// 清空根节点
if (current == root){
root = null;
}
// 清空父节点的左叶节点
else if (isLeftChild){
parent.leftChild = null;
}
// 清空父节点的右叶节点
else{
parent.rightChild = null;
}
}
// 删除只有一个子节点的节点
else if (current.rightChild == null){
// 取代根节点
if (current == root){
root = current.leftChild;
}
//
else if (isLeftChild){
parent.leftChild = current.leftChild;
}
//
else{
parent.rightChild = current.leftChild;
}
}
// 删除有两个子节点的节点:后续节点接上
else{
Node successor = getSuccessor(current);
if (current == root){
root = successor;
}else if (isLeftChild){
parent.leftChild = successor;
}else {
parent.rightChild = successor;
}
successor.leftChild = current.leftChild;
}
}
return true;
}
// 找删除节点delNode的后续节点
private Node getSuccessor(Node delNode){
Node successorParent = delNode;
Node successor = delNode;
// delNode的右子节点
Node current = delNode.rightChild;
while(current != null){
successorParent = successor;
successor = current;
current = current.leftChild;
}
if (successor != delNode.rightChild){
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
遍历二叉树
遍历意味着按照某种特定顺序访问树中所有的节点,但是遍历本身是一种线性操作,而二叉树是非线性数据结构,如何将非线性关联的节点转化为线性的序列输出呢?
从宏观的角度来看,二叉树的遍历分为:
深度优先遍历
- 前序遍历
- 中序遍历
- 后序遍历
广度优先遍历
- 层序遍历
如果要使用非递归
的方式实现深度优先遍历,那么需要使用数据结构 栈
实现,以前序为例:
public static void preOrder2(Node t){
Stack<Node> stack = new Stack<>();
Node n = t;
while (n != null || !stack.isEmpty()){
// 迭代访问节点t的左子节点,入栈
while (n != null){
System.out.print(n.iData);
stack.push(n);
n = n.leftChild;
}
// 如果没有左子节点,就弹出,访问右子节点
if (!stack.isEmpty()){
n = stack.pop();
n = n.rightChild;
}
}
}
层序遍历:使用数据结构 队列
实现:
参考
博客园
码农有道
LeetCode:91