使用Java實現二叉樹的新增，刪除，獲取以及遍歷

二叉樹節點的宣告：

static final class Entry<T extends Comparable<T>>{
//儲存的資料
private T item;
//左子樹
private Entry<T> left;
//右子樹
private Entry<T> right;
//父節點
private Entry<T> parent;
Entry(T item,Entry<T> parent){
this.item = item;
this.parent = parent;
}
}

類屬性：

 //根節點
private Entry<T> root;
//資料量
private int size = 0;

二叉樹新增資料：

/**
* 新增元素
* @param item 待新增元素
* @return 已新增元素
*/
public T put(T item){
//每次新增資料的時候都是從根節點向下遍歷
Entry<T> t = root;
size++;
if (t == null){
//當前的叉樹樹的為空，將新節點設定為根節點，父節點為null
root = new Entry<>(item,null);
return root.item;
}
//自然排序結果，如果傳入的資料小於當前節點返回-1，大於當前節點返回1，否則返回0
int ret = 0;
//記錄父節點
Entry<T> p = t;
while (t != null){
//與當前節點比較
ret = item.compareTo(t.item);
p = t;
//插入節點比當前節點小，把當前節點設定為左子節點，然後與左子比較，以此類推找到合適的位置
if (ret < 0)
t = t.left;
//大於當前節點
else if (ret > 0)
t = t.right;
else {
//相等就把舊值覆蓋掉
t.item = item;
return t.item;
}
}
//建立新節點
Entry<T> e = new Entry<>(item,p);
//根據比較結果將新節點放入合適的位置
if (ret < 0)
p.left = e;
else
p.right = e;
return e.item;
}

在put的過程中，使用Comparable<T>中的compareTo來比較兩個元素的大小的，所以在二叉樹中儲存的元素必須要繼承Comparable<T> 類，覆寫compareTo方法。

二叉樹刪除資料

/**
* 刪除元素
* 刪除元素如果細分的話，可以分為4中：沒有子節點，只有左節點，只有右節點，有兩個子節點
* 1）沒有子節點這種情況比較簡單，直接刪除就可以了
* 2）只有左節點或右節點，這兩種情況處理方式是一致的，只是方向相反，所以在一起講了，
* 將刪除節點的父節點的左節點（右節點）指向刪除節點的子節點，將左節點（右節點）指向刪除節點的父節點
* 3）有兩個子節點，這種情況相對來說比較複雜一點：
* 找到刪除節點的前驅節點或後繼節點，然後將前驅或後繼節點的值賦給刪除節點，然後將前驅或後繼節點刪除。本質是刪除前驅或後繼節點
* 前驅節點的特點：
* 1）刪除的左子節點沒有右子節點，那麼左子節點即為前驅節點
* 2）刪除節點的左子節點有右子節點，那麼最右邊的最後一個節點即為前驅節點
* 後繼節點的特點：
* 與前驅節點剛好相反，總是右子節點，或則右子節點的最左子節點;例如：刪除節點為c ，那麼前驅節點為 m，後繼節點為n
*a
*/\
*bc
*/ \/\
*defg
*/\/ \/ \/ \
* @param item 刪除元素hijklm no
* @return 刪除結果
*/
public boolean remove(T item){
//獲取刪除節點
Entry<T> delEntry = getEntry(item);
if (delEntry == null) return false;
//刪除節點的父節點
Entry<T> p = delEntry.parent;
size--;
//情況1：沒有子節點
if (delEntry.left == null && delEntry.right == null){
//刪除節點為根節點
if (delEntry == root){
root = null;
}else {//非根節點
//刪除的是父節點的左節點
if (delEntry == p.left){
p.left = null;
}else {//刪除右節點
p.right = null;
}
}
//情況2：刪除的節點只有左節點
}else if (delEntry.right == null){
Entry<T> lc = delEntry.left;
//刪除的節點為根節點，將刪除節點的左節點設定成根節點
if (p == null) {
lc.parent = null;
root = lc;
} else {//非根節點
if (delEntry == p.left){//刪除左節點
p.left = lc;
}else {//刪除右節點
p.right = lc;
}
lc.parent = p;
}
//情況3：刪除節點只有右節點
}else if (delEntry.left == null){
Entry<T> rc = delEntry.right;
//刪除根節點
if (p == null) {
rc.parent = null;
root = rc;
}else {//刪除非根節點
if (delEntry == p.left)
p.left = rc;
else
p.right = rc;
rc.parent = p;
}
//情況4：刪除節點有兩個子節點
}else {//有兩個節點,找到後繼節點，將值賦給刪除節點，然後將後繼節點刪除掉即可
Entry<T> successor = successor(delEntry);//獲取到後繼節點
delEntry.item = successor.item;
//後繼節點為右子節點
if (delEntry.right == successor){
//右子節點有右子節點
if (successor.right != null) {
delEntry.right = successor.right;
successor.right.parent = delEntry;
}else {//右子節點沒有子節點
delEntry.right = null;
}
}else {//後繼節點必定是左節點
successor.parent.left = null;
}
return true;
}
//讓gc回收
delEntry.parent = null;
delEntry.left = null;
delEntry.right = null;
return true;
}

