一荤堪、定義
- 查找二叉樹(shù)又叫二叉排序樹(shù)合陵，如果同時(shí)滿足以下性質(zhì)：
- 左右子樹(shù)都是
二叉樹(shù)枢赔；
- 如果
左子樹(shù)不為空，那么左子樹(shù)上面的所有節(jié)點(diǎn)的關(guān)鍵字都比根節(jié)點(diǎn)的關(guān)鍵字杏抵糠爬；
- 如果
右子樹(shù)不為空，那么右子樹(shù)上面的所有節(jié)點(diǎn)的關(guān)鍵字都比跟節(jié)點(diǎn)的關(guān)鍵字大举庶；
- 好處：方便查找执隧，可以提高查找效率，查找二叉樹(shù)越平衡户侥，查找的效率的越穩(wěn)定镀琉，效率越高，這種樹(shù)就是
平衡二叉樹(shù)蕊唐；
二屋摔、代碼實(shí)現(xiàn)
public class SearchBinaryTree {
private TreeNode root;//跟節(jié)點(diǎn)
/**
* 創(chuàng)建查找二叉樹(shù)，如果關(guān)鍵字比根節(jié)點(diǎn)的關(guān)鍵字大替梨，就往右邊插入钓试，
* 如果關(guān)鍵字比根節(jié)點(diǎn)小，就往左邊插入
* @param data 帶插入的數(shù)據(jù)
* @return
*/
public TreeNode put(int data) {
TreeNode node = null;
TreeNode parent = null;
//首先判斷根節(jié)點(diǎn)副瀑，如果根節(jié)點(diǎn)為空弓熏，則新創(chuàng)建的節(jié)點(diǎn)為根節(jié)點(diǎn)
if (root == null) {
node = new TreeNode(0, data);
root = node;
return node;
} else {
//如果不是根節(jié)點(diǎn)，就需要不停地遍歷已有的節(jié)點(diǎn)糠睡，找到滿足條件的節(jié)點(diǎn)的位置挽鞠，然后插入節(jié)點(diǎn)
//和根節(jié)點(diǎn)進(jìn)行比較，首先要拿到根節(jié)點(diǎn)
node = root;
while (node != null) {
//把當(dāng)前結(jié)點(diǎn)制定為父節(jié)點(diǎn)狈孔，然后比較左右孩子和當(dāng)前節(jié)點(diǎn)的大小
parent = node;
//如果要插入的數(shù)據(jù)比當(dāng)前結(jié)點(diǎn)要大信认，就需要往右子樹(shù)上找
if (data > node.data) {
node = node.rightChild;
} else if (data < node.data) {
node = node.leftChild;
} else {
return node;
}
}
//while循環(huán)結(jié)束，就表示找到了要插入的地方均抽，
// 接下來(lái)就是創(chuàng)建節(jié)點(diǎn)嫁赏，然后把這個(gè)節(jié)點(diǎn)掛在指定的位置
//角標(biāo)默認(rèn)是0
node = new TreeNode(0, data);
//節(jié)點(diǎn)創(chuàng)建完畢，需要判斷放在父節(jié)點(diǎn)的左邊還是右邊
if (data < parent.data) {
parent.leftChild = node;
} else {
parent.rightChild = node;
}
//指定這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)
node.parent = parent;
return node;
}
}
/**
* 刪除二叉查找樹(shù)中的某個(gè)節(jié)點(diǎn)油挥，
* <strong>因?yàn)槭嵌娌檎覙?shù)潦蝇，所以是刪除某個(gè)節(jié)點(diǎn)后，需要對(duì)剩下的節(jié)點(diǎn)進(jìn)行
* 重新排序喘漏，使之依然是二叉查找樹(shù)
* </strong>
* @param data
*/
public void deleteNode(int data) {
//要想刪除某個(gè)節(jié)點(diǎn)护蝶，必須先找到這個(gè)節(jié)點(diǎn)
TreeNode node = searchNode(data);
//如果node為空华烟，表示沒(méi)有找到
if (node == null) {
throw new NoSuchElementException("沒(méi)有指定的節(jié)點(diǎn)");
} else {
delete(node);
}
}
/**
* 刪除節(jié)點(diǎn)
* @param node 要?jiǎng)h除的節(jié)點(diǎn)
*/
private void delete(TreeNode node) {
if (node == null) {
throw new NoSuchElementException("沒(méi)有這個(gè)節(jié)點(diǎn)");
} else {
//如果當(dāng)前節(jié)點(diǎn)不為空翩迈，就需要判斷這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，左右孩子節(jié)點(diǎn)是否為空
TreeNode parent = node.parent;
//如果 當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)盔夜，直接刪除
if (node.leftChild == null && node.rightChild == null) {
//需要判斷是父親的左兒子還是右兒子
if (parent.leftChild == node) {
parent.leftChild = null;
node.parent = null;
} else {
parent.rightChild = null;
node.parent = null;
}
} else if (node.leftChild != null && node.rightChild == null) {
//如果被刪除的節(jié)點(diǎn)有左孩子沒(méi)有右孩子
//這是還需要判斷這個(gè)節(jié)點(diǎn)是在父節(jié)點(diǎn)的左子樹(shù)上负饲，還是在右子樹(shù)上
//如果這個(gè)節(jié)點(diǎn)在左子樹(shù)上堤魁，就需要把這個(gè)節(jié)點(diǎn)的左孩子放在parent的左子樹(shù)上
if (parent.leftChild == node) {
parent.leftChild = node.leftChild;
} else {
parent.rightChild = node.leftChild;
}
} else if (node.leftChild == null && node.rightChild != null) {
//如果被刪除的節(jié)點(diǎn)有右孩子而沒(méi)有左孩子
if (parent.leftChild == node) {
parent.leftChild = node.rightChild;
} else {
parent.rightChild = node.rightChild;
}
} else if (node.leftChild != null && node.rightChild != null) {
//如果被刪除的節(jié)點(diǎn)既有左孩子又有右孩子
//找后繼節(jié)點(diǎn)
TreeNode next = getNextNode(node);
delete(next);
node.data = next.data;
}
}
}
/**
* 找到某個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)
* @param node
* @return
*/
private TreeNode getNextNode(TreeNode node) {
if (node == null) {
return null;
} else {
//如果這個(gè)節(jié)點(diǎn)的右子樹(shù)不為空，就在右子樹(shù)里面找到key最小的節(jié)點(diǎn)
if (node.rightChild != null) {
return getMinTreeNode(node);
} else {
TreeNode parent = node.parent;
while (parent == null && node == parent.rightChild) {
node = parent;
parent = parent.parent;
}
return parent;
}
}
}
/**
* 找到這個(gè)節(jié)點(diǎn)的子樹(shù)下面key最小的節(jié)點(diǎn),最小的節(jié)點(diǎn)一定在該節(jié)點(diǎn)的左子樹(shù)上的最末端
* @param node
* @return
*/
private TreeNode getMinTreeNode(TreeNode node) {
if (node == null) {
return null;
} else {
while (node.leftChild != null) {
node = node.leftChild;
}
}
return node;
}
private TreeNode searchNode(int data) {
TreeNode node;
//先從根節(jié)點(diǎn)開(kāi)始找
node = root;
if (node == null) {
return null;
} else {
while (node != null && data != node.data) {
if (data > node.data) {
node = node.rightChild;
} else if (data < node.data) {
node = node.leftChild;
} else {
return node;
}
}
//當(dāng)while循環(huán)結(jié)束后返十，就表示已經(jīng)遍歷完了整個(gè)二叉查找樹(shù)妥泉，
// 有可能找到，有可能找不到洞坑，即node有可能為null
return node;
}
}
/**
* 中序遍歷二叉查找樹(shù)盲链，如果樹(shù)構(gòu)建的正確，中序遍歷出來(lái)應(yīng)該是升序的
* @param node
*/
public void midOrderTraverse(TreeNode node) {
midOrderTraverse(node.leftChild);
System.out.print(node.data + " ");
midOrderTraverse(node.rightChild);
}
private static final class TreeNode {
private int key;//二叉查找樹(shù)的關(guān)鍵字迟杂，通過(guò)這個(gè)關(guān)鍵字對(duì)節(jié)點(diǎn)進(jìn)行排序
private TreeNode leftChild;
private TreeNode rightChild;
private TreeNode parent;
private int data;
public TreeNode(int key, int data) {
this.key = key;
this.data = data;
this.leftChild = null;
this.rightChild = null;
this.parent = null;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public TreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(TreeNode leftChild) {
this.leftChild = leftChild;
}
public TreeNode getRightChild() {
return rightChild;
}
public void setRightChild(TreeNode rightChild) {
this.rightChild = rightChild;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
}
}
