本章介紹了內(nèi)容如下：
二叉樹和完全二叉樹狞山，二叉搜索樹的概念。二叉搜索樹的性質(zhì)- 二叉搜索樹的
遍歷方式- 如何在二叉查找樹中
查找最大值叉寂、最小值和給定的值萍启，- 如何找出某一個(gè)元素的
前驅(qū)和后繼，- 如何在二叉查找樹中進(jìn)行
插入和刪除操作屏鳍。
在二叉搜索樹上執(zhí)行這些基本操作的時(shí)間與樹的高度成正比勘纯，一棵隨機(jī)構(gòu)造的二叉搜索樹的期望高度為O(lgn)，從而基本動(dòng)態(tài)集合的操作平均時(shí)間為θ(lgn)钓瞭。
1. 二叉樹
二叉樹（Binary Tree）是一種特殊的樹型結(jié)構(gòu)驳遵，每個(gè)節(jié)點(diǎn)至多有兩棵子樹，且二叉樹的子樹有左右之分山涡，次序不能顛倒堤结。
由定義可知，二叉樹中不存在度（結(jié)點(diǎn)擁有的子樹數(shù)目）大于2的節(jié)點(diǎn)鸭丛。二叉樹形狀如下下圖所示：
二叉樹.png
二叉樹的性質(zhì)
（1）在二叉樹中的第i層上至多有2^(i-1)個(gè)結(jié)點(diǎn)（i>=1)
（2）深度為k的二叉樹至多有2^k-1個(gè)節(jié)點(diǎn)（k>=1)
（3）具有n個(gè)節(jié)點(diǎn)的完全二叉樹的深度為log+ 1竞穷。
滿二叉樹：深度為k且具有2^k-1個(gè)結(jié)點(diǎn)的二叉樹。即滿二叉樹中的每一層上的結(jié)點(diǎn)數(shù)都是最大的結(jié)點(diǎn)數(shù)鳞溉。
完全二叉樹：深度為k具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)每一個(gè)結(jié)點(diǎn)與深度為k的滿二叉樹中的編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)看政。
也就是除第 k層外允蚣，其它各層 (1～k-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 k層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊榨崩，這就是完全二叉樹母蛛。
可以得到一般結(jié)論：滿二叉樹和完全二叉樹是兩種特殊形態(tài)的二叉樹前弯，滿二叉樹肯定是完全二叉樹恕出，但完全二叉樹不不一定是滿二叉樹浙巫。
舉例如下圖是所示：
二叉樹1.png
2的畴、二叉搜索樹的基本概念
二叉搜索樹是按照二叉樹結(jié)構(gòu)來組織的丧裁，因此可以用二叉鏈表結(jié)構(gòu)表示煎娇。
二叉樹與二叉搜索樹相比逊桦，二叉搜索樹需要滿足二叉搜索樹的性質(zhì)
二叉查找樹中的性質(zhì)：
設(shè)x為二叉查找樹中的一個(gè)結(jié)點(diǎn)强经。如果y是x的左子樹中的一個(gè)結(jié)點(diǎn)匿情，則>key[y]≤key[x]汁果。如果y是x的右子樹中的一個(gè)結(jié)點(diǎn)据德，則key[x]≤key[y]
下面給出樹的節(jié)點(diǎn)的標(biāo)識(shí)的代碼
/**
* @Project: 10.dataStructure
* @description: 樹的節(jié)點(diǎn)
* @author: sunkang
* @create: 2018-08-19 15:08
* @ModificationHistory who when What
**/
public class TreeNode<E> {
//存儲(chǔ)的值
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棘利、二叉搜索樹的遍歷
二叉樹的遍歷方式有：前序遍歷善玫，中序遍歷茅郎，后續(xù)遍歷
中序遍歷是一種有序的遍歷方式系冗，
假設(shè)一個(gè)節(jié)點(diǎn)為p, 遍歷的方式為p-->p.left-->p.right
下面是遍歷的代碼實(shí)現(xiàn)
/**
* 前序遍歷樹
* @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)查找
在二叉查找樹中查找一個(gè)給定的關(guān)鍵字k的過程與二分查找很類似，根據(jù)二叉查找樹在的關(guān)鍵字存放的特征框仔，很容易得出查找過程：首先是關(guān)鍵字k與樹根的關(guān)鍵字進(jìn)行比較离斩，如果k大比根的關(guān)鍵字大寻馏，則在根的右子樹中查找诚欠，否則在根的左子樹中查找轰绵，重復(fù)此過程左腔，直到找到與遇到空結(jié)點(diǎn)為止液样。例如下圖所示的查找關(guān)鍵字13的過程：（查找過程每次在左右子樹中做出選擇鞭莽，減少一半的工作量）
二叉樹查找.png
查找的遞歸代碼和非遞歸代碼如下
/**
* 查找特定值的節(jié)點(diǎn)
* @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;
}
/**
* 通過遞歸的形式查找特定值的節(jié)點(diǎn)
* @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)查找最大關(guān)鍵字和最小關(guān)鍵字
根據(jù)二叉查找樹的特征，很容易查找出最大和最小關(guān)鍵字丹拯。查找二叉樹中的最小關(guān)鍵字：從根結(jié)點(diǎn)開始乖酬，沿著各個(gè)節(jié)點(diǎn)的left指針查找下去咬像，直到遇到NULL時(shí)結(jié)束县昂。如果一個(gè)結(jié)點(diǎn)x無左子樹倒彰，則以x為根的子樹中待讳，最小關(guān)鍵字就是key[x]创淡。查找二叉樹中的最大關(guān)鍵字：從根結(jié)點(diǎn)開始琳彩，沿著各個(gè)結(jié)點(diǎn)的right指針查找下去术辐，直到遇到NULL時(shí)結(jié)束
代碼如下：
/**
* 查找樹的最大節(jié)點(diǎn)
* @param node
* @return
*/
public TreeNode<E> maximum(TreeNode<E> node){
while(node!= null && node.right!=null){
node = node.right;
}
return node;
}
/**
* 查找樹的最小節(jié)點(diǎn)
* @param node
* @return
*/
public TreeNode<Integer> minmum(TreeNode<Integer> node){
while( node!= null && node.left !=null){
node= node.left;
}
return node;
}
(3)前驅(qū)和后繼
給定一個(gè)二叉查找樹中的結(jié)點(diǎn)辉词，找出在中序遍歷順序下某個(gè)節(jié)點(diǎn)的前驅(qū)和后繼瑞躺。如果樹中所有關(guān)鍵字都不相同幢哨，則某一結(jié)點(diǎn)x的前驅(qū)就是小于key[x]的所有關(guān)鍵字中最大的那個(gè)結(jié)點(diǎn)捞镰，后繼即是大于key[x]中的所有關(guān)鍵字中最小的那個(gè)結(jié)點(diǎn)岸售。
查找前驅(qū)步驟：先判斷x是否有左子樹凸丸，如果有則在left[x]中查找關(guān)鍵字最大的結(jié)點(diǎn)(左子樹最大)屎慢，即是x的前驅(qū)腻惠。如果沒有左子樹妖枚，則從x繼續(xù)向上執(zhí)行此操作绝页，直到遇到某個(gè)這樣一個(gè)節(jié)點(diǎn)续誉，該節(jié)點(diǎn)的左子樹的最大值即為x節(jié)點(diǎn)酷鸦。
/**
* 查找指定節(jié)點(diǎn)的后繼節(jié)點(diǎn)
*
* @return
*/
public TreeNode<Integer> successor(TreeNode<Integer> node ){
// 1.指定節(jié)點(diǎn)的右子樹的最小節(jié)點(diǎn)
if( node != null && node.right != null){
return minmum(node.right);
}
//2. 右節(jié)點(diǎn)不存在時(shí)嘹裂，往上面查找符合一個(gè)節(jié)點(diǎn)y寄狼，該節(jié)點(diǎn)的左子樹的最大值為該查找節(jié)點(diǎn)node泊愧，該y.key>node.key
TreeNode<Integer> p = node.parent;
while ( p != null && p.right == node){
node = p;
p=p.parent;
}
return p;
}
/**
* 查找指定節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
* @param node
* @return
*/
public TreeNode<E> preSuccessor(TreeNode<E> node){
//1.指定節(jié)點(diǎn)的左子樹的最大節(jié)點(diǎn)
if(node != null && node.left!= null){
return maximum(node.left);
}
//2.左節(jié)點(diǎn)不存在時(shí)，往上面查找符合一個(gè)節(jié)點(diǎn)y豪筝，該節(jié)點(diǎn)的右子樹的最小值為該查找節(jié)點(diǎn),該y.key >node.key
TreeNode<E> p = node.parent;
if( p !=null && p.left == node){
node = p;
p = p.parent;
}
return p;
}
5敲街、二叉搜索樹的插入和刪除
(1)插入
插入結(jié)點(diǎn)的位置對(duì)應(yīng)著查找過程中查找不成功時(shí)候的結(jié)點(diǎn)位置聪富，因此需要從根結(jié)點(diǎn)開始查找?guī)Р迦虢Y(jié)點(diǎn)位置著蟹，找到位置后插入即可
下面為插入的代碼
/**
* 插入節(jié)點(diǎn)
* 1.根節(jié)點(diǎn)為null的情況
* 2.找到插入節(jié)點(diǎn)的位置的父節(jié)點(diǎn)萧豆，插入父節(jié)點(diǎn)的左邊
* 3.找到插入節(jié)點(diǎn)的位置的父節(jié)點(diǎn)涮雷，插入父節(jié)點(diǎn)的右邊
* @param T 樹
* @param node 插入節(jié)點(diǎn)
*/
public void insert(BinaryTree<Integer> T, TreeNode<Integer> node){
TreeNode<Integer> y = null; //存儲(chǔ)插入節(jié)點(diǎn)的父節(jié)點(diǎn)
TreeNode<Integer> x = T.root;//表示當(dāng)前節(jié)點(diǎn)
while(x != null){
y = x; //記錄當(dāng)時(shí)的父節(jié)點(diǎn)
if(node.key < x.key ){
x = x.left;
}else{
x = x.right;
}
}
node.parent = y; //插入的節(jié)點(diǎn)的父節(jié)點(diǎn)指向父節(jié)點(diǎn)
//1.根節(jié)點(diǎn)為null的情況
if(y == null){
T.root = node;
} else if( node.key < y.key){ //2.找到插入節(jié)點(diǎn)的位置的父節(jié)點(diǎn)，插入父節(jié)點(diǎn)的左邊
y.left= node;
} else{ //3.找到插入節(jié)點(diǎn)的位置的父節(jié)點(diǎn)览爵，插入父節(jié)點(diǎn)的右邊
y.right = node;
}
}
(2)刪除
從二叉查找樹中刪除給定的結(jié)點(diǎn)z蜓竹，分三種情況討論：
-
結(jié)點(diǎn)z沒有左右子樹俱济，則修改其父節(jié)點(diǎn)p[z]蛛碌，使其為NULL左医。刪除過程如下圖所示：
樹刪除情況1.png -
如果
結(jié)點(diǎn)z只有一個(gè)子樹（左子樹或者右子樹）跛十，通過在其子結(jié)點(diǎn)與父節(jié)點(diǎn)建立一條鏈來刪除z芥映。刪除過程如下圖所示：
樹刪除情況2.png -
如果
z有兩個(gè)子女奈偏，需要找到后繼節(jié)點(diǎn)惊来，然后后繼節(jié)點(diǎn)來替換刪除節(jié)點(diǎn)裁蚁，但是后繼節(jié)點(diǎn)的位置有兩種情況
(1)后繼節(jié)點(diǎn)是刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)
樹刪除情況3-1.png
(2)后繼節(jié)點(diǎn)是刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)的最小的左子節(jié)點(diǎn)
樹刪除情況3-2.png
代碼如下：
/**
* 刪除指定節(jié)點(diǎn)
* 有三種情況
* 1.刪除節(jié)點(diǎn)沒有子節(jié)點(diǎn)
* 2.刪除節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)
* 3.刪除節(jié)點(diǎn)有兩個(gè)節(jié)點(diǎn)（1.刪除的節(jié)點(diǎn)的后繼節(jié)點(diǎn)就是該節(jié)點(diǎn)的右節(jié)點(diǎn) 2.刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)是該節(jié)點(diǎn)的右子樹的最大節(jié)點(diǎn) ）
* @param T
* @param node
*/
public void delete(BinaryTree<Integer> T, TreeNode<Integer> node){
//1.刪除節(jié)點(diǎn)的左子節(jié)點(diǎn)為null
if( node.left == null){
transplant(T,node,node.right);
}else if( node.right == null){ //2.刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)為null
transplant(T,node,node.left);
}else{
TreeNode<Integer> successor = successor(node);
if( successor.parent != node){ //4.刪除節(jié)點(diǎn)的有2個(gè)子節(jié)點(diǎn)移必，但左子樹的后繼節(jié)點(diǎn)不為該刪除節(jié)點(diǎn)的左子節(jié)點(diǎn)
transplant(T,successor,successor.right);//交換后繼節(jié)點(diǎn)和后繼節(jié)點(diǎn)的左子節(jié)點(diǎn)崔泵，讓后繼節(jié)點(diǎn)和父節(jié)點(diǎn)相互指向后繼節(jié)點(diǎn)的左子節(jié)點(diǎn)
//后繼節(jié)點(diǎn)相互指向刪除節(jié)點(diǎn)的右節(jié)點(diǎn)
successor.right = node.right;
successor.right.parent = successor;
}
//3刪除節(jié)點(diǎn)的有2個(gè)子節(jié)點(diǎn)憎瘸，但左子節(jié)點(diǎn)的數(shù)據(jù)為后繼節(jié)點(diǎn)
//交換后繼節(jié)點(diǎn)與刪除節(jié)點(diǎn)
transplant(T,successor,node);
//讓后繼節(jié)點(diǎn)與刪除節(jié)點(diǎn)的左子節(jié)點(diǎn)相互引用
successor.left=node.left;
successor.left.parent = successor;
}
}
/**
* 替換節(jié)點(diǎn)
* 有三種情況
* 1.該原始節(jié)點(diǎn)為父節(jié)點(diǎn)為null,即為根節(jié)點(diǎn)
* 2.該原始節(jié)點(diǎn)是父節(jié)點(diǎn)的左節(jié)點(diǎn)
* 3.該原始節(jié)點(diǎn)是父節(jié)點(diǎn)的右節(jié)點(diǎn)
*
* @param T
* @param orginalNode
* @param replaceNode
*/
private void transplant(BinaryTree<Integer> T,TreeNode<Integer> orginalNode ,TreeNode<Integer> replaceNode){
//1.該原始節(jié)點(diǎn)為父節(jié)點(diǎn)為null,即為根節(jié)點(diǎn)
if(orginalNode !=null && orginalNode.parent ==null){
T.root = replaceNode;
// 2.該原始節(jié)點(diǎn)是父節(jié)點(diǎn)的左節(jié)點(diǎn)
}else if( orginalNode.parent.left == orginalNode){
orginalNode.parent.left = replaceNode;
// 3.該原始節(jié)點(diǎn)是父節(jié)點(diǎn)的右節(jié)點(diǎn)
}else if( orginalNode.parent.right == orginalNode){
orginalNode.parent.right = replaceNode;
}
if(replaceNode != null){
replaceNode.parent = orginalNode.parent;
}
}
6崎弃、完整的二叉樹的代碼
- 樹節(jié)點(diǎn)TreeNode
/**
* @Project: 10.dataStructure
* @description: 樹的節(jié)點(diǎn)
* @author: sunkang
* @create: 2018-08-19 15:08
* @ModificationHistory who when What
**/
public class TreeNode<E> {
//存儲(chǔ)的值
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+",");
}
}
/**
* 查找特定值的節(jié)點(diǎn)
* @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;
}
/**
* 通過遞歸的形式查找特定值的節(jié)點(diǎn)
* @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);
}
}
/**
* 查找樹的最大節(jié)點(diǎn)
* @param node
* @return
*/
public TreeNode<E> maximum(TreeNode<E> node){
while(node!= null && node.right!=null){
node = node.right;
}
return node;
}
/**
* 查找樹的最小節(jié)點(diǎn)
* @param node
* @return
*/
public TreeNode<Integer> minmum(TreeNode<Integer> node){
while( node!= null && node.left !=null){
node= node.left;
}
return node;
}
/**
* 查找指定節(jié)點(diǎn)的后繼節(jié)點(diǎn)
*
* @return
*/
public TreeNode<Integer> successor(TreeNode<Integer> node ){
// 1.指定節(jié)點(diǎn)的右子樹的最小節(jié)點(diǎn)
if( node != null && node.right != null){
return minmum(node.right);
}
//2. 右節(jié)點(diǎn)不存在時(shí)，往上面查找符合一個(gè)節(jié)點(diǎn)y塞弊，該節(jié)點(diǎn)的左子樹的最大值為該查找節(jié)點(diǎn)node游沿，該y.key>node.key
TreeNode<Integer> p = node.parent;
while ( p != null && p.right == node){
node = p;
p=p.parent;
}
return p;
}
/**
* 查找指定節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
* @param node
* @return
*/
public TreeNode<E> preSuccessor(TreeNode<E> node){
//1.指定節(jié)點(diǎn)的左子樹的最大節(jié)點(diǎn)
if(node != null && node.left!= null){
return maximum(node.left);
}
//2.左節(jié)點(diǎn)不存在時(shí)诀黍，往上面查找符合一個(gè)節(jié)點(diǎn)y眯勾，該節(jié)點(diǎn)的右子樹的最小值為該查找節(jié)點(diǎn),該y.key >node.key
TreeNode<E> p = node.parent;
if( p !=null && p.left == node){
node = p;
p = p.parent;
}
return p;
}
/**
* 插入節(jié)點(diǎn)
* 1.根節(jié)點(diǎn)為null的情況
* 2.找到插入節(jié)點(diǎn)的位置的父節(jié)點(diǎn)吃环，插入父節(jié)點(diǎn)的左邊
* 3.找到插入節(jié)點(diǎn)的位置的父節(jié)點(diǎn)郁轻，插入父節(jié)點(diǎn)的右邊
* @param T 樹
* @param node 插入節(jié)點(diǎn)
*/
public void insert(BinaryTree<Integer> T, TreeNode<Integer> node){
TreeNode<Integer> y = null; //存儲(chǔ)插入節(jié)點(diǎn)的父節(jié)點(diǎn)
TreeNode<Integer> x = T.root;//表示當(dāng)前節(jié)點(diǎn)
while(x != null){
y = x; //記錄當(dāng)時(shí)的父節(jié)點(diǎn)
if(node.key < x.key ){
x = x.left;
}else{
x = x.right;
}
}
node.parent = y; //插入的節(jié)點(diǎn)的父節(jié)點(diǎn)指向父節(jié)點(diǎn)
//1.根節(jié)點(diǎn)為null的情況
if(y == null){
T.root = node;
} else if( node.key < y.key){ //2.找到插入節(jié)點(diǎn)的位置的父節(jié)點(diǎn)好唯，插入父節(jié)點(diǎn)的左邊
y.left= node;
} else{ //3.找到插入節(jié)點(diǎn)的位置的父節(jié)點(diǎn)渠啊，插入父節(jié)點(diǎn)的右邊
y.right = node;
}
}
/**
* 刪除指定節(jié)點(diǎn)
* 有三種情況
* 1.刪除節(jié)點(diǎn)沒有子節(jié)點(diǎn)
* 2.刪除節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)
* 3.刪除節(jié)點(diǎn)有兩個(gè)節(jié)點(diǎn)（1.刪除的節(jié)點(diǎn)的后繼節(jié)點(diǎn)就是該節(jié)點(diǎn)的右節(jié)點(diǎn) 2.刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)是該節(jié)點(diǎn)的右子樹的最大節(jié)點(diǎn) ）
* @param T
* @param node
*/
public void delete(BinaryTree<Integer> T, TreeNode<Integer> node){
//1.刪除節(jié)點(diǎn)的左子節(jié)點(diǎn)為null
if( node.left == null){
transplant(T,node,node.right);
}else if( node.right == null){ //2.刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)為null
transplant(T,node,node.left);
}else{
TreeNode<Integer> successor = successor(node);
if( successor.parent != node){ //4.刪除節(jié)點(diǎn)的有2個(gè)子節(jié)點(diǎn)，但左子樹的后繼節(jié)點(diǎn)不為該刪除節(jié)點(diǎn)的左子節(jié)點(diǎn)
transplant(T,successor,successor.right);//交換后繼節(jié)點(diǎn)和后繼節(jié)點(diǎn)的左子節(jié)點(diǎn)拄氯，讓后繼節(jié)點(diǎn)和父節(jié)點(diǎn)相互指向后繼節(jié)點(diǎn)的左子節(jié)點(diǎn)
//后繼節(jié)點(diǎn)相互指向刪除節(jié)點(diǎn)的右節(jié)點(diǎn)
successor.right = node.right;
successor.right.parent = successor;
}
//3刪除節(jié)點(diǎn)的有2個(gè)子節(jié)點(diǎn)译柏，但左子節(jié)點(diǎn)的數(shù)據(jù)為后繼節(jié)點(diǎn)
//交換后繼節(jié)點(diǎn)與刪除節(jié)點(diǎn)
transplant(T,successor,node);
//讓后繼節(jié)點(diǎn)與刪除節(jié)點(diǎn)的左子節(jié)點(diǎn)相互引用
successor.left=node.left;
successor.left.parent = successor;
}
}
/**
* 替換節(jié)點(diǎn)
* 有三種情況
* 1.該原始節(jié)點(diǎn)為父節(jié)點(diǎn)為null,即為根節(jié)點(diǎn)
* 2.該原始節(jié)點(diǎn)是父節(jié)點(diǎn)的左節(jié)點(diǎn)
* 3.該原始節(jié)點(diǎn)是父節(jié)點(diǎn)的右節(jié)點(diǎn)
*
* @param T
* @param orginalNode
* @param replaceNode
*/
private void transplant(BinaryTree<Integer> T,TreeNode<Integer> orginalNode ,TreeNode<Integer> replaceNode){
//1.該原始節(jié)點(diǎn)為父節(jié)點(diǎn)為null,即為根節(jié)點(diǎn)
if(orginalNode !=null && orginalNode.parent ==null){
T.root = replaceNode;
// 2.該原始節(jié)點(diǎn)是父節(jié)點(diǎn)的左節(jié)點(diǎn)
}else if( orginalNode.parent.left == orginalNode){
orginalNode.parent.left = replaceNode;
// 3.該原始節(jié)點(diǎn)是父節(jié)點(diǎn)的右節(jié)點(diǎn)
}else if( orginalNode.parent.right == orginalNode){
orginalNode.parent.right = replaceNode;
}
if(replaceNode != null){
replaceNode.parent = orginalNode.parent;
}
}
/***************************
* 構(gòu)造下面的樹
* 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("后繼節(jié)點(diǎn)：");
System.out.println(binaryTree.successor(binaryTree.root).key);
System.out.print("前序節(jié)點(diǎn)：");
System.out.println(binaryTree.preSuccessor(binaryTree.root).key);
System.out.print("跟節(jié)點(diǎn)的后繼節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn):");
System.out.println(binaryTree.preSuccessor(binaryTree.successor(binaryTree.root)).key);
System.out.print("跟節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的后繼節(jié)點(diǎn):");
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