/**
* 獲取節點節點
* @param item 獲取節點
* @return 獲取到的節點，可能為null
*/
private Entry<T> getEntry(T item){
Entry<T> t = root;
int ret;
//從根節點開始遍歷
for (;t != null;){
ret = item.compareTo(t.item);
if (ret < 0)
t = t.left;
else if (ret > 0)
t = t.right;
else
return t;
}
return null;
}


/**
* 查詢後繼節點
* @param delEntry 刪除節點
* @return 後繼節點
*/
private Entry<T> successor(Entry<T> delEntry) {
Entry<T> r = delEntry.right;//r節點必定不為空
while (r.left != null){
r = r.left;
}
return r;
}

二叉樹獲取節點

/**
* 判斷是否存在該元素
* @param item 查詢元素
* @return 結果
*/
public boolean contains(T item){
return getEntry(item) != null;
}



/**
* 獲取節點節點
* @param item 獲取節點
* @return 獲取到的節點，可能為null
*/
private Entry<T> getEntry(T item){
Entry<T> t = root;
int ret;
//從根節點開始遍歷
for (;t != null;){
ret = item.compareTo(t.item);
if (ret < 0)
t = t.left;
else if (ret > 0)
t = t.right;
else
return t;
}
return null;
}

因為我這個例子是儲存一個元素，獲取到的元素和傳進去的元素是一致的，所以我用contains方法來判斷返回true即表示獲取成功了，不返回獲取到的結果了。當然，如果將entry儲存的元素改為kv形式的話，就可以使用get方法了。

二叉樹的遍歷

二叉樹的遍歷可以分為三種：前序遍歷、中序遍歷和後續遍歷，其中中序遍歷是最常用的遍歷方式，因為它遍歷出來的結果的升序的。

前序遍歷：

/**
* 前序遍歷
* @param e 開始遍歷元素
*/
public void prevIterator(Entry<T> e){
if (e != null) {
System.out.print(e.item + " ");
prevIterator(e.left);
prevIterator(e.right);
}
}

中序遍歷：

/**
* 中序遍歷
* @param e
*/
public void midIterator(Entry<T> e){
if (e != null){
midIterator(e.left);
System.out.print(e.item + " ");
midIterator(e.right);
}
}

後序遍歷：

/**
* 後續遍歷
* @param e 開始遍歷元素
*/
public void subIterator(Entry<T> e){
if (e != null) {
subIterator(e.left);
subIterator(e.right);
System.out.print(e.item + " ");
}
}

demo完整的程式碼：也可以到我的github中下載程式碼： ofollow,noindex">https://github.com/rainple1860/MyCollection

package com.rainple.collections;

/**
 * 二叉樹
 * @param <T>
 */
