特点：结合有序组和链表的优点
查找
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.调用自身来遍历节点的左子树
2.访问自己节点
3....右子树
private void inOrder(node localRoot) {
if(localRoot != null) {
inOrder(localRoot.leftChild);
System.out.println(localRoot.iData + "");
inOrder(localRoot.rightChild);
}
}
前序：
1.访问自己节点
2.自身左子树
3.自身右子树
后序：自己想
最小值和最大值：最下最左左子树，最下最右右子树
删除节点
三种情况：
1.该节点是叶节点（没有子节点）
2.该节点有一个子节点
3.该节点有两个子节点
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;
}
//第二种情况：没有左节点或没有右节点，都要考虑被删除节点可能是根
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;
}
//第三种情况：双节点又分两种情况，第一种后继节点是delNode的右节点参考图8.19，第二种后继节点是delNode右子节点的左后代参考图8.20
Node successor = getSuccessor(current);
if(current == root)
root = successor;
else if(isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = current.leftChild;
}
return true;
}
//查找后继节点，参照图8.17和8.18是两种情况
private node getSuccessor(node delNode) {
Node SuccessorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild;
//参照图8.17，38是需要删除的节点
while(current != null) {
SuccessorParent = successor;
successor = current;
current = current.leftChild;
}
//参照图8.18，假如不等于，这两句代码是实现第二种情况的树旋转
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
