引言
前面提到的顺序表和单链表对于元素的访问都有自己的局限性，而二叉树的结构兼具完美解决了二者的访问元素效率问题，原因是它的节点结构存放了左右两个子节点，左边的元素小于父节点，右边的元素大于父节点，它是的二分法思想运用的典型。我们访问节点，如查找时，都会从根节点出发，比较元素确定查找的方向，遍历的次数最大为树的深度，时间复杂度为O(lgN)。相应的，由于是非线性结构，它的各种操作的实现也相对复杂许多。由于树的内容确实比较多，仅仅一篇博文肯定不够，本篇主要讲它的基本实现，如插入、查找、遍历、包含等操作，大部分操作采用遍历和递归分别实现。二叉树的应用相当广泛，java的中的集合框架(HashMap、TreeSet等等)、赫夫曼编码、数据库索引等等方面都会用到，在数据结构中非常重要，修炼内功必备！希望大家认真研究。
二叉树的概念
1.定义:二叉树（Binary Tree）是n(n≥0)个结点组成的有限集合，n=0时称为空二叉树；n>0的二叉树由一个根结点和两棵互不相交、分别称为左子树和右子树的子二叉树构成，二叉树也是递归定义的，在树种定义的度、层次等术语，同样适用于二叉树。
说白了，它由一个根节点和若干子节点构成，每个一个节点最多有俩子节点，逻辑结构和分叉的树一样。
2.相关术语:
1>根节点:没有双亲的节点，也是整个树的代表;
2>孩子节点:一个节点的子树的根节点为其孩子节点;
3>父母节点:和孩子节点对应，是孩子节点的前驱,父母节点挂载孩子节点;
4>兄弟节点:同一父母节点下的孩子节点;
5>叶子节点:没有孩子节点的节点，处于树的最下层;
6>树的层(高度):反应树的层次，约定根的层为1，没向下遍历一次则层数+1。它的本质反应了从根节点到所有叶子节点遍历路径中最长的路径长度,可以反应树的访问效率。
二叉树是一个递归结构，它的子树和自己结构相同，大部分操作都可以通过递归实现，递归的结束条件问遍历到叶子节点，此时的主要工作就是对最简单的树结构进行处理。最简单的树结构有五种基本状态:
1>空树:根节点为空;
2>只有根节点的树:
3>只有左孩子或者右孩子的树;
4>有左右孩子的树。
二叉树的抽象数据结构描述
1>节点类:
package tree;
/**
* Created by chenming on 16/12/30.
*/
public class BinaryNode<T extends Comparable> {
public BinaryNode<T> left;//左结点
public BinaryNode<T> right;//右结点
public int mDupCount;//重复的节点值放到一个节点,mDupCount=1表示重复次数为1,两个相同值
public T data;
public BinaryNode(T data,BinaryNode left,BinaryNode right){
this.data=data;
this.left=left;
this.right=right;
}
public BinaryNode(T data){
this(data,null,null);
}
/**
* 判断是否为叶子结点
* @return
*/
public boolean isLeaf(){
return this.left==null&&this.right==null;
}
}
本文采用二叉链表存储结构，它持有左右孩子的节点引用;持有的元素类型需要实现Comparable接口用于比较。
2>顶层接口定义:
package tree;
/**
* Created by chenming on 16/12/30.
*/
public interface Tree<T extends Comparable> {
/**
* 判空
* @return
*/
boolean isEmpty();
/**
* 二叉树的结点个数
* @return
*/
int size();
/**
* 返回二叉树的高度或者深度,即结点的最大层次
* @return
*/
int height();
/**
* 先根次序遍历
*/
String preOrder();
/**
* 中根次序遍历
*/
String inOrder();
/**
* 后根次序遍历
*/
String postOrder();
/**
* 层次遍历
*/
String levelOrder();
/**
* 将data 插入
* @return
*/
void insert(T data);
/**
* 删除
*/
void remove(T data);
/**
* 查找最大值
* @return
*/
T findMin();
/**
* 查找最小值
* @return
*/
T findMax();
/**
* 根据值找到结点
* @param data
* @return
*/
BinaryNode findNode(T data);
/**
* 是否包含某个值
* @param data
* @return
*/
boolean contains(T data) throws Exception;
/**
* 清空
*/
void clear();
}
3>SearchTree的定义
/**
* Created by chenming on 2018/6/1
* 排序二叉树树的复习,方法尽量提供循环和递归两种方式实现
*/
public class SearchTree<T extends Comparable> implements Tree<T> {
private BinaryNode<T> mRoot;
public SearchTree() {
mRoot = null;
}
......
}
成员变量很简单，仅仅包含根节点，所有操作均从它开始。
二叉树的插入元素
1>循环实现:比较当前节点和待插入元素的大小,如果待插入元素大，则向左树遍历，否则向右子树遍历,直到遍历到叶子节点，它的父节点挂载新节点。代码如下:
/**
* 循环插入
*/
private void insertByTrans(T data) {
BinaryNode<T> newNode = new BinaryNode<>(data);
if (mRoot == null) {
mRoot = newNode;
return;
}
BinaryNode<T> curNode = mRoot;//从根节点出发
BinaryNode<T> parentNode = mRoot;//当前节点的父节点
boolean isLeft = false;//标记插入位置是左还是右
while (curNode != null) {
//循环体：判断大小
parentNode = curNode;//保存父节点
int compare = data.compareTo(curNode.data);
if (compare > 0) {//data较大
//curNode往右走
isLeft = false;
curNode = curNode.right;
} else if (compare < 0) {
//curNode往左走
curNode = curNode.left;
isLeft = true;
} else {
curNode.mDupCount++;
}
}
//挂载新节点
if (isLeft) {
parentNode.left = newNode;
} else {
parentNode.right = newNode;
}
}
2>递归插入:每次递归做如下操作:比较元素，判断大小，然后向子树递归插入；
node.left = insertByRecursion(node.left, data);
or:
node.right = insertByRecursion(node.right, data);
递归结束条件:node为空，表示已经遍历到叶子节点的下一层，此时返回新建节点.完整代码如下:
/**
* 递归插入元素
*
* @param node 子树节点
* @param data 插入数据
*/
private BinaryNode<T> insertByRecursion(BinaryNode<T> node, T data) {
//递归结束条件 node == null表示已经到叶子节点的下面一层了，挂载新节点,返回
if (node == null) {
node = new BinaryNode<>(data);//连接新节点返回给上一层链接
} else {//向左右子树递归
//递归比较
int compare = data.compareTo(node.data);
if (compare < 0) {//左
node.left = insertByRecursion(node.left, data);//由于插入操作需要链接节点,所以需要将低层次的node返回给上一层次的rootNode
} else if (compare > 0) {//右
node.right = insertByRecursion(node.right, data);
} else {//相等
node.mDupCount++;//重复计数+1
}
}
return node;
}
二叉树的查找元素
二叉树的查找和插入元素的原理基本一样，不再赘述，具体看代码:
@Override
public BinaryNode findNode(T data) {
return findNodeByTrans(data);
// return findNodeByRecursion(mRoot, data);
}
/**
* 循环查找
*
* @param data
* @return
*/
private BinaryNode findNodeByTrans(T data) {
if (mRoot == null) {
return null;
}
BinaryNode<T> curNode = mRoot;
while (curNode != null) {
int compare = data.compareTo(curNode.data);
if (compare > 0) {//data较大
//curNode往右走
curNode = curNode.right;
} else if (compare < 0) {
//curNode往左走
curNode = curNode.left;
} else {//相等,则查找到
return curNode;
}
}
return null;
}
/**
* 递归查找元素
*
* @param data
* @return
*/
private BinaryNode findNodeByRecursion(T data) {
return findNodeByRecursion(mRoot, data);
}
/**
* 当前子树节点
*
* @param node
* @param data
*/
public BinaryNode findNodeByRecursion(BinaryNode<T> node, T data) {
//递归结束条件：子树节点为空 or node.data = data
if (node == null) {
return null;
}
int compare = data.compareTo(node.data);
if (compare == 0) {//找到匹配元素,返回
return node;
}
//否则向左右子树递归
if (compare > 0) {//右子树递归
return findNodeByRecursion(node.right, data);
} else {
return findNodeByRecursion(node.left, data);
}
}
二叉树的包含判断
有了查找元素的实现，包含判断水到渠成:
/**
* 是否包含元素
*
* @param data
* @return
* @throws Exception
*/
@Override
public boolean contains(T data) {
// return containsByRecursion(data, mRoot);
return containsByTrans(data);
}
/***
* 递归判断是否包含元素
* @param data
* @param tree
* @return
*/
public boolean containsByRecursion(T data, BinaryNode<T> tree) {
if (data == null) {
return false;
}
if (tree == null) {//遍历到叶子节点的下一层，表示遍历完毕，递归结束
return false;
}
int compareResult = data.compareTo(tree.data);
if (compareResult == 0) {//相等则返回ture
return true;
} else if (compareResult > 0) {
return containsByRecursion(data, tree.right);//向右子树遍历
} else if (compareResult < 0) {
return containsByRecursion(data, tree.left);//向右左子树遍历
}
return false;
}
/**
* 循环判断是否包含某个元素
*
* @param data
* @return
*/
public boolean containsByTrans(T data) {
BinaryNode<T> p = mRoot;
while (p != null) {
int compareResult = data.compareTo(p.data);
if (compareResult == 0) {
return true;
} else if (compareResult > 0) {
p = p.right;
} else {
p = p.left;
}
}
return false;
}
二叉树查找最值
循环和递归实现思路和查找元素基本一样，具体看代码实现:
@Override
public T findMin() {
// return findMinByTrans(mRoot);
return findMinRecursion(mRoot);
}
/**
* 循环查找最小值
*
* @param root
* @return
*/
public T findMinByTrans(BinaryNode<T> root) {
BinaryNode<T> p = root;
while (p.left != null) {
p = p.left;
}
return p.data;
}
/**
* 递归查找最小值
*
* @param root
* @return
*/
public T findMinRecursion(BinaryNode<T> root) {
if (root.left == null) {
return root.data;
}
return findMinRecursion(root.left);
}
/**
* 循环查找最小值
*
* @param root
* @return
*/
public T findMaxByTrans(BinaryNode<T> root) {
BinaryNode<T> p = root;
while (p.right != null) {
p = p.right;
}
return p.data;
}
/**
* 递归查找最小值
*
* @param root
* @return
*/
public T findMaxRecursion(BinaryNode<T> root) {
if (root.right == null) {
return root.data;
}
return findMaxRecursion(root.right);
}
@Override
public T findMax() {
return findMaxRecursion(mRoot);
// return findMaxByTrans(mRoot);
}
二叉树删除元素
删除元素相对于增加和查找元素相对复杂些，原因有二:
1)二叉树是非线性结构,节点之间的断开和连接操作比较复杂;
2)二叉树的基本结构有五种，所以删除元素考虑的情况比较多。
设要删除的结点为q，其父母结点为p，删除节点的大致思路如下:
① 如果要删除的结点q恰好是叶子结点，那么它可以立即被删除
② 如果要删除的结点q拥有一个孩子结点，则应该调整要被删除的父结点(p.left 或 p.right)指向被删除结点的孩子结点（q.left 或 q.right）
③如果要删除的结点q拥有两个孩子结点，则删除策略是用q的右子树的最小的节点(中继节点)数据替代要被删除结点的数据，并递归删除用于中继节点(此时该结点已为空)，或者在右子树中删除中继节点，然后将它替换到q的位置，此时二叉查找树的结构并不会被打乱，其特性仍旧生效。采用这样策略的主要原因是右子树的最小结点的数据替换要被删除的结点后可以满足维持二叉查找树的结构和特性，又因为右子树最小结点不可能有左孩子，删除起来也相对简单些。
删除元素的节点情况如下图:
删除点分析(图片摘自泽坚博客).png
1>删除元素递归实现:
/**
* 递归删除元素
* 1.当找到目标节点时，分三种情况删除元素
* 1>叶子节点，直接删除
* 2>带一个子节点,父节点指向它的子节点
* 3>带俩节点，找到右子树的最小元素(中继节点)，替换当前节点,并递归删除右子树的这个中继节点
*
* @param data
* @param p
* @return
*/
public BinaryNode<T> removeByRecursion(T data, BinaryNode<T> p) {
if (p == null) {
return null;//没有找到元素,返回空
}
int compareResult = data.compareTo(p.data);
if (compareResult < 0) {//左边查找删除结点
//左边相当于父节点，右边相当于删除节点后的子节点
p.left = removeByRecursion(data, p.left);
} else if (compareResult > 0) {
p.right = removeByRecursion(data, p.right);
} else {
//找到目标节点，删除分三种情况
if (p.left != null && p.right != null) {
//情况3 找到中继节点,替换元素，删除它
p.data = findMinByTrans(p.right);//找到中继节点
p.right = removeByRecursion(p.data, p.right);//右子树删除这个中继节点
} else {//情况1和2，遍历到最下面了
p = (p.left != null) ? p.left : p.right;
}
}
return p;//返回删除后的子树节点,用于返回上层递归连接父节点
}
2>删除元素的循环实现:
1)先找到目标位置，并记录它的父节点;
2)根据目标节点的子节点挂载情况分前面已经分析的三种情况分析。
代码如下:
/**
* 循环删除
*
* @param data
* @return
*/
public BinaryNode<T> removeByTrans(T data) {
//找到目标节点
if (data == null) {
return null;
}
BinaryNode<T> current = mRoot;
BinaryNode<T> parent = mRoot;//记录父节点
//判断左右孩子的flag
boolean isLeft = true;
//找到要删除的结点
while (data.compareTo(current.data) != 0) {
//更新父结点记录
parent = current;
int result = data.compareTo(current.data);
if (result < 0) {//从左子树查找
isLeft = true;
current = current.left;
} else if (result > 0) {//从右子树查找
isLeft = false;
current = current.right;
}
//如果没有找到,返回null
if (current == null) {
return null;
}
}
//找到目标位置,判断它的挂载情况
//删除叶子节点
if (current.left == null && current.right == null) {
if (current == mRoot) {
mRoot = null;
} else if (isLeft) {
parent.left = null;
} else {
parent.right = null;
}
} else if (current.left == null) {//right不为空
if (current == mRoot) {
mRoot = current.right;
} else if (isLeft) {
parent.left = current.right;
} else {
parent.right = current.right;
}
} else if (current.right == null) {//left不为空
if (current == mRoot) {
mRoot = current.left;
} else if (isLeft) {
parent.left = current.left;
} else {
parent.right = current.left;
}
} else {//带有俩孩子的节点(说明1)
//找右边子树的最小节点（中继节点）
//找到当前要删除结点current的右子树中的最小值元素
BinaryNode<T> successor = findRelayNode(current);//找到中继节点，并且中继节点的右边子树已经指向了要删除节点的右子树
if (current == mRoot) {
mRoot = successor;
} else if (isLeft) {
parent.left = successor;//左子树连接中继节点
} else {
parent.right = successor;//右子树连接中继节点
}
//把当前要删除的结点的左子树赋值给successor的左子树
successor.left = current.left;
}
return current;
}
/**
* 查找中继节点
*
* @param delNode 要删除的节点
* @return
*/
private BinaryNode<T> findRelayNode(BinaryNode<T> delNode) {
BinaryNode<T> relayNode = delNode;//最小节点
BinaryNode<T> relayParentNode = delNode;//父节点
BinaryNode<T> curNode = delNode.right;//临时遍历变量
while (curNode != null) {
relayParentNode = relayNode;//保存父节点
relayNode = curNode;
curNode = curNode.left;
}
if (relayNode != delNode.right) {
//如果relayNode不是删除节点的直接子节点，relayNode就是要替换delNode的节点,
// 第一步先处理好它的断开操作:relayNode是最小节点，所以它必然在父节点的左边，且没有左子节点
// 所以relayParentNode的左子树指向relayNode的右子树,即可完成relayNode的断开操作
// 断开操作之后,relayNode需要替代delNode,需要把delNode的右边子树赋给relayNode.right
relayParentNode.left = relayNode.right;
//这种情况下relayNode和delNode至少隔了一层，所以需要将delNode的右边子树赋值给relayNode的右子树，
relayNode.right = delNode.right;
}//relayNode == delNode.right时候，说明delNode和relayNode是直接的父子关系，不用额外操作
return relayNode;
}
前面两种情况很容易实现，比较麻烦的是第三种情况。下面是关键代码的说明:
说明1:findRelayNode方法是找到当前要删除节点右子树下面的最小节点作为中继节点，用来替换目标节点(见代码)，将中继节点挂载到目标节点的父节点上，然后将目标节点的左子树挂在到中继节点下，因为中继节点是是从右子树得到的，所以右子树结构不变，只要将目标节点的左子树挂载到中继节点即可实现节点替换;
说明2: 说明1中的代码处理好了目标节点的替换，findRelayNode方法除了寻找中继节点意外，还做了下面几个工作:
① 当中继节点是目标节点的直接子节点时(relayNode == delNode.right)直接返回，因为这种情况下说明1中的处理足够完成替换操作,不用额外处理;
②当relayNode!=delNode.right表明中继节点与目标节点隔了若干层，这就需要调整数的结构了:首先处理好中继节点和父节点的断开操作:relayNode是最小节点，它必然在父节点的左边,且没有左子节点,因此relayNode的右子树挂载到relayParentNode的左子树上,即可完成relayNode的断开操作;断开操作后，这些老数据已经挂载到它父节点的左子树上了，要实现目标节点的替换，需要把目标节点的右子树挂载到中继节点的右子树上。说的很复杂，看图就一目了然了(图中的successor为中继节点):
删除节点示意图(摘自泽坚博客).png
当中继节点是目标节点的直接子节点时:
图片摘自泽坚博客
删除操作相对麻烦，这里花费了很多笔墨说明它，相信大家结合图和代码注释应该能弄透它。
二叉树的遍历
根据节点的访问顺序,二叉树有四种遍历方式
1.前序遍历:先访问根节点，再遍历左右子树;
2.中序遍历:先遍历左子树，再访问根节点，再遍历右子树;
3.后序遍历:先遍历左右子树,再访问根节点;
4.层序遍历:按层从左向右访问.
前序遍历
1>递归实现:
/**
* 递归前序遍历：先访问根节点，在访问左右子树
*
* @param root
* @return
*/
private String preOrderByRecursion(BinaryNode<T> root) {
StringBuilder sb = new StringBuilder();
if (root != null) {//递归结束条件
sb.append(root.data + ", ");//先访问根节点
sb.append(preOrderByRecursion(root.left));
sb.append(preOrderByRecursion(root.right));
}
return sb.toString();
}
2>循环实现:引入栈，保存访问的根节点p，直到最左边的叶子节点，此时表明一条路径走到尽头，弹出栈顶元素，向右子树遍历，继续循环;代码如下:
/**
* 利用栈实现前序遍历,利用栈保存已经访问的节点，实现思想如下：
* 1.当前节点p不为空时,访问节点，并保存入栈
* 2.p节点向左遍历,执行1的操作,直到p为空
* 3.p为空时，表示一条完整的路径已经遍历完,栈顶存放的是上一个节点即当前的父节点,弹出这个父节点，向它的右子树遍历,执行
* p=stack.pop,p = p.right,然后重复1.2.3操作。
* 当p==null && 栈为空时表示遍历完，退出循环
*
* @return
*/
private String preOrderByTrans() {
Stack<BinaryNode<T>> historyNodeStack = new Stack<>();
BinaryNode<T> p = mRoot;
StringBuilder result = new StringBuilder();
while (p != null || !historyNodeStack.isEmpty()) {
if (p == null) {//一条完整路径走到尽头,向父节点的右子树遍历
p = historyNodeStack.pop();//弹出当前的父节点
p = p.right;
} else {
//访问节点,保存路径,向左边遍历直到p=null
result.append(p.data + ",");
historyNodeStack.push(p);
p = p.left;
}
}
return result.toString();
}
中序遍历
1>递归实现:
/**
* 递归中序遍历
*
* @return
*/
public String inOrderByRecursion(BinaryNode root) {
StringBuilder sb = new StringBuilder();
if (root != null) {//递归结束条件
sb.append(inOrderByRecursion(root.left));//先访问左子树
sb.append(root.data + ", ");//访问根节点
sb.append(inOrderByRecursion(root.right));//最后访问右子树
}
return sb.toString();
}
2>循环实现：引入栈存放历史节点，思路和前序遍历基本一致
/**
* 循环中序遍历,和前序引入栈存放经过的路径,这些路径没有被访问，当向左的路径走到尽头，弹栈访问节点，并向右遍历，
* 如果p不为空，则存入stack，向左边遍历
*
* @return
*/
public String inOrderByTrans(BinaryNode root) {
Stack<BinaryNode<T>> historyNodeStack = new Stack<>();
BinaryNode<T> p = mRoot;
StringBuilder result = new StringBuilder();
while (p != null || !historyNodeStack.isEmpty()) {
if (p == null) {//一条完整路径走到尽头,弹栈，并访问它
p = historyNodeStack.pop();
result.append(p.data + ",");
p = p.right;
} else {
//向左边遍历直到p=null
historyNodeStack.push(p);
p = p.left;
}
}
return result.toString();
}
3>后序遍历:注意弹栈的条件是栈顶节点的右子树为空或者被访问过，表明它的右子树已经访问完毕，可以弹栈访问栈顶节点.
/**
* 循环实现后序遍历
*
* @return
*/
public String postOrderByTrans() {
Stack<BinaryNode<T>> stack = new Stack<>();
BinaryNode<T> currentNode = mRoot;
BinaryNode<T> prev = mRoot;
StringBuilder result = new StringBuilder();
while (currentNode != null || !stack.isEmpty()) {
//把左子树加入栈中,直到叶子结点为止,这是左子树先遍历的前提
while (currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.left;
}
if (!stack.isEmpty()) {//当前的栈顶节点未访问，先看看它的右节点是否被访问过或者是否为空，如果是则表示右子树遍历完，可以弹出访问
BinaryNode<T> rightNode = stack.peek().right;
if (rightNode == null || rightNode == prev) {//右子树访问完毕，才弹出父节点
currentNode = stack.pop();//弹出父节点访问
result.append(currentNode.data + ",");
prev = currentNode;
currentNode = null;//curnode=null，避免上面的while重复循环
} else {
currentNode = rightNode;//向右遍历
}
}
}
return result.toString();
}
3>层序遍历:由于层序遍历按层遍历，也就是说左右兄弟节点按层顺序输出，由于兄弟节点以及上下层的的首尾没有直接关系，这里无法用递归实现，需要引入队列保存兄弟节点，每遇到一个节点，就将它的子节点入队，这样就保证兄弟节点按层顺序输出.
/**
* 程序遍历:二叉树的兄弟节点没有直接联系，无法用递归实现,引入队列
*
* @return
*/
@Override
public String levelOrder() {
Queue<BinaryNode<T>> queue = new Queue<>();
StringBuilder result = new StringBuilder();
BinaryNode<T> p = mRoot;
while (p != null) {
result.append(p.data + ",");
//左右子节点入队
if (p.left != null) {
queue.enquene(p.left);
}
//左右子节点入队
if (p.right != null) {
queue.enquene(p.right);
}
p = queue.dequeue();
}
return result.toString();
}
好了，以上就是二叉树的基本实现，内容比较多，然而不仅限于此，后面还有赫夫曼树以及平衡二叉树等内容需要另开篇幅研究。
完整代码地址:数据结构与算法学习JAVA描述GayHub地址
