数的特点
- 每个节点有0个或者多个子节点。
- 没有父节点的节点叫做根节点。
- 每一个非根节点有且只有一个父节点。
- 除了根节点，每一个子节点可以分为多个不相交的子树。
数的基本术语
若一个结点有子树，那么该结点称为子树根的"双亲"，子树的根是该结点的"孩子"。有相同双亲的结点互为"兄弟"。一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先。
节点的度: 节点拥有的子树的数目。
叶子节点: 度为0的节点。
分支节点:度不为0的节点。
树的度:树中节点最大的度。
层次:根节点的层次为1。其余节点的层次为，该节点的双亲的层次加上1。
树的高度:树中节点最大的层次。
无序树:树中节点的各个子树的次序不重要，可以交换次序。
有序树:树中节点的各个树的次序重要，不可交换次序。
森林:由多个不相交的树组成，给深林加上一个根，就变成树，删除根，树就变成森林。
二叉树的定义
二叉树是每个节点最多有2个子树的结构。二叉树可以是空集。他的五种基本形态如下:
image
- 空集
- 根和空的左右子树
- 根和左子树
- 根和右子树
- 根和左右子树
注意: 根节点的深度是0，高度是1。
二叉树的性质
二叉树有一下几种性质:
- 二叉树第i层上的节点数最多为2^(i-1) (i>=1)。
- 深度为k的二叉树，节点最多为2^k -1个节点 (k>=1)。
- 包含n个节点的二叉树的高度至少为log_2(n+1)。
- 在任意一棵二叉树中，若叶子结点的个数为n0，度为2的结点数为n2，则n0=n2+1。
满二叉树
定义:高度为h，由2^n -1 个节点组成的树，成为满二叉树。
image
完全二叉树
定义: 一棵树中，只有最下面两层节点的可以小于2，并且，最下一层叶子节点集中在靠左的节点上。
特点: 叶子节点只能出现在最下层和次下层。且最下层的叶子节点集中在数的左部。很显然，满二叉树也是完全二叉树的一种，而完全二叉树不一定是满二叉树。
image
二叉查找树
定义：二叉查找树(Binary Search Tree)，又被称为二叉搜索树。设x为二叉查找树中的一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y] <= key[x]；如果y是x的右子树的一个结点，则key[y] >= key[x]。
二叉查找树的特点:
- 若任意节点的左子树不为空，该节点的左子树上所有节点的值，小于根节点的值。
- 任意节点的右子树不为空，该节点的右子树上所有的节点的值，大于该节点的根节点。
- 任意节点的左右子树也分别是二叉查找树。
- 没有键值相等的节点。
二叉树的Java实现
public class BSTree<T extends Comparable<T>> {
private BSTNode<T> mRoot; // 根结点
public class BSTNode<T extends Comparable<T>> {
T key; // 关键字(键值)
BSTNode<T> left; // 左孩子
BSTNode<T> right; // 右孩子
BSTNode<T> parent; // 父结点
public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
this.key = key;
this.parent = parent;
this.left = left;
this.right = right;
}
}
......
}
遍历
这里讲解前序遍历、中序遍历、后序遍历3种方式。
前序遍历
若二叉树非空，执行以下操作:
- 访问根节点
- 先序遍历左子树
- 先序遍历右子树
递归实现前序遍历:
/**
* 二叉树前序遍历
* 递归实现
*/
public void preorderTraversalRecursion(BSTNode<String> rootNode){
if(rootNode==null) return;
//先添加根节点
list.add(rootNode);
//继续左边遍历添加
preorderTraversalRecursion(rootNode.left);
//继续右边的添加
preorderTraversalRecursion(rootNode.right);
}
非递归，利用栈实现二叉查找树的前序遍历:
/**
* 二叉树前序遍历
* 非递归实现
*/
public <T extends Comparable<T>> List<BSTNode<T>> preorderTraversal(BSTNode<T> rootNode){
if(rootNode==null) return null;
List<BSTNode<T>> list=new ArrayList<>();
//利用栈stack存储
Stack<BSTNode<T>> stack=new Stack<>();
stack.push(rootNode);
//遍历stack
while (!stack.isEmpty()){
//取出根节点，并且删除
BSTNode<T> treeNode=stack.pop();
if(treeNode==null) continue;
//先保存根节点
list.add(treeNode);
//注意stack栈是先进后出，所以先推入右边的
//将右节点推入stack栈
if(treeNode.right!=null)
stack.push(treeNode.right);
//将左节点推入stack栈
if(treeNode.left!=null)
stack.push(treeNode.left);
}
return list;
}
中序遍历
若二叉树为非空执行以下操作:
- 中序遍历左子树
- 访问根节点
- 中序遍历右子树
递归实现中序遍历代码:
/**
* 二叉树中遍历
* 递归实现
*/
public void preorderTraversalRecursion(BSTNode<String> rootNode){
if(rootNode==null) return;
//继续左边遍历添加
preorderTraversalRecursion(rootNode.left);
//先添加根节点
list.add(rootNode);
//继续右边的添加
preorderTraversalRecursion(rootNode.right);
}
只改变了，中间代码执行的顺序
非递归实现中序遍历:
/**
* 二叉树中序遍历
* 非递归实现
* 思路：利用栈从根结点，一直将左子树入栈，直到左子树为null，
* 然后逐个将结点出栈，同时遍历该结点的右子树，
* 遍历右子树为根的子树时，用同样的方法从根节点，一直将左子树入栈。
* test:(null),(单结点)，（默认二叉树）
*/
public <T extends Comparable<T>> List<BSTNode<T>> preorderTraversal(BSTNode<T> rootNode){
if(rootNode==null) return null;
List<BSTNode<T>> list=new ArrayList<>();
//利用栈stack存储
Stack<BSTNode<T>> stack=new Stack<>();
BSTNode<T> curr=rootNode;//当前的节点
stack.push(curr);
//遍历stack
while (!stack.isEmpty()){
//取出根节点
BSTNode<T>roNode=stack.peek();
//将该节点的所有左边节点压入栈
while(roNode.left!=null){
stack.push(roNode.left);
roNode=rootNode.left;
}
//此时的roNode是树的最左边的节点
//访问，节点，退出栈
BSTNode<T>temp=stack.pop();
list.add(temp);
//判断这个节点的右边是否有节点，有就先计算这个节点右边右边
if(temp.right!=null)
stack.push(temp.right);
}
return list;
}
先保存左节点，再将右节点和根节点分别推入栈中
后续遍历
若二叉树非空，执行以下操作
- 后续遍历左字数
- 后续遍历右字数
- 访问根节点
后续遍历递归实现:
/**
* 二叉树后续遍历
* 递归实现
*/
public void preorderTraversalRecursion(BSTNode<String> rootNode){
if(rootNode==null) return;
//继续左边遍历添加
preorderTraversalRecursion(rootNode.left);
//继续右边的添加
preorderTraversalRecursion(rootNode.right);
//先添加根节点
list.add(rootNode);
}
后续遍历非递归实现:
/**
* 二叉树后续
* 非递归实现
* 思路：先将左边节点加入栈，再将右边节点加入栈，最后是根节点
*/
public <T extends Comparable<T>> List<BSTNode<T>> preorderTraversal(BSTNode<T> rootNode){
if(rootNode==null) return null;
List<BSTNode<T>> list=new ArrayList<>();
//利用栈stack存储
Stack<BSTNode<T>> stack=new Stack<>();
BSTNode<T> curr;//当前的节点
BSTNode<T>pre=null;//当前节点的上一个节点
stack.push(rootNode);
//遍历stack
while (!stack.isEmpty()){
//取出根节点
curr=stack.peek();
if(curr.right==null||curr.left==null//当前节点是叶子节点，直接访问
||(pre!=null&&(pre==curr.left||pre==curr.right))//当访问到根节点，直接访问
){
list.add(curr);
stack.pop();
pre=curr;
}else{
//将左右压入栈
if(curr.right!=null)
stack.push(curr.right);
if(curr.left!=null)
stack.push(curr.left);
}
}
return list;
}
二叉树查找树的 查找
查找二叉树中键值为key的节点
递归版本实现:
/**
* (递归实现)查找"二叉树x"中键值为key的节点
*/
public <T extends Comparable<T>> BSTNode<T> search(BSTNode<T> bstNode,T key){
if(key==null||bstNode==null) return null;
int cmp=key.compareTo(bstNode.key);
//查找的数值大于当前节点，继续查找，此节点的右节点
if(cmp>0){
return search(bstNode.right,key);
}else if(cmp<0){
//查找树小于此节点，继续查找此节点的左节点
return search(bstNode.left,key);
}else{
return bstNode;
}
}
查找非递归实现:
/**
* (递归实现)查找"二叉树x"中键值为key的节点
*/
public <T extends Comparable<T>> BSTNode<T> iterativeSearch(BSTNode<T> bstNode,T key){
if(key==null||bstNode==null) return null;
while (bstNode!=null){
int cmp=key.compareTo(bstNode.key);
//查找的数值大于当前节点，继续查找，此节点的右节点
if(cmp>0){
bstNode=bstNode.right;
}else if(cmp<0){
//查找树小于此节点，继续查找此节点的左节点
bstNode=bstNode.left;
}else{
return bstNode;
}
}
return null;
}
最大值和最小值
查找最大值代码
/*
* 查找最大结点：返回tree为根结点的二叉树的最大结点。
* 思路:返回树的最右边的叶子节点
*/
private <T extends Comparable<T>> BSTNode<T> maximum(BSTNode<T> tree) {
if(tree==null) return null;
while (tree.right!=null){
tree=tree.right;
}
return tree;
}
最小值代码
/*
* 查找最小结点：返回tree为根结点的二叉树的最小结点。
* 思路:返回树的最左边节点
*/
private <T extends Comparable<T>> BSTNode<T> minimum(BSTNode<T> tree) {
if(tree==null) return null;
while (tree.left!=null){
tree=tree.left;
}
return tree;
}
前驱和后继
节点的前驱:该节点的左子树中的最大节点。
节点的后继:该节点的右子树的最小节点。
查找前驱节点代码:
/*
* 找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。
*
*/
public <T extends Comparable<T>> BSTNode<T> predecessor(BSTNode<T> x) {
if(x==null) return null;
//如果节点存在左子树，直接求左子树的最大节点
if(x.left!=null) return maximum(x.left);
/**
* 如果左子树为空，存在两种情况
* 1. 这个节点是父节点的右节点
* 这种情况，父节点就是该节点的前驱节点
* 2. 这个节点是父亲节点的左节点
*
* 如果需要找一个比这个节点小的，且最大的节点
* 需要找到最近的父亲节点P1 ，已经P1的父亲P2，且P1在P2的右边
*
* P2< P1
* 根据查找二叉树的特点，右边的大于左边的
* 所以 x>P2
*
*/
BSTNode<T>y=x.parent;
//第一个是当没有父类的时候，停止
//第二个是当父亲节点刚好是在右边的，停止
while (y!=null&&x==y.left){
x=y;
y=y.parent;
}
return y;
}
后继代码:
/*
* 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。
*/
public <T extends Comparable<T>> BSTNode<T> successor(BSTNode<T> x) {
if(x==null) return null;
//如果有右子树，直接找右子树最小的
if(x.right!=null)
return minimum(x.right);
/**
* 如果右子树为空有两种情况
* 1. 该节点是父亲节点的左子树
* 这种情况，后继节点就是父亲节点
* 2. 该节点是父亲节点的右子树
*
* 需要找到父亲节点，的父亲节点，且父亲的父亲的的左节点是父亲节点
*/
BSTNode<T>y=x.parent;
while (y!=null&&x==y.right){
x=y;
y=y.parent;
}
return y;
}
插入
插入节点的代码
/*
* 将结点插入到二叉树中
*
* 参数说明：
* tree 二叉树的
* z 插入的结点
*/
private <T extends Comparable<T>> void insert(BSTree<T> bst, BSTNode<T> z) {
if(z==null||bst==null||bst.mRoot==null) return;
BSTNode<T>rot=bst.mRoot;
BSTNode<T>y=null;//用来存储当前比较的值
int temp=0;
//查找插入的位置
while (rot!=null){
y=rot;
temp=z.key.compareTo(rot.key);
//z比当前的值大，查找右边
if(temp>0){
rot=rot.right;
}else if(temp<0){
rot=rot.left;
}
}
//z插入到当前比较的值
z.parent=y;
//如果y是空的
if(y==null){
//一个parent为空的节点是，根节点
bst.mRoot=z;
}else{
//判断是插入在y的左边还是右边
temp=z.key.compareTo(y.key);
//在右边
if(temp>0)
y.right=z;
else
y.left=z;
}
}
删除
删除节点存在三种情况:
- 没有左右子节点，可以直接删除
- 存在左节点或者右节点，删除后需要移动节点
- 存在左右节点。不能简单删除，需要通过寻找后继节点，转换为上述两种情况
非递归代码如下:
/*
* 删除结点(z)，并返回被删除的结点
*
* 参数说明：
* bst 二叉树
* z 删除的结点
*
* 1. 左右节点都为空，直接删除
* 2. 左右节点有一个为空，删除节点，移动子节点到父亲节点下
* 3. 左右节点都有，删除后继节点，把后继节点的值转移到当前节点。
*/
private <T extends Comparable<T>> BSTNode<T> remove(BSTree<T> bst, BSTNode<T> z) {
if(bst==null||z==null||bst.mRoot==null) return null;
BSTNode<T>x=null;//存储子被删除的节点的子节点child
BSTNode<T>y=null;//要删除的节点
//只有一个节点或者没有节点
if(z.left!=null||z.right!=null){
//z就是要删除的节点
y=z;
}else {
//有两个节点，删除后继节点
y=successor(z);
}
//获取被删除节点的子节点，无论是在左还是右
if(y.left!=null)
x=y.left;
else
x=y.right;
//如果存在子节点，关联子节点和父节点
if(x!=null){
x.parent=y.parent;
}
//如果父节点为空，说明删除的是根节点
if(y.parent==null)
bst.mRoot=z;
//如果要删除的节点是父节点的左节点，关联左节点
else if(y==y.parent.left){
y.parent.left=x;
}
//如果要删除的是父亲节点的右节点
else if(y==y.parent.right){
y.parent.right=x;
}
//如果要删除的节点和刚开始传入的节点不一样就是后继节点
//需要将值传递过去
if(z!=y)
z.key=y.key;
return y;
}
打印二叉树
代码如下:
/*
* 打印"二叉查找树"
*
* key -- 节点的键值
* direction -- 0，表示该节点是根节点;
* -1，表示该节点是它的父结点的左孩子;
* 1，表示该节点是它的父结点的右孩子。
*/
private <T extends Comparable<T>> void print(BSTNode<T> tree, T key, int direction) {
if(tree==null) return;
if(direction==0) // tree是根节点
System.out.printf("%2d is root\n", tree.key);
else // tree是分支节点
System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1?"right" : "left");
//打印左节点
print(tree.left,key,-1);
//打印右节点
print(tree.left,key,1);
}
销毁
销毁二叉树的代码
/*
* 销毁二叉树
*/
private <T extends Comparable<T>> void destroy(BSTNode<T> tree) {
if(tree==null) return;
//先删除左子树
if(tree.left!=null)
destroy(tree.left);
//再删除右子树
if(tree.right!=null)
destroy(tree.right);
tree=null;
}
树的深度/广度优先遍历
树的深度优先遍历需要用到额外的数据结构-> 栈。
- 其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
深度遍历代码和前序遍历类似。参考上面👆。
树的广度优先遍历需要 队列的辅助。
- 其过程检验来说是对每一层节点依次访问，访问完一层进入下一层，而且每个节点只能访问一次。
非递归实现代码:
/**
* 广度优先遍历
* 采用非递归实现
* 需要辅助数据结构：队列
*/
public <T extends Comparable<T>> void levelOrderTraversal(BSTNode<T> node){
if(node==null) return;
ArrayDeque<BSTNode<T>> arrayDeque=new ArrayDeque<>();
//添加根节点
arrayDeque.add(node);
//编列队列
while (!arrayDeque.isEmpty()){
//移除根节点
BSTNode<T>bstNode=arrayDeque.remove();
// 输出当前节点，或者处理当前节点
System.out.print(node.key+" ");
//推入当前节点的左节点
if(bstNode.left!=null)
arrayDeque.add(bstNode.left);
//推入当前节点的右节点
if(bstNode.right!=null)
arrayDeque.add(bstNode.right);
}
}
