在计算机科学领域，二叉树和链表是两种常见的数据结构，它们在数据组织和存储中扮演着重要角色。本文将介绍二叉树和链表的基本概念、特点以及实际应用，帮助读者更好地理解这两种数据结构在算法设计和编程中的重要性。让我们一起深入探讨二叉树和链表，揭示它们背后的奥秘和实用之处。
目录
6、树与二叉树
6.1 树的理解
6.2 二叉树的基本概念
6.3 二叉树的遍历
6.4 经典二叉树
6.5 二叉树及其节点的表示
7、List接口分析
7.2 动态数组ArrayList与Vector
7.2.1ArrayList与Vector的区别
7.2.2 ArrayList部分源码分析
7.2.3 Vector部分源码分析
7.3 链表LinkedList
7.3.1 链表与动态数组的区别
7.3.2 LinkedList源码分析
6、树与二叉树
6.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都是
树的深度（或高度）：树中结点的最大层次数，图中树的深度为4
结点的层数：从根节点到树中某结点所经路径上的分支树称为该结点的层数，根节点的层数规定为1，其余结点的层数等于其父亲结点的层数+1
同代：在同一棵树中具有相同层数的节点
6.2 二叉树的基本概念
二叉树（Binary tree）是树形结构的一个重要类型。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。许多实际问题抽象出来的数据结构往往是二叉树形式，二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。
6.3 二叉树的遍历
-
前序遍历：中左右（根左右）
即先访问根结点，再前序遍历左子树，最后再前序遍历右子 树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。
-
中序遍历：左中右服务器托管网（左根右）
即先中前序遍历左子树，然后再访问根结点，最后再中序遍 历右子树。中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。
-
后序遍历：左右中（左右根）
即先后序遍历左子树，然后再后序遍历右子树，最后访问根 结点。后序遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的。
6.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)，效率非常之高。
6.5 二叉树及其节点的表示
普通二叉树：
public class BinaryTree{
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 {
private transient Entry root;
private transient int size = 0;
static final class Entry implements Map.Entry {
K key;
V value;
Entry left;
Entry right;
Entry 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 parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
}7、List接口分析
-
List集合所有的元素是以一种
线性方式进行存储的，例如，存元素的顺序是11、22、33。那么集合中，元素的存储就是按照11、22、33的顺序完成的）。 -
它是一个元素
存取有序的集合。即元素的存入顺序和取出顺序有保证。 -
它是一个
带有索引的集合，通过索引就可以精确的操作集合中的元素（与数组的索引是一个道理）。 -
集合中可以有
重复的元素，通过元素的equals方法，来比较是否为重复的元素。
注意：
List集合关心元素是否有序，而不关心是否重复，请大家记住这个原则。例如“张三”可以领取两个号。
-
List接口的主要实现类
-
ArrayList：动态数组
-
Vector：动态数组
-
LinkedList：双向链表
-
Stack：栈
-
7.2 动态数组ArrayList与Vector
Java的List接口的实现类中有两个动态数组的实现：ArrayList 和 Vector。
7.2.1ArrayList与Vector的区别
它们的底层物理结构都是数组，我们称为动态数组。
-
ArrayList是新版的动态数组，线程不安全，效率高，Vector是旧版的动态数组，线程安全，效率低。
-
动态数组的扩容机制不同，ArrayList默认扩容为原来的1.5倍，Vector默认扩容增加为原来的2倍。
-
数组的初始化容量，如果在构建ArrayList与Vector的集合对象时，没有显式指定初始化容量，那么Vector的内部数组的初始容量默认为10，而ArrayList在JDK 6.0 及之前的版本也是10，JDK8.0 之后的版本ArrayList初始化为长度为0的空数组，之后在添加第一个元素时，再创建长度为10的数组。原因：
-
用的时候，再创建数组，避免浪费。因为很多方法的返回值是ArrayList类型，需要返回一个ArrayList的对象，例如：后期从数据库查询对象的方法，返回值很多就是ArrayList。有可能你要查询的数据不存在，要么返回null，要么返回一个没有元素的ArrayList对象。
-
7.2.2 ArrayList部分源码分析
JDK1.7.0_07中：
//属性
private transient Object[] elementData; //存储底层数组元素
private int size; //记录数组中存储的元素的个数
//构造器
public ArrayList() {
this(10); //指定初始容量为10
}
public ArrayList(int initialCapacity) {
super();
//检查初始容量的合法性
if (initialCapacity 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; //当前数组容量
int newCapacity = oldCapacity + (oldCapacity >> 1); //新数组容量是旧数组容量的1.5倍
if (newCapacity - minCapacity 0)
newCapacity = hugeCapacity(minCapacity);
//复制一个新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
//方法：remove()相关方法
public E remove(int index) {
rangeCheck(index); //判断index是否在有效的范围内
modCount++; //修改次数加1
//取出[index]位置的元素，[index]位置的元素就是要被删除的元素，用于最后返回被删除的元素
E oldValue = elementData(index);
int numMoved = size - index - 1; //确定要移动的次数
//如果需要移动元素，就用System.arraycopy移动元素
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
//将elementData[size-1]位置置空，让GC回收空间，元素个数减少
elementData[--size] = null;
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size) //index不合法的情况
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) { //返回指定位置的元素
return (E) elementData[index];
}
//方法：set()方法相关
public E set(int index, E element) {
rangeCheck(index); //检验index是否合法
//取出[index]位置的元素，[index]位置的元素就是要被替换的元素，用于最后返回被替换的元素
E oldValue = elementData(index);
//用element替换[index]位置的元素
elementData[index] = element;
return oldValue;
}
//方法：get()相关方法
public E get(int index) {
rangeCheck(index); //检验index是否合法
return elementData(index); //返回[index]位置的元素
}
//方法：indexOf()
public int indexOf(Object o) {
//分为o是否为空两种情况
if (o == null) {
//从前往后找
for (int i = 0; i = 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}JDK1.8.0_271中：
//属性
transient Object[] elementData;
private int size;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//构造器
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //初始化为空数组
}
//方法:add()相关方法
public boolean add(E e) {
//查看当前数组是否够多存一个元素
ensureCapacityInternal(size + 1); // Increments modCount!!
//存入新元素到[size]位置，然后size自增1
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果当前数组还是空数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//那么minCapacity取DEFAULT_CAPACITY与minCapacity的最大值
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//查看是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++; //修改次数加1
//如果需要的最小容量比当前数组的长度大，即当前数组不够存，就扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; //当前数组容量
int newCapacity = oldCapacity + (oldCapacity >> 1); //新数组容量是旧数组容量的1.5倍
//看旧数组的1.5倍是否够
if (newCapacity - minCapacity 0)
newCapacity = hugeCapacity(minCapacity);
//复制一个新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}7.2.3 Vector部分源码分析
JDK1.8.0_271中：
//属性
protected Object[] elementData;
protected int elementCount;
//构造器
public Vector() {
this(10); //指定初始容量initialCapacity为10
}
public Vector(int initialCapacity) {
this(initialCapacity, 0); //指定capacityIncrement增量为0
}
public Vector(int initialCapacity, int capacityIncrement) {
super();
//判断了形参初始容量initialCapacity的合法性
if (initialCapacity 0)
grow(minCapacity); //扩容
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; //获取目前数组的长度
//如果capacityIncrement增量是0，新容量 = oldCapacity的2倍
//如果capacityIncrement增量是不是0，新容量 = oldCapacity + capacityIncrement增量;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
//如果按照上面计算的新容量还不够，就按照你指定的需要的最小容量来扩容minCapacity
if (newCapacity - minCapacity 0)
newCapacity = hugeCapacity(minCapacity);
//把旧数组中的数据复制到新数组中，新数组的长度为newCapacity
elementData = Arrays.copyOf(elementData, newCapacity);
}
//方法：remove()相关方法
public boolean remove(Object o) {
return removeElement(o);
}
public synchronized boolean removeElement(Object obj) {
modCount++;
//查找obj在当前Vector中的下标
int i = indexOf(obj);
//如果i>=0，说明存在，删除[i]位置的元素
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}
//方法：indexOf()
public int indexOf(Object o) {
return indexOf(o, 0);
}
public synchronized int indexOf(Object o, int index) {
if (o == null) {//要查找的元素是null值
for (int i = index ; i = elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
else if (index 0) {
//把index+1位置以及后面的元素往前移动
//index+1的位置的元素移动到index位置，依次类推
//一共移动j个
System.arraycopy(elementData, index + 1, elementData, index, j);
}
//元素的总个数减少
elementCount--;
//将elementData[elementCount]这个位置置空，用来添加新元素，位置的元素等着被GC回收
elementData[elementCount] = null; /* to let gc do its work */
}7.3 链表LinkedList
Java中有双链表的实现：LinkedList，它是List接口的实现类。
LinkedList是一个双向链表
7.3.1 链表与动态数组的区别
动态数组底层的物理结构是数组，因此根据索引访问的效率非常高。但是非末尾位置的插入和删除效率不高，因为涉及到移动元素。另外添加操作时涉及到扩容问题，就会增加时空消耗。
链表底层的物理结构是链表，因此根据索引访问的效率不高，即查找元素慢。但是插入和删除不需要移动元素，只需要修改前后元素的指向关系即可，所以插入、删除元素快。而且链表的添加不会涉及到扩容问题。
7.3.2 LinkedList源码分析
JDK1.8.0_271中：
//属性
transient Node first; //记录第一个结点的位置
transient Node last; //记录当前链表的尾元素
transient int size = 0; //记录最后一个结点的位置
//构造器
public LinkedList() {
}
//方法：add()相关方法
public boolean add(E e) {
linkLast(e); //默认把新元素链接到链表尾部
return true;
}
void linkLast(E e) {
final Node l = last; //用 l 记录原来的最后一个结点
//创建新结点
final Node newNode = new Node(l, e, null);
//现在的新结点是最后一个结点了
last = newNode;
//如果l==null，说明原来的链表是空的
if (l == null)
//那么新结点同时也是第一个结点
first = newNode;
else
//否则把新结点链接到原来的最后一个结点的next中
l.next = newNode;
//元素个数增加
size++;
//修改次数增加
modCount++;
}
//其中，Node类定义如下
private static class Node {
E item; //元素数据
Node next; //下一个结点
Node prev; //前一个结点
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
//方法：获取get()相关方法
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//方法：插入add()相关方法
public void add(int index, E element) {
checkPositionIndex(index);//检查index范围
if (index == size)//如果index==size，连接到当前链表的尾部
linkLast(element);
else
linkBefore(element, node(index));
}
Node node(int index) {
// assert isElementIndex(index);
/*
index > 1)采用二分思想，先将index与长度size的一半比较，如果indexsize/2，就只从位置size往前遍历到位置index处。这样可以减少一部
分不必要的遍历。
*/
//如果index> 1)) {
Node x = first;
for (int i = 0; i x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//把新结点插入到[index]位置的结点succ前面
void linkBefore(E e, Node succ) {//succ是[index]位置对应的结点
// assert succ != null;
final Node pred = succ.prev; //[index]位置的前一个结点
//新结点的prev是原来[index]位置的前一个结点
//新结点的next是原来[index]位置的结点
final Node newNode = new Node(pred, e, succ);
//[index]位置对应的结点的prev指向新结点
succ.prev = newNode;
//如果原来[index]位置对应的结点是第一个结点，那么现在新结点是第一个结点
if (pred == null)
first = newNode;
else
pred.next = newNode;//原来[index]位置的前一个结点的next指向新结点
size++;
modCount++;
}
//方法：remove()相关方法
public boolean remove(Object o) {
//分o是否为空两种情况
if (o == null) {
//找到o对应的结点x
for (Node x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);//删除x结点
return true;
}
}
} else {
//找到o对应的结点x
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);//删除x结点
return true;
}
}
}
return false;
}
E unlink(Node x) {//x是要被删除的结点
// assert x != null;
final E element = x.item;//被删除结点的数据
final Node next = x.next;//被删除结点的下一个结点
final Node prev = x.prev;//被删除结点的上一个结点
//如果被删除结点的前面没有结点，说明被删除结点是第一个结点
if (prev == null) {
//那么被删除结点的下一个结点变为第一个结点
first = next;
} else {//被删除结点不是第一个结点
//被删除结点的上一个结点的next指向被删除结点的下一个结点
prev.next = next;
//断开被删除结点与上一个结点的链接
x.prev = null;//使得GC回收
}
//如果被删除结点的后面没有结点，说明被删除结点是最后一个结点
if (next == null) {
//那么被删除结点的上一个结点变为最后一个结点
last = prev;
} else {//被删除结点不是最后一个结点
//被删除结点的下一个结点的prev执行被删除结点的上一个结点
next.prev = prev;
//断开被删除结点与下一个结点的连接
x.next = null;//使得GC回收
}
//把被删除结点的数据也置空，使得GC回收
x.item = null;
//元素个数减少
size--;
//修改次数增加
modCount++;
//返回被删除结点的数据
return element;
}
public E remove(int index) { //index是要删除元素的索引位置
checkElementIndex(index);
return unlink(node(index));
}服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