public class BinaryTree<T extends Comparable<T>> {

//根節點
private Entry<T> root;
//資料量
private int size = 0;

public BinaryTree(){}

/**
* 新增元素
* @param item 待新增元素
* @return 已新增元素
*/
public T put(T item){
//每次新增資料的時候都是從根節點向下遍歷
Entry<T> t = root;
size++;
if (t == null){
//當前的叉樹樹的為空，將新節點設定為根節點，父節點為null
root = new Entry<>(item,null);
return root.item;
}
//自然排序結果，如果傳入的資料小於當前節點返回-1，大於當前節點返回1，否則返回0
int ret = 0;
//記錄父節點
Entry<T> p = t;
while (t != null){
//與當前節點比較
ret = item.compareTo(t.item);
p = t;
//插入節點比當前節點小，把當前節點設定為左子節點，然後與左子比較，以此類推找到合適的位置
if (ret < 0)
t = t.left;
//大於當前節點
else if (ret > 0)
t = t.right;
else {
//相等就把舊值覆蓋掉
t.item = item;
return t.item;
}
}
//建立新節點
Entry<T> e = new Entry<>(item,p);
//根據比較結果將新節點放入合適的位置
if (ret < 0)
p.left = e;
else
p.right = e;
return e.item;
}

public void print(){
midIterator(root);
}

/**
* 中序遍歷
* @param e
*/
public void midIterator(Entry<T> e){
if (e != null){
midIterator(e.left);
System.out.print(e.item + " ");
midIterator(e.right);
}
}

/**
* 獲取根節點
* @return 根節點
*/
public Entry<T> getRoot(){return root;}

/**
* 前序遍歷
* @param e 開始遍歷元素
*/
public void prevIterator(Entry<T> e){
if (e != null) {
System.out.print(e.item + " ");
prevIterator(e.left);
prevIterator(e.right);
}
}

/**
* 後續遍歷
* @param e 開始遍歷元素
*/
public void subIterator(Entry<T> e){
if (e != null) {
subIterator(e.left);
subIterator(e.right);
System.out.print(e.item + " ");
}
}

/**
* 獲取節點節點
* @param item 獲取節點
* @return 獲取到的節點，可能為null
*/
private Entry<T> getEntry(T item){
Entry<T> t = root;
int ret;
//從根節點開始遍歷
for (;t != null;){
ret = item.compareTo(t.item);
if (ret < 0)
t = t.left;
else if (ret > 0)
t = t.right;
else
return t;
}
return null;
}

/**
* 判斷是否存在該元素
* @param item 查詢元素
* @return 結果
*/
public boolean contains(T item){
return getEntry(item) != null;
}

/**
* 刪除元素
* 刪除元素如果細分的話，可以分為4中：沒有子節點，只有左節點，只有右節點，有兩個子節點
* 1）沒有子節點這種情況比較簡單，直接刪除就可以了
* 2）只有左節點或右節點，這兩種情況處理方式是一致的，只是方向相反，所以在一起講了，
* 將刪除節點的父節點的左節點（右節點）指向刪除節點的子節點，將左節點（右節點）指向刪除節點的父節點
* 3）有兩個子節點，這種情況相對來說比較複雜一點：
* 找到刪除節點的前驅節點或後繼節點，然後將前驅或後繼節點的值賦給刪除節點，然後將前驅或後繼節點刪除。本質是刪除前驅或後繼節點
* 前驅節點的特點：
* 1）刪除的左子節點沒有右子節點，那麼左子節點即為前驅節點
* 2）刪除節點的左子節點有右子節點，那麼最右邊的最後一個節點即為前驅節點
* 後繼節點的特點：
* 與前驅節點剛好相反，總是右子節點，或則右子節點的最左子節點;例如：刪除節點為c ，那麼前驅節點為 m，後繼節點為n
*a
*/\
*bc
*/ \/\
*defg
*/\/ \/ \/ \
* @param item 刪除元素hijklm no
* @return 刪除結果
*/
public boolean remove(T item){
//獲取刪除節點
Entry<T> delEntry = getEntry(item);
if (delEntry == null) return false;
//刪除節點的父節點
Entry<T> p = delEntry.parent;
size--;
//情況1：沒有子節點
if (delEntry.left == null && delEntry.right == null){
//刪除節點為根節點
if (delEntry == root){
root = null;
}else {//非根節點
//刪除的是父節點的左節點
if (delEntry == p.left){
p.left = null;
}else {//刪除右節點
p.right = null;
}
}
//情況2：刪除的節點只有左節點
}else if (delEntry.right == null){
Entry<T> lc = delEntry.left;
//刪除的節點為根節點，將刪除節點的左節點設定成根節點
if (p == null) {
lc.parent = null;
root = lc;
} else {//非根節點
if (delEntry == p.left){//刪除左節點
p.left = lc;
}else {//刪除右節點
p.right = lc;
}
lc.parent = p;
}
//情況3：刪除節點只有右節點
}else if (delEntry.left == null){
Entry<T> rc = delEntry.right;
//刪除根節點
if (p == null) {
rc.parent = null;
root = rc;
}else {//刪除非根節點
if (delEntry == p.left)
p.left = rc;
else
p.right = rc;
rc.parent = p;
}
//情況4：刪除節點有兩個子節點
}else {//有兩個節點,找到後繼節點，將值賦給刪除節點，然後將後繼節點刪除掉即可
Entry<T> successor = successor(delEntry);//獲取到後繼節點
delEntry.item = successor.item;
//後繼節點為右子節點
if (delEntry.right == successor){
//右子節點有右子節點
if (successor.right != null) {
delEntry.right = successor.right;
successor.right.parent = delEntry;
}else {//右子節點沒有子節點
delEntry.right = null;
}
}else {//後繼節點必定是左節點
successor.parent.left = null;
}
return true;
}
//讓gc回收
delEntry.parent = null;
delEntry.left = null;
delEntry.right = null;
return true;
}

/**
* 查詢後繼節點
* @param delEntry 刪除節點
* @return 後繼節點
*/
private Entry<T> successor(Entry<T> delEntry) {
Entry<T> r = delEntry.right;//r節點必定不為空
while (r.left != null){
r = r.left;
}
return r;
}

public int size(){return size;}

public boolean isEmpty(){return size == 0;}

public void clear(){
clear(getRoot());
root = null;
}

private void clear(Entry<T> e){
if (e != null){
clear(e.left);
e.left = null;
clear(e.right);
e.right = null;
}
}

static final class Entry<T extends Comparable<T>>{
//儲存的資料
private T item;
//左子樹
private Entry<T> left;
//右子樹
private Entry<T> right;
//父節點
private Entry<T> parent;
Entry(T item,Entry<T> parent){
this.item = item;
this.parent = parent;
}
}

}

純手寫的demo，有什麼錯誤的地方歡迎指正，謝謝大家的閱讀！！！