二叉樹的基本定義
簡而言之：二叉樹就是度不能超過2的樹（每個樹只能有兩個節(jié)點）
滿二叉樹：
一個二叉樹，如果每一個層的結點樹達到最大值，則在這個樹就是滿二叉樹
完全二叉樹：
葉結點只能出現(xiàn)在最下層和次下層，并且最下面那一層的結點都集中在該層最左邊的若干位置的二叉樹
二叉查找樹：
二叉查找樹是一種特殊的二叉樹，相對較小的值保存在左結點中，較大的值保存在右結點中。
根據(jù)對圖的觀察，我們發(fā)現(xiàn)二叉樹其實就是由一個一個的結點及其之間的關系組成的，按照面向?qū)ο蟮乃枷耄覀冊O計一個結點來描述結點這個事務。
首先我們先想著實現(xiàn)二叉樹需要一些什么參數(shù)？
private static class Node{
public Node left;
public Node right;
public Integer key;
public String value;
public Node(Node left, Node right, Integer key, String value) {
this.left = left;
this.right = right;
this.key = key;
this.value = value;
}
}
在上面我們定義了left，right，key，value四個參數(shù)，并且定義了這個類的構造方法
我們看插入方法put思想：
- 如果當樹中沒有任何一個結點，則直接把新結點當根結點使用
- 如果當前樹不為空，就從根結點開始
2-1：如果要查詢的key，小于當前結點的key，則繼續(xù)查找當前結點的左子結點2-2：如果新結點的key大于當前結點的key，則繼續(xù)找當前結點的右子結點2-3：如果新結點的key等于當前結點的key，則樹中已經(jīng)存在這樣的結點，替換該結點的value值就好
那么我們要怎么實現(xiàn)呢？
//向樹中插入一個鍵值對
public void put(Integer key,String value){
root=put(root,key,value);
}
//給指定的數(shù)x添加一個鍵,添加一個鍵值對，并返回添加后的新數(shù)
private Node put(Node tree,Integer key,String value){
if(tree==null){
//個數(shù)加1
n++;
//直接把新結點當成根結點使用
return new Node(null,null,key,value);
}
//比較key,如果新結點大于當前結點的key，繼續(xù)尋找當前結點的右子結點
if(key > tree.key){
tree.right=put(tree.right,key,value);
}else if(key<tree.key){
//新結點的key小于當前結點的key,繼續(xù)找當前結點的左子結點
tree.left=put(tree.left,key,value);
}else{
//新結點的key等于當前結點的key
tree.value=value;
}
return tree;
}
在上面的代碼塊中，我們定義了兩個put方法，一個是給其他類操作的，一個是給自己類操作的，對于外部的用戶來說，他只需要將鍵值對傳遞進來就好了，排序是我們程序員的事，所以，我們這里的put只有兩個參數(shù)：
public void put(Integer key,String value)
然后我們通過這個put方法再去調(diào)用我們內(nèi)部的put方法，在這個方法中，我們首先要把我們的根結點root傳遞進去，然后再將前端傳給我們的key：value傳遞進去
private Node put(Node tree,Integer key,String value)
這樣，我們就可以在這個put上進行我們一開始定義的開發(fā)流程了：
- 如果樹中沒有結點，就把當前插入的結點當成首節(jié)點使用：
if(tree==null){
//個數(shù)加1
n++;
//直接把新結點當成根結點使用
return new Node(null,null,key,value);
}
- 如果樹不為空，就從根結點開始遍歷，也就是root結點
2-1. 如果要查詢的key，小于當前結點的key，則繼續(xù)查找當前結點的左子結點
//比較key,如果新結點大于當前結點的key，繼續(xù)尋找當前結點的右子結點
if(key > tree.key){
tree.right=put(tree.right,key,value);
}
2-2. 如果新結點的key大于當前結點的key，則繼續(xù)找當前結點的右子結點
else if(key<tree.key){
//新結點的key小于當前結點的key,繼續(xù)找當前結點的左子結點
tree.left=put(tree.left,key,value);
}
2-3：如果新結點的key等于當前結點的key，則樹中已經(jīng)存在這樣的結點，替換該結點的value值就好
else{
//新結點的key等于當前結點的key
tree.value=value;
}
現(xiàn)在put方法就執(zhí)行完畢了，我們把一個前端傳遞過來的值放入了二叉樹中.
上面我們已經(jīng)實現(xiàn)了二叉樹中的put方法，按照我的習慣的話呢接下來我們還是先講思想，講get方法和delete方法：
查詢方法get實現(xiàn)思想：
從根結點開始：
- 如果要查詢的key小于當前結點的key，則繼續(xù)查找當前結點的左子結點
- 如果要查詢的key大于當前結點的key，則繼續(xù)找當前結點的右子結點
- 如果要查詢的key等于當前結點的key，則樹中返回當前結點的value
刪除方法delete實現(xiàn)思想：
- 找到被刪除結點
- 找到被刪除結點右子樹的最小結點
- 刪除右子樹中的最小結點
- 讓被刪除結點的左子樹稱為最小結點的左子樹，讓被刪除結點的右子樹稱為最小結點的子樹
- 讓被刪除節(jié)點的父結點指向最小結點
按照從簡單到困難的準則，我們先從簡單的開始，get方法相對于delete而言要簡單一點，所以我們先實現(xiàn)get方法
//從樹中找到對應的值
public String get(Integer key){
return get(root,key);
}
private String get(Node tree,Integer key){
if(root==null){
return null;
}
//比較key,如果新結點大于當前結點的key，繼續(xù)尋找當前結點的右子結點
if(key > tree.key){
return get(tree.right,key);
}else if(key<tree.key){
//比較key,如果新結點大于當前結點的key，繼續(xù)尋找當前結點的左子結點
return get(tree.left,key);
}else{
//要查找的key和當前結點的key相等，返回value
return tree.value;
}
}
通過不停的遞歸調(diào)用get方法，我們就可以不斷的查找樹的左右結點，從而最終返回get到的結果值，這個非常簡單，沒什么好說的。
接下來比較重要的是delete方法：
//從指定的樹中，根據(jù)key刪除鍵中的鍵值對
public void delete(Integer key){
root=delete(root,key);
}
private Node delete(Node tree,Integer key){
if(tree==null){
return null;
}
if(key > tree.key){
tree.right=delete(tree.right,key);
}else if(key<tree.key){
tree.left=delete(tree.left,key);
}else{
//待刪除的key等于當前結點的key，說明當前結點就是要刪除的結點
//1、如果當前結點的右子樹不存在，則直接返回當前結點的左子結點
if(tree.right==null){
n--;
return tree.left;
}
//2、如果當前結點的左子樹不存在，則直接返回當前結點的右子結點
if(tree.left==null){
n--;
return tree.right;
}
//當前結點的左右子樹都存在
//找到右子樹中的最小結點
Node minNode=tree.right;
//二叉查找樹的左結點一定比右結點小
if(minNode.left!=null){
minNode=minNode.left;
}
//到這里就找到了當前結點右子樹中最小的結點minNode
//刪除右子樹中最小的結點
Node node=tree.right;
while (node.left!=null){
if(node.left.left==null){
//說明N的左結點就是我們要找的最小結點
node.left=null;
}else{
node=node.left;
}
}
//到這里，最小結點已經(jīng)被刪除了
//讓被刪除結點的左子樹成為最小結點的左子樹，讓被刪除結點的右子樹，成為最小結點的右子樹
minNode.left=tree.left;
minNode.right=tree.right;
//讓被刪除結點的父結點指向最小結點
tree=minNode;
//個數(shù)減1
n--;
}
return tree;
}
上面的這段代碼看著很長，且聽我與你一一分解
首先我們通過public方法方便別的類調(diào)用，用戶只需要傳遞key值進入我們的后臺，我們就可以通過后臺的查找方法來查找二叉樹中的元素，然后對其進行刪除。
這同樣使用了遞歸的思想。通過不斷的查找二叉樹中的元素，找到要刪除的那個數(shù)據(jù)。
if(key > tree.key){
tree.right=delete(tree.right,key);
}else if(key<tree.key){
tree.left=delete(tree.left,key);
}else{
//待刪除的key等于當前結點的key，說明當前結點就是要刪除的結點
//1、如果當前結點的右子樹不存在，則直接返回當前結點的左子結點
if(tree.right==null){
n--;
return tree.left;
}
//2、如果當前結點的左子樹不存在，則直接返回當前結點的右子結點
if(tree.left==null){
n--;
return tree.right;
}
//當前結點的左右子樹都存在
//找到右子樹中的最小結點
Node minNode=tree.right;
//二叉查找樹的左結點一定比右結點小
if(minNode.left!=null){
minNode=minNode.left;
}
//到這里就找到了當前結點右子樹中最小的結點minNode
//刪除右子樹中最小的結點
Node node=tree.right;
while (node.left!=null){
if(node.left.left==null){
//說明N的左結點就是我們要找的最小結點
node.left=null;
}else{
node=node.left;
}
}
//到這里，最小結點已經(jīng)被刪除了
//讓被刪除結點的左子樹成為最小結點的左子樹，讓被刪除結點的右子樹，成為最小結點的右子樹
minNode.left=tree.left;
minNode.right=tree.right;
//讓被刪除結點的父結點指向最小結點
tree=minNode;
//個數(shù)減1
n--;
}
如果當前遞歸到的這個結點的元素值小于我們用戶傳遞進來的key的話我們將其往左進行遞歸
if(key > tree.key){
tree.right=delete(tree.right,key);
}
如果大于的話我們就往右進行遞歸
else if(key<tree.key){
tree.left=delete(tree.left,key);
}
如果說用戶傳遞過來的key與當前結點的key值相等的話，那么說明當前的這個結點就是我們要刪除的這個結點
else{
//待刪除的key等于當前結點的key，說明當前結點就是要刪除的結點
//1、如果當前結點的右子樹不存在，則直接返回當前結點的左子結點
if(tree.right==null){
n--;
return tree.left;
}
//2、如果當前結點的左子樹不存在，則直接返回當前結點的右子結點
if(tree.left==null){
n--;
return tree.right;
}
//當前結點的左右子樹都存在
//找到右子樹中的最小結點
Node minNode=tree.right;
//二叉查找樹的左結點一定比右結點小
if(minNode.left!=null){
minNode=minNode.left;
}
//到這里就找到了當前結點右子樹中最小的結點minNode
//刪除右子樹中最小的結點
Node node=tree.right;
while (node.left!=null){
if(node.left.left==null){
//說明N的左結點就是我們要找的最小結點
node.left=null;
}else{
node=node.left;
}
}
//到這里，最小結點已經(jīng)被刪除了
//讓被刪除結點的左子樹成為最小結點的左子樹，讓被刪除結點的右子樹，成為最小結點的右子樹
minNode.left=tree.left;
minNode.right=tree.right;
//讓被刪除結點的父結點指向最小結點
tree=minNode;
//個數(shù)減1
n--;
}
return tree;
}
現(xiàn)在又要研究二叉樹中的刪除方法中結點的性質(zhì)了，我們既然要把這個元素進行刪除操作的話，那么是不是，我們就要將他的子結點的層級往上提升一級，那么我們接著研究：
//待刪除的key等于當前結點的key，說明當前結點就是要刪除的結點
//1、如果當前結點的右子樹不存在，則直接返回當前結點的左子結點
if(tree.right==null){
n--;
return tree.left;
}
//2、如果當前結點的左子樹不存在，則直接返回當前結點的右子結點
if(tree.left==null){
n--;
return tree.right;
}
如果當前結點的右子樹不存在，那么我們就把該結點的左子樹給他提上去
如果當前結點的左子樹不存在，那么我們就把他的右子樹提上去
如果說當前結點的左右子樹都存在的話，那么就有點小麻煩了，那么我們就要從要被刪除的這個結點的右子樹中找到他的最小元素，然后把他的最小元素給他提上去。
//到這里就找到了當前結點右子樹中最小的結點minNode
//刪除右子樹中最小的結點
Node node=tree.right;
while (node.left!=null){
if(node.left.left==null){
//說明N的左結點就是我們要找的最小結點
node.left=null;
}else{
node=node.left;
}
}
//到這里，最小結點已經(jīng)被刪除了
//讓被刪除結點的左子樹成為最小結點的左子樹，讓被刪除結點的右子樹，成為最小結點的右子樹
minNode.left=tree.left;
minNode.right=tree.right;
//讓被刪除結點的父結點指向最小結點
tree=minNode;
//個數(shù)減1
n--;
}
最后在我們所有操作都已經(jīng)執(zhí)行完畢之后，我們只要返回這個改變之后的tree就好了
好了，現(xiàn)在我們創(chuàng)建一個外部類Test1來驗證此程序的正確性
class Test1{
public static void main(String[] args) {
BinaryTree tree=new BinaryTree();
tree.put(8,"雞霸");
tree.put(7,"田七");
tree.put(9,"吳久");
tree.put(3,"張三");
tree.put(6,"陸遠");
System.out.println(tree.get(7));
tree.delete(6);
tree.delete(9);
tree.delete(3);
System.out.println(tree.size());
}
}
然后我放出全部代碼方便大家實驗：
package com.gm.tree;
public class BinaryTree {
//記錄一個根結點
private Node root;
//記錄樹中的元素個數(shù)
private int n;
public BinaryTree() {
}
//向樹中插入一個鍵值對
public void put(Integer key,String value){
root=put(root,key,value);
}
//給指定的數(shù)x添加一個鍵,添加一個鍵值對，并返回添加后的新數(shù)
private Node put(Node tree,Integer key,String value){
if(tree==null){
//個數(shù)加1
n++;
//直接把新結點當成根結點使用
return new Node(null,null,key,value);
}
//比較key,如果新結點大于當前結點的key，繼續(xù)尋找當前結點的右子結點
if(key > tree.key){
tree.right=put(tree.right,key,value);
}else if(key<tree.key){
//新結點的key小于當前結點的key,繼續(xù)找當前結點的左子結點
tree.left=put(tree.left,key,value);
}else{
//新結點的key等于當前結點的key
tree.value=value;
}
return tree;
}
//從樹中找到對應的值
public String get(Integer key){
return get(root,key);
}
private String get(Node tree,Integer key){
if(root==null){
return null;
}
//比較key,如果新結點大于當前結點的key，繼續(xù)尋找當前結點的右子結點
if(key > tree.key){
return get(tree.right,key);
}else if(key<tree.key){
//比較key,如果新結點大于當前結點的key，繼續(xù)尋找當前結點的左子結點
return get(tree.left,key);
}else{
//要查找的key和當前結點的key相等，返回value
return tree.value;
}
}
//從指定的樹中，根據(jù)key刪除鍵中的鍵值對
public void delete(Integer key){
root=delete(root,key);
}
private Node delete(Node tree,Integer key){
if(tree==null){
return null;
}
if(key > tree.key){
tree.right=delete(tree.right,key);
}else if(key<tree.key){
tree.left=delete(tree.left,key);
}else{
//待刪除的key等于當前結點的key，說明當前結點就是要刪除的結點
//1、如果當前結點的右子樹不存在，則直接返回當前結點的左子結點
if(tree.right==null){
n--;
return tree.left;
}
//2、如果當前結點的左子樹不存在，則直接返回當前結點的右子結點
if(tree.left==null){
n--;
return tree.right;
}
//當前結點的左右子樹都存在
//找到右子樹中的最小結點
Node minNode=tree.right;
//二叉查找樹的左結點一定比右結點小
if(minNode.left!=null){
minNode=minNode.left;
}
//到這里就找到了當前結點右子樹中最小的結點minNode
//刪除右子樹中最小的結點
Node node=tree.right;
while (node.left!=null){
if(node.left.left==null){
//說明N的左結點就是我們要找的最小結點
node.left=null;
}else{
node=node.left;
}
}
//到這里，最小結點已經(jīng)被刪除了
//讓被刪除結點的左子樹成為最小結點的左子樹，讓被刪除結點的右子樹，成為最小結點的右子樹
minNode.left=tree.left;
minNode.right=tree.right;
//讓被刪除結點的父結點指向最小結點
tree=minNode;
//個數(shù)減1
n--;
}
return tree;
}
public int size(){
return n;
}
private static class Node{
public Node left;
public Node right;
public Integer key;
public String value;
public Node(Node left, Node right, Integer key, String value) {
this.left = left;
this.right = right;
this.key = key;
this.value = value;
}
}
}
class Test1{
public static void main(String[] args) {
BinaryTree tree=new BinaryTree();
tree.put(8,"雷霸天");
tree.put(7,"田七");
tree.put(9,"吳久");
tree.put(3,"張三");
tree.put(6,"陸遠");
System.out.println(tree.get(7));
tree.delete(6);
tree.delete(9);
tree.delete(3);
System.out.println(tree.size());
}
}
