二叉樹的基本定義
簡而言之：二叉樹就是度不能超過2的樹（每個樹只能有兩個節點）
滿二叉樹：
一個二叉樹，如果每一個層的結點樹達到最大值，則在這個樹就是滿二叉樹
完全二叉樹：
葉結點只能出現在最下層和次下層，并且最下面那一層的結點都集中在該層最左邊的若干位置的二叉樹
二叉查找樹
二叉查找樹是一種特殊的二叉樹，相對較小的值保存在左結點中，較大的值保存在右結點中，
根據對圖的觀察，我們發現二叉樹其實就是由一個一個的結點及其之間的關系組成的，按照面向物件的思想，我們設計一個結點來描述結點這個事務，
首先我們先想著實作二叉樹需要一些什么引數？
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四個引數，并且定義了這個類的構造方法
我們看插入方法put思想：
- 如果當樹中沒有任何一個結點，則直接把新結點當根結點使用
- 如果當前樹不為空，就從根結點開始
2-1：如果要查詢的key，小于當前結點的key，則繼續查找當前結點的左子結點
2-2：如果新結點的key大于當前結點的key，則繼續找當前結點的右子結點
2-3：如果新結點的key等于當前結點的key，則樹中已經存在這樣的結點，替換該結點的value值就好
那么我們要怎么實作呢？
//向樹中插入一個鍵值對
public void put(Integer key,String value){
root=put(root,key,value);
}
//給指定的數x添加一個鍵,添加一個鍵值對，并回傳添加后的新數
private Node put(Node tree,Integer key,String value){
if(tree==null){
//個數加1
n++;
//直接把新結點當成根結點使用
return new Node(null,null,key,value);
}
//比較key,如果新結點大于當前結點的key，繼續尋找當前結點的右子結點
if(key > tree.key){
tree.right=put(tree.right,key,value);
}else if(key<tree.key){
//新結點的key小于當前結點的key,繼續找當前結點的左子結點
tree.left=put(tree.left,key,value);
}else{
//新結點的key等于當前結點的key
tree.value=value;
}
return tree;
}
在上面的代碼塊中，我們定義了兩個put方法，一個是給其他類操作的，一個是給自己類操作的，對于外部的用戶來說，他只需要將鍵值對傳遞進來就好了，排序是我們程式員的事，所以，我們這里的put只有兩個引數：
public void put(Integer key,String value)
然后我們通過這個put方法再去呼叫我們內部的put方法，在這個方法中，我們首先要把我們的根結點root傳遞進去，然后再將前端傳給我們的key：value傳遞進去
private Node put(Node tree,Integer key,String value)
這樣，我們就可以在這個put上進行我們一開始定義的開發流程了：
- 如果樹中沒有結點，就把當前插入的結點當成首節點使用：
if(tree==null){
//個數加1
n++;
//直接把新結點當成根結點使用
return new Node(null,null,key,value);
}
- 如果樹不為空，就從根結點開始遍歷，也就是root結點
2-1. 如果要查詢的key，小于當前結點的key，則繼續查找當前結點的左子結點
//比較key,如果新結點大于當前結點的key，繼續尋找當前結點的右子結點
if(key > tree.key){
tree.right=put(tree.right,key,value);
}
2-2. 如果新結點的key大于當前結點的key，則繼續找當前結點的右子結點
else if(key<tree.key){
//新結點的key小于當前結點的key,繼續找當前結點的左子結點
tree.left=put(tree.left,key,value);
}
2-3：如果新結點的key等于當前結點的key，則樹中已經存在這樣的結點，替換該結點的value值就好
else{
//新結點的key等于當前結點的key
tree.value=value;
}
現在put方法就執行完畢了，我們把一個前端傳遞過來的值放入了二叉樹中.
上面我們已經實作了二叉樹中的put方法，按照我的習慣的話呢接下來我們還是先講思想，講get方法和delete方法：
查詢方法get實作思想：
從根結點開始：
- 如果要查詢的key小于當前結點的key，則繼續查找當前結點的左子結點
- 如果要查詢的key大于當前結點的key，則繼續找當前結點的右子結點
- 如果要查詢的key等于當前結點的key，則樹中回傳當前結點的value
洗掉方法delete實作思想：
- 找到被洗掉結點
- 找到被洗掉結點右子樹的最小結點
- 洗掉右子樹中的最小結點
- 讓被洗掉結點的左子樹稱為最小結點的左子樹，讓被洗掉結點的右子樹稱為最小結點的子樹
- 讓被洗掉節點的父結點指向最小結點
按照從簡單到困難的準則，我們先從簡單的開始，get方法相對于delete而言要簡單一點，所以我們先實作get方法
//從樹中找到對應的值
public String get(Integer key){
return get(root,key);
}
private String get(Node tree,Integer key){
if(root==null){
return null;
}
//比較key,如果新結點大于當前結點的key，繼續尋找當前結點的右子結點
if(key > tree.key){
return get(tree.right,key);
}else if(key<tree.key){
//比較key,如果新結點大于當前結點的key，繼續尋找當前結點的左子結點
return get(tree.left,key);
}else{
//要查找的key和當前結點的key相等，回傳value
return tree.value;
}
}
通過不停的遞回呼叫get方法，我們就可以不斷的查找樹的左右結點，從而最侄訓傳get到的結果值，這個非常簡單，沒什么好說的，
接下來比較重要的是delete方法：
//從指定的樹中，根據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;
}
}
//到這里，最小結點已經被洗掉了
//讓被洗掉結點的左子樹成為最小結點的左子樹，讓被洗掉結點的右子樹，成為最小結點的右子樹
minNode.left=tree.left;
minNode.right=tree.right;
//讓被洗掉結點的父結點指向最小結點
tree=minNode;
//個數減1
n--;
}
return tree;
}
上面的這段代碼看著很長，且聽我與你一一分解
首先我們通過public方法方便別的類呼叫，用戶只需要傳遞key值進入我們的后臺，我們就可以通過后臺的查找方法來查找二叉樹中的元素，然后對其進行洗掉，
這同樣使用了遞回的思想，通過不斷的查找二叉樹中的元素，找到要洗掉的那個資料，
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;
}
}
//到這里，最小結點已經被洗掉了
//讓被洗掉結點的左子樹成為最小結點的左子樹，讓被洗掉結點的右子樹，成為最小結點的右子樹
minNode.left=tree.left;
minNode.right=tree.right;
//讓被洗掉結點的父結點指向最小結點
tree=minNode;
//個數減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;
}
}
//到這里，最小結點已經被洗掉了
//讓被洗掉結點的左子樹成為最小結點的左子樹，讓被洗掉結點的右子樹，成為最小結點的右子樹
minNode.left=tree.left;
minNode.right=tree.right;
//讓被洗掉結點的父結點指向最小結點
tree=minNode;
//個數減1
n--;
}
return tree;
}
現在又要研究二叉樹中的洗掉方法中結點的性質了，我們既然要把這個元素進行洗掉操作的話，那么是不是，我們就要將他的子結點的層級往上提升一級，那么我們接著研究：
//待洗掉的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;
}
}
//到這里，最小結點已經被洗掉了
//讓被洗掉結點的左子樹成為最小結點的左子樹，讓被洗掉結點的右子樹，成為最小結點的右子樹
minNode.left=tree.left;
minNode.right=tree.right;
//讓被洗掉結點的父結點指向最小結點
tree=minNode;
//個數減1
n--;
}
最后在我們所有操作都已經執行完畢之后，我們只要回傳這個改變之后的tree就好了
好了，現在我們創建一個外部類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;
//記錄樹中的元素個數
private int n;
public BinaryTree() {
}
//向樹中插入一個鍵值對
public void put(Integer key,String value){
root=put(root,key,value);
}
//給指定的數x添加一個鍵,添加一個鍵值對，并回傳添加后的新數
private Node put(Node tree,Integer key,String value){
if(tree==null){
//個數加1
n++;
//直接把新結點當成根結點使用
return new Node(null,null,key,value);
}
//比較key,如果新結點大于當前結點的key，繼續尋找當前結點的右子結點
if(key > tree.key){
tree.right=put(tree.right,key,value);
}else if(key<tree.key){
//新結點的key小于當前結點的key,繼續找當前結點的左子結點
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，繼續尋找當前結點的右子結點
if(key > tree.key){
return get(tree.right,key);
}else if(key<tree.key){
//比較key,如果新結點大于當前結點的key，繼續尋找當前結點的左子結點
return get(tree.left,key);
}else{
//要查找的key和當前結點的key相等，回傳value
return tree.value;
}
}
//從指定的樹中，根據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;
}
}
//到這里，最小結點已經被洗掉了
//讓被洗掉結點的左子樹成為最小結點的左子樹，讓被洗掉結點的右子樹，成為最小結點的右子樹
minNode.left=tree.left;
minNode.right=tree.right;
//讓被洗掉結點的父結點指向最小結點
tree=minNode;
//個數減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());
}
}
感謝觀看！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/226831.html
標籤：java