特點：結(jié)合有序組和鏈表的優(yōu)點
查找
public Node find(int key) {
Node current = root;
while(current.iData != key) {
if(key<current.iData)
current = current.leftChild;
else
current = current.rightChild;
if(current == null) {
return null;
}
}
return current;
}
插入：順著查找的思路搜变，在返回前插入
public void insert(int id, double dd) {
Node newNode = new Node();
newNode.iData = id;
newNode.dData = dd;
if(root == null) {
root = newNode;
} else {
Node current = root;
Node parent;
while(true) {
parent = current;
if(id < current.iData) {
current = current.leftChild;
if(current == null) {
parent.leftChild = newNode;
return;
}
}else {
current = current.rightChild;
if(current == null) {
parent.rightChild = newNode;
return;
}
}
}
}
}
遍歷樹
中序遍歷：
1.調(diào)用自身來遍歷節(jié)點的左子樹
2.訪問自己節(jié)點
3....右子樹
private void inOrder(node localRoot) {
if(localRoot != null) {
inOrder(localRoot.leftChild);
System.out.println(localRoot.iData + "");
inOrder(localRoot.rightChild);
}
}
前序：
1.訪問自己節(jié)點
2.自身左子樹
3.自身右子樹
后序：自己想
最小值和最大值：最下最左左子樹，最下最右右子樹
刪除節(jié)點
三種情況：
1.該節(jié)點是葉節(jié)點（沒有子節(jié)點）
2.該節(jié)點有一個子節(jié)點
3.該節(jié)點有兩個子節(jié)點
public boolean delete(int key) {
Node current = root;
Node parent = root;
boolean isLeftChild = true;
//和查找一樣
while(current.iData != key) {
parent = current;
if(key<current.iData) {
isLeftChild = true;
current = current.leftChild;
}
else {
isLeftChild = false;
current = current.rightChild;
}
if(current == null) {
return null;
}
}
//找到之后
//第一種情況
if(current.leftChild == null && current.rightChild == null) {
if(current == root)
root = null;
else if(isLeftChild)
parent.leftChild = null;
else
parent.rightChild = null;
}
//第二種情況：沒有左節(jié)點或沒有右節(jié)點嗽交，都要考慮被刪除節(jié)點可能是根
else if(current.rightChild == null) {
if(current == root)
root = current.leftChild;
else if(isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.rightChild;
}
else if(current.leftChild == null) {
if(current == root)
root = current.rightChild;
else if(isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.rightChild;
}
//第三種情況：雙節(jié)點又分兩種情況，第一種后繼節(jié)點是delNode的右節(jié)點參考圖8.19路狮，第二種后繼節(jié)點是delNode右子節(jié)點的左后代參考圖8.20
Node successor = getSuccessor(current);
if(current == root)
root = successor;
else if(isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = current.leftChild;
}
return true;
}
//查找后繼節(jié)點周蹭，參照圖8.17和8.18是兩種情況
private node getSuccessor(node delNode) {
Node SuccessorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild;
//參照圖8.17绰筛，38是需要刪除的節(jié)點
while(current != null) {
SuccessorParent = successor;
successor = current;
current = current.leftChild;
}
//參照圖8.18，假如不等于逐工，這兩句代碼是實現(xiàn)第二種情況的樹旋轉(zhuǎn)
if(successor != delNode.rightChild){
SuccessorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
Paste_Image.png
Paste_Image.png
Paste_Image.png
哈夫曼
專用于壓縮文本
Paste_Image.png
Paste_Image.png
Paste_Image.png
重點解釋：用10表示S,用00表示空格后铡溪，不能再用01和11，因為它們是其它字符的前綴泪喊，不夠就用三位來組合：000棕硫，001，010袒啼，011哈扮，100，110蚓再，111. A是010滑肉，I是110，因為除去10和00開始的組合摘仅，在用四位表示其它字符靶庙，依此類推
Paste_Image.png
Paste_Image.png
