一段來自百度百科的對(duì)二叉樹的解釋：
在計(jì)算機(jī)科學(xué)中桐款，二叉樹是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）夷恍。二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆魔眨。
一棵深度為k，且有2^k-1個(gè)節(jié)點(diǎn)的二叉樹酿雪，稱為滿二叉樹遏暴。這種樹的特點(diǎn)是每一層上的節(jié)點(diǎn)數(shù)都是最大節(jié)點(diǎn)數(shù)。而在一棵二叉樹中指黎，除最后一層外朋凉，若其余層都是滿的，并且最后一層或者是滿的醋安，或者是在右邊缺少連續(xù)若干節(jié)點(diǎn)杂彭，則此二叉樹為完全二叉樹。具有n個(gè)節(jié)點(diǎn)的完全二叉樹的深度為floor(log2n)+1吓揪。深度為k的完全二叉樹亲怠，至少有2k-1個(gè)葉子節(jié)點(diǎn)，至多有2k-1個(gè)節(jié)點(diǎn)磺芭。
二叉樹的結(jié)構(gòu)：
image
二叉樹節(jié)點(diǎn)的聲明：
static final class Entry<T extends Comparable<T>>{ //保存的數(shù)據(jù)
private T item; //左子樹
private Entry<T> left; //右子樹
private Entry<T> right; //父節(jié)點(diǎn)
private Entry<T> parent;
Entry(T item,Entry<T> parent){ this.item = item; this.parent = parent;
}
}
類屬性：
//根節(jié)點(diǎn)
private Entry<T> root;
//數(shù)據(jù)量
private int size = 0;
二叉樹添加數(shù)據(jù)：
/**
* 添加元素
* @param item 待添加元素
* @return 已添加元素
*/
public T put(T item){
//每次添加數(shù)據(jù)的時(shí)候都是從根節(jié)點(diǎn)向下遍歷
Entry<T> t = root;
if (t == null){
//當(dāng)前的叉樹樹的為空赁炎，將新節(jié)點(diǎn)設(shè)置為根節(jié)點(diǎn)，父節(jié)點(diǎn)為null
root = new Entry<>(item,null); size++;
return root.item;
}
//自然排序結(jié)果钾腺，如果傳入的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)返回-1徙垫，大于當(dāng)前節(jié)點(diǎn)返回1，否則返回0
int ret = 0;
//記錄父節(jié)點(diǎn)
Entry<T> p = t;
while (t != null){
//與當(dāng)前節(jié)點(diǎn)比較
ret = item.compareTo(t.item);
p = t;
//插入節(jié)點(diǎn)比當(dāng)前節(jié)點(diǎn)小放棒，把當(dāng)前節(jié)點(diǎn)設(shè)置為左子節(jié)點(diǎn)姻报，然后與左子比較，以此類推找到合適的位置
if (ret < 0)
t = t.left;
//大于當(dāng)前節(jié)點(diǎn)
else if (ret > 0)
t = t.right;
else {
//相等就把舊值覆蓋掉
t.item = item;
return t.item;
}
}
//創(chuàng)建新節(jié)點(diǎn)
Entry<T> e = new Entry<>(item,p);
//根據(jù)比較結(jié)果將新節(jié)點(diǎn)放入合適的位置
if (ret < 0)
p.left = e;
else
p.right = e; size++;
return e.item;
}
在put的過程中间螟，使用Comparable<T>中的compareTo來比較兩個(gè)元素的大小的吴旋，所以在二叉樹中存儲(chǔ)的元素必須要繼承Comparable<T> 類损肛，覆寫compareTo方法。
二叉樹刪除數(shù)據(jù)
/**
* 刪除元素
* 刪除元素如果細(xì)分的話荣瑟，可以分為4中：沒有子節(jié)點(diǎn)治拿，只有左節(jié)點(diǎn)，只有右節(jié)點(diǎn)笆焰，有兩個(gè)子節(jié)點(diǎn)
* 1）沒有子節(jié)點(diǎn)這種情況比較簡(jiǎn)單劫谅，直接刪除就可以了
* 2）只有左節(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)）指向刪除節(jié)點(diǎn)的父節(jié)點(diǎn)
* 3）有兩個(gè)子節(jié)點(diǎn)贯城，這種情況相對(duì)來說比較復(fù)雜一點(diǎn)：
* 找到刪除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)或后繼節(jié)點(diǎn)，然后將前驅(qū)或后繼節(jié)點(diǎn)的值賦給刪除節(jié)點(diǎn)霹娄，然后將前驅(qū)或后繼節(jié)點(diǎn)刪除能犯。本質(zhì)是刪除前驅(qū)或后繼節(jié)點(diǎn)
* 前驅(qū)節(jié)點(diǎn)的特點(diǎn)：
* 1）刪除的左子節(jié)點(diǎn)沒有右子節(jié)點(diǎn)，那么左子節(jié)點(diǎn)即為前驅(qū)節(jié)點(diǎn)
* 2）刪除節(jié)點(diǎn)的左子節(jié)點(diǎn)有右子節(jié)點(diǎn)犬耻，那么最右邊的最后一個(gè)節(jié)點(diǎn)即為前驅(qū)節(jié)點(diǎn)
* 后繼節(jié)點(diǎn)的特點(diǎn)：
* 與前驅(qū)節(jié)點(diǎn)剛好相反悲雳，總是右子節(jié)點(diǎn)，或則右子節(jié)點(diǎn)的最左子節(jié)點(diǎn);例如：刪除節(jié)點(diǎn)為c 香追，那么前驅(qū)節(jié)點(diǎn)為 m，后繼節(jié)點(diǎn)為n
* a
* / \
* b c
* / \ / \
* d e f g
* / \ / \ / \ / \
* @param item 刪除元素 h i j k l m n o
* @return 刪除結(jié)果 */
public boolean remove(T item){ //獲取刪除節(jié)點(diǎn)
Entry<T> delEntry = getEntry(item); if (delEntry == null) return false; //刪除節(jié)點(diǎn)的父節(jié)點(diǎn)
Entry<T> p = delEntry.parent;
size--; //情況1：沒有子節(jié)點(diǎn)
if (delEntry.left == null && delEntry.right == null){ //刪除節(jié)點(diǎn)為根節(jié)點(diǎn)
if (delEntry == root){
root = null;
}else {//非根節(jié)點(diǎn) //刪除的是父節(jié)點(diǎn)的左節(jié)點(diǎn)
if (delEntry == p.left){
p.left = null;
}else {//刪除右節(jié)點(diǎn)
p.right = null;
}
} //情況2：刪除的節(jié)點(diǎn)只有左節(jié)點(diǎn)
}else if (delEntry.right == null){
Entry<T> lc = delEntry.left; //刪除的節(jié)點(diǎn)為根節(jié)點(diǎn)坦胶，將刪除節(jié)點(diǎn)的左節(jié)點(diǎn)設(shè)置成根節(jié)點(diǎn)
if (p == null) {
lc.parent = null;
root = lc;
} else {//非根節(jié)點(diǎn)
if (delEntry == p.left){//刪除左節(jié)點(diǎn)
p.left = lc;
}else {//刪除右節(jié)點(diǎn)
p.right = lc;
}
lc.parent = p;
} //情況3：刪除節(jié)點(diǎn)只有右節(jié)點(diǎn)
}else if (delEntry.left == null){
Entry<T> rc = delEntry.right; //刪除根節(jié)點(diǎn)
if (p == null) {
rc.parent = null;
root = rc;
}else {//刪除非根節(jié)點(diǎn)
if (delEntry == p.left)
p.left = rc; else p.right = rc;
rc.parent = p;
} //情況4：刪除節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
}else {//有兩個(gè)節(jié)點(diǎn),找到后繼節(jié)點(diǎn)透典，將值賦給刪除節(jié)點(diǎn)，然后將后繼節(jié)點(diǎn)刪除掉即可
Entry<T> successor = successor(delEntry);//獲取到后繼節(jié)點(diǎn)
delEntry.item = successor.item; //后繼節(jié)點(diǎn)為右子節(jié)點(diǎn)
if (delEntry.right == successor){ //右子節(jié)點(diǎn)有右子節(jié)點(diǎn)
if (successor.right != null) {
delEntry.right = successor.right;
successor.right.parent = delEntry;
}else {//右子節(jié)點(diǎn)沒有子節(jié)點(diǎn)
delEntry.right = null;
}
}else {//后繼節(jié)點(diǎn)必定是左節(jié)點(diǎn)
successor.parent.left = null;
} return true;
} //讓gc回收
delEntry.parent = null;
delEntry.left = null;
delEntry.right = null; return true;
} /**
* 獲取節(jié)點(diǎn)節(jié)點(diǎn)
* @param item 獲取節(jié)點(diǎn)
* @return 獲取到的節(jié)點(diǎn)顿苇，可能為null */
private Entry<T> getEntry(T item){
Entry<T> t = root; int ret; //從根節(jié)點(diǎn)開始遍歷
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;
} /**
* 查找后繼節(jié)點(diǎn)
* @param delEntry 刪除節(jié)點(diǎn)
* @return 后繼節(jié)點(diǎn) */
private Entry<T> successor(Entry<T> delEntry) {
Entry<T> r = delEntry.right;//r節(jié)點(diǎn)必定不為空
while (r.left != null){
r = r.left;
} return r;
}
二叉樹獲取節(jié)點(diǎn)
/**
* 判斷是否存在該元素
* @param item 查找元素
* @return 結(jié)果 */
public boolean contains(T item){ return getEntry(item) != null;
} /**
* 獲取節(jié)點(diǎn)節(jié)點(diǎn)
* @param item 獲取節(jié)點(diǎn)
* @return 獲取到的節(jié)點(diǎn)峭咒，可能為null */
private Entry<T> getEntry(T item){
Entry<T> t = root; int ret; //從根節(jié)點(diǎn)開始遍歷
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;
}
因?yàn)槲疫@個(gè)例子是存儲(chǔ)一個(gè)元素，獲取到的元素和傳進(jìn)去的元素是一致的纪岁，所以我用contains方法來判斷返回true即表示獲取成功了凑队，不返回獲取到的結(jié)果了。當(dāng)然幔翰，如果將entry存儲(chǔ)的元素改為kv形式的話漩氨，就可以使用get方法了。
二叉樹的遍歷
二叉樹的遍歷可以分為三種：前序遍歷遗增、中序遍歷和后續(xù)遍歷叫惊，其中中序遍歷是最常用的遍歷方式，因?yàn)樗闅v出來的結(jié)果的升序的做修。
前序遍歷：
/**
* 前序遍歷
* @param e 開始遍歷元素 */
public void prevIterator(Entry<T> e){ if (e != null) {
System.out.print(e.item + " ");
prevIterator(e.left);
prevIterator(e.right);
}
}</pre>
中序遍歷：
<pre style="color: rgb(0, 0, 0); font-family: "Courier New"; font-size: 12px; margin: 5px 8px; padding: 5px;"> /**
* 中序遍歷
* @param e */
public void midIterator(Entry<T> e){ if (e != null){
midIterator(e.left);
System.out.print(e.item + " ");
midIterator(e.right);
}
}
后序遍歷：
/**
* 后續(xù)遍歷
* @param e 開始遍歷元素 */
public void subIterator(Entry<T> e){ if (e != null) {
subIterator(e.left);
subIterator(e.right);
System.out.print(e.item + " ");
}
}
demo完整的代碼：也可以到我的github中下載代碼：https://github.com/rainple1860/MyCollection
/**
* 二叉樹
* @param <T> */
public class BinaryTree<T extends Comparable<T>> { //根節(jié)點(diǎn)
private Entry<T> root; //數(shù)據(jù)量
private int size = 0; public BinaryTree(){} /**
* 添加元素
* @param item 待添加元素
* @return 已添加元素 */
public T put(T item){ //每次添加數(shù)據(jù)的時(shí)候都是從根節(jié)點(diǎn)向下遍歷
Entry<T> t = root;
size++; if (t == null){ //當(dāng)前的叉樹樹的為空霍狰，將新節(jié)點(diǎn)設(shè)置為根節(jié)點(diǎn)抡草，父節(jié)點(diǎn)為null
root = new Entry<>(item,null); return root.item;
} //自然排序結(jié)果，如果傳入的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)返回-1蔗坯，大于當(dāng)前節(jié)點(diǎn)返回1康震，否則返回0
int ret = 0; //記錄父節(jié)點(diǎn)
Entry<T> p = t; while (t != null){ //與當(dāng)前節(jié)點(diǎn)比較
ret = item.compareTo(t.item);
p = t; //插入節(jié)點(diǎn)比當(dāng)前節(jié)點(diǎn)小，把當(dāng)前節(jié)點(diǎn)設(shè)置為左子節(jié)點(diǎn)宾濒，然后與左子比較腿短，以此類推找到合適的位置
if (ret < 0)
t = t.left; //大于當(dāng)前節(jié)點(diǎn)
else if (ret > 0)
t = t.right; else { //相等就把舊值覆蓋掉
t.item = item; return t.item;
}
} //創(chuàng)建新節(jié)點(diǎn)
Entry<T> e = new Entry<>(item,p); //根據(jù)比較結(jié)果將新節(jié)點(diǎn)放入合適的位置
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);
}
} /**
* 獲取根節(jié)點(diǎn)
* @return 根節(jié)點(diǎn) */
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);
}
} /**
* 后續(xù)遍歷
* @param e 開始遍歷元素 */
public void subIterator(Entry<T> e){ if (e != null) {
subIterator(e.left);
subIterator(e.right);
System.out.print(e.item + " ");
}
} /**
* 獲取節(jié)點(diǎn)節(jié)點(diǎn)
* @param item 獲取節(jié)點(diǎn)
* @return 獲取到的節(jié)點(diǎn)，可能為null */
private Entry<T> getEntry(T item){
Entry<T> t = root; int ret; //從根節(jié)點(diǎn)開始遍歷
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 結(jié)果 */
public boolean contains(T item){ return getEntry(item) != null;
} /**
* 刪除元素
* 刪除元素如果細(xì)分的話鼎兽，可以分為4中：沒有子節(jié)點(diǎn)答姥，只有左節(jié)點(diǎn)，只有右節(jié)點(diǎn)谚咬，有兩個(gè)子節(jié)點(diǎn)
* 1）沒有子節(jié)點(diǎn)這種情況比較簡(jiǎn)單鹦付，直接刪除就可以了
* 2）只有左節(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)）指向刪除節(jié)點(diǎn)的父節(jié)點(diǎn)
* 3）有兩個(gè)子節(jié)點(diǎn)祈噪，這種情況相對(duì)來說比較復(fù)雜一點(diǎn)：
* 找到刪除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)或后繼節(jié)點(diǎn)，然后將前驅(qū)或后繼節(jié)點(diǎn)的值賦給刪除節(jié)點(diǎn)尚辑，然后將前驅(qū)或后繼節(jié)點(diǎn)刪除辑鲤。本質(zhì)是刪除前驅(qū)或后繼節(jié)點(diǎn)
* 前驅(qū)節(jié)點(diǎn)的特點(diǎn)：
* 1）刪除的左子節(jié)點(diǎn)沒有右子節(jié)點(diǎn)，那么左子節(jié)點(diǎn)即為前驅(qū)節(jié)點(diǎn)
* 2）刪除節(jié)點(diǎn)的左子節(jié)點(diǎn)有右子節(jié)點(diǎn)杠茬，那么最右邊的最后一個(gè)節(jié)點(diǎn)即為前驅(qū)節(jié)點(diǎn)
* 后繼節(jié)點(diǎn)的特點(diǎn)：
* 與前驅(qū)節(jié)點(diǎn)剛好相反月褥，總是右子節(jié)點(diǎn)，或則右子節(jié)點(diǎn)的最左子節(jié)點(diǎn);例如：刪除節(jié)點(diǎn)為c 瓢喉，那么前驅(qū)節(jié)點(diǎn)為 m宁赤，后繼節(jié)點(diǎn)為n
* a
* / \
* b c
* / \ / \
* d e f g
* / \ / \ / \ / \
* @param item 刪除元素 h i j k l m n o
* @return 刪除結(jié)果 */
public boolean remove(T item){ //獲取刪除節(jié)點(diǎn)
Entry<T> delEntry = getEntry(item); if (delEntry == null) return false; //刪除節(jié)點(diǎn)的父節(jié)點(diǎn)
Entry<T> p = delEntry.parent;
size--; //情況1：沒有子節(jié)點(diǎn)
if (delEntry.left == null && delEntry.right == null){ //刪除節(jié)點(diǎn)為根節(jié)點(diǎn)
if (delEntry == root){
root = null;
}else {//非根節(jié)點(diǎn) //刪除的是父節(jié)點(diǎn)的左節(jié)點(diǎn)
if (delEntry == p.left){
p.left = null;
}else {//刪除右節(jié)點(diǎn)
p.right = null;
}
} //情況2：刪除的節(jié)點(diǎn)只有左節(jié)點(diǎn)
}else if (delEntry.right == null){
Entry<T> lc = delEntry.left; //刪除的節(jié)點(diǎn)為根節(jié)點(diǎn)，將刪除節(jié)點(diǎn)的左節(jié)點(diǎn)設(shè)置成根節(jié)點(diǎn)
if (p == null) {
lc.parent = null;
root = lc;
} else {//非根節(jié)點(diǎn)
if (delEntry == p.left){//刪除左節(jié)點(diǎn)
p.left = lc;
}else {//刪除右節(jié)點(diǎn)
p.right = lc;
}
lc.parent = p;
} //情況3：刪除節(jié)點(diǎn)只有右節(jié)點(diǎn)
}else if (delEntry.left == null){
Entry<T> rc = delEntry.right; //刪除根節(jié)點(diǎn)
if (p == null) {
rc.parent = null;
root = rc;
}else {//刪除非根節(jié)點(diǎn)
if (delEntry == p.left)
p.left = rc; else p.right = rc;
rc.parent = p;
} //情況4：刪除節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
}else {//有兩個(gè)節(jié)點(diǎn),找到后繼節(jié)點(diǎn)栓票，將值賦給刪除節(jié)點(diǎn)决左，然后將后繼節(jié)點(diǎn)刪除掉即可
Entry<T> successor = successor(delEntry);//獲取到后繼節(jié)點(diǎn)
delEntry.item = successor.item; //后繼節(jié)點(diǎn)為右子節(jié)點(diǎn)
if (delEntry.right == successor){ //右子節(jié)點(diǎn)有右子節(jié)點(diǎn)
if (successor.right != null) {
delEntry.right = successor.right;
successor.right.parent = delEntry;
}else {//右子節(jié)點(diǎn)沒有子節(jié)點(diǎn)
delEntry.right = null;
}
}else {//后繼節(jié)點(diǎn)必定是左節(jié)點(diǎn)
successor.parent.left = null;
} return true;
} //讓gc回收
delEntry.parent = null;
delEntry.left = null;
delEntry.right = null; return true;
} /**
* 查找后繼節(jié)點(diǎn)
* @param delEntry 刪除節(jié)點(diǎn)
* @return 后繼節(jié)點(diǎn) */
private Entry<T> successor(Entry<T> delEntry) {
Entry<T> r = delEntry.right;//r節(jié)點(diǎn)必定不為空
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>>{ //保存的數(shù)據(jù)
private T item; //左子樹
private Entry<T> left; //右子樹
private Entry<T> right; //父節(jié)點(diǎn)
private Entry<T> parent;
Entry(T item,Entry<T> parent){ this.item = item; this.parent = parent;
}
}
}
測(cè)試代碼示例：
public static void main(String[] args) {
BinaryTree<Integer> binaryTree = new BinaryTree<>(); //放數(shù)據(jù)
binaryTree.put(73);
binaryTree.put(22);
binaryTree.put(532);
binaryTree.put(62);
binaryTree.put(72);
binaryTree.put(243);
binaryTree.put(42);
binaryTree.put(3);
binaryTree.put(12);
binaryTree.put(52);
System.out.println("size： " + binaryTree.size());
binaryTree.put(52);
System.out.println("添加相同元素后的size： " + binaryTree.size()); //判斷數(shù)據(jù)是否存在
System.out.println("數(shù)據(jù)是否存在：" + binaryTree.contains(12)); //中序遍歷
System.out.print("中序遍歷結(jié)果： ");
binaryTree.midIterator(binaryTree.getRoot());
System.out.println(); //前序遍歷
System.out.print("前遍歷結(jié)果： ");
binaryTree.prevIterator(binaryTree.getRoot());
System.out.println(); //后序遍歷
System.out.print("后續(xù)遍歷結(jié)果： ");
binaryTree.subIterator(binaryTree.getRoot()); //刪除數(shù)據(jù)
System.out.println();
binaryTree.remove(62);
System.out.println("刪除數(shù)據(jù)后判斷是否存在：" + binaryTree.contains(62)); //清空二叉樹
binaryTree.clear();
System.out.print("清空數(shù)據(jù)后中序遍歷： ");
binaryTree.midIterator(binaryTree.getRoot());
}
測(cè)試結(jié)果：
size： 10
添加相同元素后的size： 10
數(shù)據(jù)是否存在：true
中序遍歷結(jié)果： 3 12 22 42 52 62 72 73 243 532
前遍歷結(jié)果： 73 22 3 12 62 42 52 72 532 243
后續(xù)遍歷結(jié)果： 12 3 52 42 72 62 22 243 532 73
刪除數(shù)據(jù)后判斷是否存在：false
清空數(shù)據(jù)后中序遍歷：
純手寫的demo，有什么錯(cuò)誤的地方歡迎指正走贪，謝謝大家的閱讀７鹈汀！坠狡！
