本章介绍了内容如下：
二叉树和完全二叉树，二叉搜索树的概念。二叉搜索树的性质- 二叉搜索树的
遍历方式- 如何在二叉查找树中
查找最大值、最小值和给定的值，- 如何找出某一个元素的
前驱和后继，- 如何在二叉查找树中进行
插入和删除操作。
在二叉搜索树上执行这些基本操作的时间与树的高度成正比，一棵随机构造的二叉搜索树的期望高度为O(lgn)，从而基本动态集合的操作平均时间为θ(lgn)。
1. 二叉树
二叉树（Binary Tree）是一种特殊的树型结构，每个节点至多有两棵子树，且二叉树的子树有左右之分，次序不能颠倒。
由定义可知，二叉树中不存在度（结点拥有的子树数目）大于2的节点。二叉树形状如下下图所示：
二叉树.png
二叉树的性质
（1）在二叉树中的第i层上至多有2^(i-1)个结点（i>=1)
（2）深度为k的二叉树至多有2^k-1个节点（k>=1)
（3）具有n个节点的完全二叉树的深度为log+ 1。
满二叉树：深度为k且具有2^k-1个结点的二叉树。即满二叉树中的每一层上的结点数都是最大的结点数。
完全二叉树：深度为k具有n个结点的二叉树，当且仅当每一个结点与深度为k的满二叉树中的编号从1至n的结点一一对应。
也就是除第 k层外，其它各层 (1～k-1) 的结点数都达到最大个数，第 k层所有的结点都连续集中在最左边，这就是完全二叉树。
可以得到一般结论：满二叉树和完全二叉树是两种特殊形态的二叉树，满二叉树肯定是完全二叉树，但完全二叉树不不一定是满二叉树。
举例如下图是所示：
二叉树1.png
2、二叉搜索树的基本概念
二叉搜索树是按照二叉树结构来组织的，因此可以用二叉链表结构表示。
二叉树与二叉搜索树相比，二叉搜索树需要满足二叉搜索树的性质
二叉查找树中的性质：
设x为二叉查找树中的一个结点。如果y是x的左子树中的一个结点，则>key[y]≤key[x]。如果y是x的右子树中的一个结点，则key[x]≤key[y]
下面给出树的节点的标识的代码
/**
* @Project: 10.dataStructure
* @description: 树的节点
* @author: sunkang
* @create: 2018-08-19 15:08
* @ModificationHistory who when What
**/
public class TreeNode<E> {
//存储的值
public E key;
public TreeNode<E> parent;
public TreeNode<E> left;
public TreeNode<E> right;
@Override
public String toString() {
return "TreeNode{" +
"key=" + key +
", parent=" + parent +
", left=" + left +
", right=" + right +
'}';
}
public TreeNode(E key) {
this.key = key;
}
}
3、二叉搜索树的遍历
二叉树的遍历方式有：前序遍历，中序遍历，后续遍历
中序遍历是一种有序的遍历方式，
假设一个节点为p, 遍历的方式为p-->p.left-->p.right
下面是遍历的代码实现
/**
* 前序遍历树
* @param node
*/
public void preOrder(TreeNode<E> node){
if(node != null){
System.out.print(node.key+",");
preOrder(node.left);
preOrder(node.right);
}
}
/**
* 中序遍历树
* @param node
*/
public void inOrder(TreeNode<E> node){
if(node != null){
inOrder(node.left);
System.out.print(node.key+",");
inOrder(node.right);
}
}
/**
* 后序遍历树
* @param node
*/
public void postOrder(TreeNode<E> node){
if(node != null){
postOrder(node.left);
postOrder(node.right);
System.out.print(node.key+",");
}
}
4、二叉搜索树的查询
(1)查找
在二叉查找树中查找一个给定的关键字k的过程与二分查找很类似，根据二叉查找树在的关键字存放的特征，很容易得出查找过程：首先是关键字k与树根的关键字进行比较，如果k大比根的关键字大，则在根的右子树中查找，否则在根的左子树中查找，重复此过程，直到找到与遇到空结点为止。例如下图所示的查找关键字13的过程：（查找过程每次在左右子树中做出选择，减少一半的工作量）
二叉树查找.png
查找的递归代码和非递归代码如下
/**
* 查找特定值的节点
* @param node
* @param key
* @return
*/
public TreeNode<Integer> search(TreeNode<Integer> node, int key ){
while (node != null && node.key != key){
if(key < node.key){
node = node.left;
}else{
node = node.right;
}
}
return node;
}
/**
* 通过递归的形式查找特定值的节点
* @param node
* @param key
* @return
*/
public TreeNode<Integer> searchByRecursion(TreeNode<Integer> node,int key){
if( node == null || node.key == key){
return node;
}
if(key <node.key){
return searchByRecursion(node.left,key);
}else{
return searchByRecursion(node.right,key);
}
}
(2)查找最大关键字和最小关键字
根据二叉查找树的特征，很容易查找出最大和最小关键字。查找二叉树中的最小关键字：从根结点开始，沿着各个节点的left指针查找下去，直到遇到NULL时结束。如果一个结点x无左子树，则以x为根的子树中，最小关键字就是key[x]。查找二叉树中的最大关键字：从根结点开始，沿着各个结点的right指针查找下去，直到遇到NULL时结束
代码如下：
/**
* 查找树的最大节点
* @param node
* @return
*/
public TreeNode<E> maximum(TreeNode<E> node){
while(node!= null && node.right!=null){
node = node.right;
}
return node;
}
/**
* 查找树的最小节点
* @param node
* @return
*/
public TreeNode<Integer> minmum(TreeNode<Integer> node){
while( node!= null && node.left !=null){
node= node.left;
}
return node;
}
(3)前驱和后继
给定一个二叉查找树中的结点，找出在中序遍历顺序下某个节点的前驱和后继。如果树中所有关键字都不相同，则某一结点x的前驱就是小于key[x]的所有关键字中最大的那个结点，后继即是大于key[x]中的所有关键字中最小的那个结点。
查找前驱步骤：先判断x是否有左子树，如果有则在left[x]中查找关键字最大的结点(左子树最大)，即是x的前驱。如果没有左子树，则从x继续向上执行此操作，直到遇到某个这样一个节点，该节点的左子树的最大值即为x节点。
/**
* 查找指定节点的后继节点
*
* @return
*/
public TreeNode<Integer> successor(TreeNode<Integer> node ){
// 1.指定节点的右子树的最小节点
if( node != null && node.right != null){
return minmum(node.right);
}
//2. 右节点不存在时，往上面查找符合一个节点y，该节点的左子树的最大值为该查找节点node，该y.key>node.key
TreeNode<Integer> p = node.parent;
while ( p != null && p.right == node){
node = p;
p=p.parent;
}
return p;
}
/**
* 查找指定节点的前驱节点
* @param node
* @return
*/
public TreeNode<E> preSuccessor(TreeNode<E> node){
//1.指定节点的左子树的最大节点
if(node != null && node.left!= null){
return maximum(node.left);
}
//2.左节点不存在时，往上面查找符合一个节点y，该节点的右子树的最小值为该查找节点,该y.key >node.key
TreeNode<E> p = node.parent;
if( p !=null && p.left == node){
node = p;
p = p.parent;
}
return p;
}
5、二叉搜索树的插入和删除
(1)插入
插入结点的位置对应着查找过程中查找不成功时候的结点位置，因此需要从根结点开始查找带插入结点位置，找到位置后插入即可
下面为插入的代码
/**
* 插入节点
* 1.根节点为null的情况
* 2.找到插入节点的位置的父节点，插入父节点的左边
* 3.找到插入节点的位置的父节点，插入父节点的右边
* @param T 树
* @param node 插入节点
*/
public void insert(BinaryTree<Integer> T, TreeNode<Integer> node){
TreeNode<Integer> y = null; //存储插入节点的父节点
TreeNode<Integer> x = T.root;//表示当前节点
while(x != null){
y = x; //记录当时的父节点
if(node.key < x.key ){
x = x.left;
}else{
x = x.right;
}
}
node.parent = y; //插入的节点的父节点指向父节点
//1.根节点为null的情况
if(y == null){
T.root = node;
} else if( node.key < y.key){ //2.找到插入节点的位置的父节点，插入父节点的左边
y.left= node;
} else{ //3.找到插入节点的位置的父节点，插入父节点的右边
y.right = node;
}
}
(2)删除
从二叉查找树中删除给定的结点z，分三种情况讨论：
-
结点z没有左右子树，则修改其父节点p[z]，使其为NULL。删除过程如下图所示：
树删除情况1.png -
如果
结点z只有一个子树（左子树或者右子树），通过在其子结点与父节点建立一条链来删除z。删除过程如下图所示：
树删除情况2.png -
如果
z有两个子女，需要找到后继节点，然后后继节点来替换删除节点，但是后继节点的位置有两种情况
(1)后继节点是删除节点的右子节点
树删除情况3-1.png
(2)后继节点是删除节点的右子节点的最小的左子节点
树删除情况3-2.png
代码如下：
/**
* 删除指定节点
* 有三种情况
* 1.删除节点没有子节点
* 2.删除节点有一个子节点
* 3.删除节点有两个节点（1.删除的节点的后继节点就是该节点的右节点 2.删除节点的后继节点是该节点的右子树的最大节点 ）
* @param T
* @param node
*/
public void delete(BinaryTree<Integer> T, TreeNode<Integer> node){
//1.删除节点的左子节点为null
if( node.left == null){
transplant(T,node,node.right);
}else if( node.right == null){ //2.删除节点的右子节点为null
transplant(T,node,node.left);
}else{
TreeNode<Integer> successor = successor(node);
if( successor.parent != node){ //4.删除节点的有2个子节点，但左子树的后继节点不为该删除节点的左子节点
transplant(T,successor,successor.right);//交换后继节点和后继节点的左子节点，让后继节点和父节点相互指向后继节点的左子节点
//后继节点相互指向删除节点的右节点
successor.right = node.right;
successor.right.parent = successor;
}
//3删除节点的有2个子节点，但左子节点的数据为后继节点
//交换后继节点与删除节点
transplant(T,successor,node);
//让后继节点与删除节点的左子节点相互引用
successor.left=node.left;
successor.left.parent = successor;
}
}
/**
* 替换节点
* 有三种情况
* 1.该原始节点为父节点为null,即为根节点
* 2.该原始节点是父节点的左节点
* 3.该原始节点是父节点的右节点
*
* @param T
* @param orginalNode
* @param replaceNode
*/
private void transplant(BinaryTree<Integer> T,TreeNode<Integer> orginalNode ,TreeNode<Integer> replaceNode){
//1.该原始节点为父节点为null,即为根节点
if(orginalNode !=null && orginalNode.parent ==null){
T.root = replaceNode;
// 2.该原始节点是父节点的左节点
}else if( orginalNode.parent.left == orginalNode){
orginalNode.parent.left = replaceNode;
// 3.该原始节点是父节点的右节点
}else if( orginalNode.parent.right == orginalNode){
orginalNode.parent.right = replaceNode;
}
if(replaceNode != null){
replaceNode.parent = orginalNode.parent;
}
}
6、完整的二叉树的代码
- 树节点TreeNode
/**
* @Project: 10.dataStructure
* @description: 树的节点
* @author: sunkang
* @create: 2018-08-19 15:08
* @ModificationHistory who when What
**/
public class TreeNode<E> {
//存储的值
public E key;
public TreeNode<E> parent;
public TreeNode<E> left;
public TreeNode<E> right;
@Override
public String toString() {
return "TreeNode{" +
"key=" + key +
", parent=" + parent +
", left=" + left +
", right=" + right +
'}';
}
public TreeNode(E key) {
this.key = key;
}
}
- 二叉搜索树BinaryTree
/**
* @Project: 10.dataStructure
* @description:
* @author: sunkang
* @create: 2018-08-19 15:13
* @ModificationHistory who when What
**/
public class BinaryTree<E> {
public TreeNode<E> root;
/**
* 前序遍历树
* @param node
*/
public void preOrder(TreeNode<E> node){
if(node != null){
System.out.print(node.key+",");
preOrder(node.left);
preOrder(node.right);
}
}
/**
* 中序遍历树
* @param node
*/
public void inOrder(TreeNode<E> node){
if(node != null){
inOrder(node.left);
System.out.print(node.key+",");
inOrder(node.right);
}
}
/**
* 后序遍历树
* @param node
*/
public void postOrder(TreeNode<E> node){
if(node != null){
postOrder(node.left);
postOrder(node.right);
System.out.print(node.key+",");
}
}
/**
* 查找特定值的节点
* @param node
* @param key
* @return
*/
public TreeNode<Integer> search(TreeNode<Integer> node, int key ){
while (node != null && node.key != key){
if(key < node.key){
node = node.left;
}else{
node = node.right;
}
}
return node;
}
/**
* 通过递归的形式查找特定值的节点
* @param node
* @param key
* @return
*/
public TreeNode<Integer> searchByRecursion(TreeNode<Integer> node,int key){
if( node == null || node.key == key){
return node;
}
if(key <node.key){
return searchByRecursion(node.left,key);
}else{
return searchByRecursion(node.right,key);
}
}
/**
* 查找树的最大节点
* @param node
* @return
*/
public TreeNode<E> maximum(TreeNode<E> node){
while(node!= null && node.right!=null){
node = node.right;
}
return node;
}
/**
* 查找树的最小节点
* @param node
* @return
*/
public TreeNode<Integer> minmum(TreeNode<Integer> node){
while( node!= null && node.left !=null){
node= node.left;
}
return node;
}
/**
* 查找指定节点的后继节点
*
* @return
*/
public TreeNode<Integer> successor(TreeNode<Integer> node ){
// 1.指定节点的右子树的最小节点
if( node != null && node.right != null){
return minmum(node.right);
}
//2. 右节点不存在时，往上面查找符合一个节点y，该节点的左子树的最大值为该查找节点node，该y.key>node.key
TreeNode<Integer> p = node.parent;
while ( p != null && p.right == node){
node = p;
p=p.parent;
}
return p;
}
/**
* 查找指定节点的前驱节点
* @param node
* @return
*/
public TreeNode<E> preSuccessor(TreeNode<E> node){
//1.指定节点的左子树的最大节点
if(node != null && node.left!= null){
return maximum(node.left);
}
//2.左节点不存在时，往上面查找符合一个节点y，该节点的右子树的最小值为该查找节点,该y.key >node.key
TreeNode<E> p = node.parent;
if( p !=null && p.left == node){
node = p;
p = p.parent;
}
return p;
}
/**
* 插入节点
* 1.根节点为null的情况
* 2.找到插入节点的位置的父节点，插入父节点的左边
* 3.找到插入节点的位置的父节点，插入父节点的右边
* @param T 树
* @param node 插入节点
*/
public void insert(BinaryTree<Integer> T, TreeNode<Integer> node){
TreeNode<Integer> y = null; //存储插入节点的父节点
TreeNode<Integer> x = T.root;//表示当前节点
while(x != null){
y = x; //记录当时的父节点
if(node.key < x.key ){
x = x.left;
}else{
x = x.right;
}
}
node.parent = y; //插入的节点的父节点指向父节点
//1.根节点为null的情况
if(y == null){
T.root = node;
} else if( node.key < y.key){ //2.找到插入节点的位置的父节点，插入父节点的左边
y.left= node;
} else{ //3.找到插入节点的位置的父节点，插入父节点的右边
y.right = node;
}
}
/**
* 删除指定节点
* 有三种情况
* 1.删除节点没有子节点
* 2.删除节点有一个子节点
* 3.删除节点有两个节点（1.删除的节点的后继节点就是该节点的右节点 2.删除节点的后继节点是该节点的右子树的最大节点 ）
* @param T
* @param node
*/
public void delete(BinaryTree<Integer> T, TreeNode<Integer> node){
//1.删除节点的左子节点为null
if( node.left == null){
transplant(T,node,node.right);
}else if( node.right == null){ //2.删除节点的右子节点为null
transplant(T,node,node.left);
}else{
TreeNode<Integer> successor = successor(node);
if( successor.parent != node){ //4.删除节点的有2个子节点，但左子树的后继节点不为该删除节点的左子节点
transplant(T,successor,successor.right);//交换后继节点和后继节点的左子节点，让后继节点和父节点相互指向后继节点的左子节点
//后继节点相互指向删除节点的右节点
successor.right = node.right;
successor.right.parent = successor;
}
//3删除节点的有2个子节点，但左子节点的数据为后继节点
//交换后继节点与删除节点
transplant(T,successor,node);
//让后继节点与删除节点的左子节点相互引用
successor.left=node.left;
successor.left.parent = successor;
}
}
/**
* 替换节点
* 有三种情况
* 1.该原始节点为父节点为null,即为根节点
* 2.该原始节点是父节点的左节点
* 3.该原始节点是父节点的右节点
*
* @param T
* @param orginalNode
* @param replaceNode
*/
private void transplant(BinaryTree<Integer> T,TreeNode<Integer> orginalNode ,TreeNode<Integer> replaceNode){
//1.该原始节点为父节点为null,即为根节点
if(orginalNode !=null && orginalNode.parent ==null){
T.root = replaceNode;
// 2.该原始节点是父节点的左节点
}else if( orginalNode.parent.left == orginalNode){
orginalNode.parent.left = replaceNode;
// 3.该原始节点是父节点的右节点
}else if( orginalNode.parent.right == orginalNode){
orginalNode.parent.right = replaceNode;
}
if(replaceNode != null){
replaceNode.parent = orginalNode.parent;
}
}
/***************************
* 构造下面的树
* 15
* / \
* 6 18
* / \ / \
* 3 7 17 20
* /\ \
* 2 4 13
* /
* 9
***************************/
public static void main(String[] args) {
BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
Integer[] arr = new Integer[]{15,6,18,3,7,17,20,2,4,23,9};
for(Integer key :arr){
TreeNode<Integer> node = new TreeNode<>(key);
binaryTree.insert(binaryTree,node);
}
System.out.println(binaryTree.maximum(binaryTree.root).key);
System.out.println( binaryTree.minmum(binaryTree.root).key);
System.out.println("前序排列:");
//前序排列
binaryTree.preOrder(binaryTree.root);
System.out.println();
//中序排列
System.out.println("中序排列:");
binaryTree.inOrder(binaryTree.root);
System.out.println();
//后序排列
System.out.println("后序排列:");
binaryTree.postOrder(binaryTree.root);
System.out.println();
System.out.print("后继节点：");
System.out.println(binaryTree.successor(binaryTree.root).key);
System.out.print("前序节点：");
System.out.println(binaryTree.preSuccessor(binaryTree.root).key);
System.out.print("跟节点的后继节点的前驱节点:");
System.out.println(binaryTree.preSuccessor(binaryTree.successor(binaryTree.root)).key);
System.out.print("跟节点的前驱节点的后继节点:");
System.out.println(binaryTree.successor(binaryTree.preSuccessor(binaryTree.root)).key);
}
}
7、参考的资料
https://www.cnblogs.com/Anker/archive/2013/01/28/2880581.html
https://www.cnblogs.com/ysocean/p/8032642.html
