Chapter 9 Binary Trees.

Presentation on theme: "Chapter 9 Binary Trees."— Presentation transcript:

1 Chapter 9 Binary Trees

2 Outline Why Use Binary Trees? Tree Terminology（树的术语）
How Do Binary Search Trees Work? Finding a Node Inserting a Node Traversing the Tree（遍历树） Finding Maximum and Minimum Values Deleting a Node* The Efficiency of Binary Trees （二叉树的效率） Trees Represented as Arrays* The Huffman Code（哈夫曼编码）

3 Why Use Binary Trees? With it, you can…
It combines the advantages of two other structures: an ordered array and a linked list. Search quickly, as you can an ordered array. Insert and delete items quickly, as you can with a linked list. With it, you can…

4 Why Use Binary Trees? Slow Insertion in an Ordered Array
You first need to find where the object will go, and then move all the objects with greater keys up one space in the array to make room for it. Slow Searching in a Linked List You must start at the beginning of the list and visit each element until you find the one you’re looking for.

5 Why Use Binary Trees? Trees to the Rescue
It would be nice if there were a data structure with the quick insertion and deletion of a linked list, and also the quick searching of an ordered array. Trees provide both these characteristics, and are also one of the most interesting data structures.

6 Why Use Binary Trees? What is a Tree?
A tree consists of nodes connected by edges. Nodes Edges In computer programs, nodes often represent such entities as people, car parts, airline reservations…

7 Why Use Binary Trees? The lines (edges) between the nodes represent the way the nodes are related. It’s easy (and fast) for a program to get from one node to another if there is a line connecting them. The only way to get from node to node is to follow a path along the lines. Trees are small on the top and large on the bottom. This may seem upside-down compared with real trees, but generally a program starts an operation at the small end of the tree, and it’s (arguably) more natural to think about going from top to bottom, as in reading text.

8 Why Use Binary Trees? A binary tree has a maximum of two children.
Multiway tree

9 Tree Terminology(术语) A B C D E F G H I J
There must be one (and only one!) path from the root to any other node. The dashed line is a path (A,C,F,J) Root A Level 0 B is the parent of D and E B C Level 1 D is the left child of B E is the right child of B D E F G Level 2 H I J Level 3 A leaf node 叶子结点 A subtree with F as its root

10 Tree Terminology Visiting---A node is visited when program control arrives at the node, usually for the purpose of carrying out some operation on the node, such as checking the value of one of its data fields or displaying it. 为了访问Node A而经过Node B，对B则不算Visit. Traversing---To traverse a tree means to visit all the nodes in some specified order. Keys---We’ve seen that one data field in an object is usually designated a key value. This value is used to search for the item or perform other operations on it.

11 An Analogy（类比） The hierarchical file structure（层次文件结构）.
The root directory of a given device (designated with the backslash, as in C:\, on many systems) is the tree’s root. The directories one level below the root directory are its children. There may be many levels of subdirectories. Files represent leaves; they have no children of their own

12 Binary Search Trees（二叉查找树）
The Binary Tree Workshop Applet Key values range from 0 to 99. Level is limited to a depth of 5 Invariant in BST？ 一个结点总比其左孩子大 ；比其右孩子小。

13 Binary Search Trees（二叉查找树）
Unbalanced Trees（非平衡树） Most of their nodes on one side of the root or the other 在此情形下，树的搜索效率严重退化。

14 Binary Search Trees（二叉查找树）
如何用java表述二叉查找树？ Java World Real World className fields methods Entity（实体） Action（行为） State（状态）

15 Binary Search Trees（二叉查找树）
Representing the Tree in Java Code class Node{ int iData; // data used as key value double fData; // other data Node leftChild; // this node’s left child Node rightChild; // this node’s right child public void displayNode() { // (see Listing 8.1 for method body) }

16 Binary Search Trees（二叉查找树）
This approach makes it conceptually clearer that the node and the data item it holds aren’t the same thing, but it results in somewhat more complicated code. class Node{ Person p1; // reference to person object Node leftChild; // this node’s left child Node rightChild; // this node’s right child } class Person{ int iData; double fData;

17 Binary Search Trees（二叉查找树）
The Tree Class They are used for finding, inserting, and deleting nodes; for different kinds of traverses; and for displaying the tree. class Tree{ private Node root; // the only data field in Tree public void find(int key) {//…} public void insert(int id, double dd){//… } public void delete(int id) {//… // various other methods } // end class Tree

18 A Tree object A Node object iData root leftChild rightChild iData
null

19 The TreeApp Class class TreeApp{
public static void main(String[] args){ Tree theTree = new Tree; // make a tree theTree.insert(50, 1.5); // insert 3 nodes theTree.insert(25, 1.7); theTree.insert(75, 1.9); Node found = theTree.find(25); // find node with key 25 if(found != null) System.out.println(“Found the node with key 25”); else System.out.println(“Could not find node with key 25”); } // end main() } // end class TreeApp

20 Finding a Node Using the Workshop Applet to Find a Node
As the Workshop applet looks for the specified node, the prompt will display either Going to left child or Going to right child, and the red arrow will move down one level to the right or left. Node find(int key){ //… if(key > current.iData) // go right {//… } else{ // go left

21 Finding a Node Java Code for Finding a Node(递归方式)
public Node recFind(int key, Node current) { if(current == null) return null; if(current.iData == key) return current; if(current.iData > key) return recFind(key, current.leftChild); else return recFind(key, current.rightChild); } public Node recFind(int key) { return recFind(key, root); }

22 Finding a Node Java Code for Finding a Node（非递归方式）
public Node find(int key) // find node with given key { // (assumes non-empty tree) Node current = root; // start at root while(current.iData != key) // while no match, { if(key < current.iData) // go left? current = current.leftChild; else current = current.rightChild; // or go right? if(current == null) // if no child, return null; // didn’t find it } return current; // found it

23 Finding a Node 时间复杂度为与层数L成比例 2L-1≥N→L ≥log2(N+1) 即O（N）=log2N
Tree Efficiency The time required to find a node depends on how many levels down it is situated. This is O(logN) time, or more specifically O(log2N) 层数 1 2 3 … L 结点数 7 N≤（2L-1） 时间复杂度为与层数L成比例 2L-1≥N→L ≥log2(N+1) 即O（N）=log2N

24 Inserting a Node 条件1：有空位 条件2：如果是左孩子位空，新结点要比parent小；如果右孩子位空，新结点要比parent大。 To insert a node, we must first find the place to insert it. 关键是要找到新Node的parent！（要满足的条件？） When this parent is found, the new node is connected as its left or right child, depending on whether the new node’s key is less or greater than that of the parent.

25 Inserting a Node root null … 60 45 40 30 50
Using the Workshop Applet to Insert a Node root 60 45 40 I think I have found it 30 50 null …

26 Inserting a Node Java Code for Inserting a Node
A place to insert a new node will always be found (unless you run out of memory); when it is, and the new node is attached, the while loop exits with a return statement.

27 Traversing the Tree（遍历树）
Traversing a tree means visiting each node in a specified order. There are three simple ways to traverse a tree： inorder（中序） preorder（前序） postorder（后序） in pre post order The order most commonly used for binary search trees is inorder.

28 Traversing the Tree Traversing with the Workshop Applet

29 Traversing the Tree Inorder Traversal（中序遍历）
An inorder traversal of a binary search tree will cause all the nodes to be visited in ascending order（升序）, based on their key values. 如果想从二叉查找树中得到一个有序的序列，就可以用中序遍历得到。 递归方法进行中序遍历: 1. Call itself to traverse the node’s left subtree. 2. Visit the node---displaying it, writing it to a file, or whatever. 3. Call itself to traverse the node’s right subtree.

30 Traversing the Tree Java Code for Traversing
private void inOrder(Node localRoot){ if(localRoot != null) { inOrder(localRoot.leftChild); System.out.print(localRoot.iData + “ ”);// visiting node inOrder(localRoot.rightChild); } This method is initially called with the root as an argument: inOrder(root);

31 Traversing a Three-Node Tree

32 Traversing the Tree * A + B C Preorder and Postorder Traversals
These traversals are indeed useful if you’re writing programs that parse or analyze algebraic expressions. * A + Infix: A*(B+C) Prefix: *A+BC Postfix: ABC+* B C

33 Traversing the Tree Here’s the sequence for a preorder() method:
1. Visit the node. 2. Call itself to traverse the node’s left subtree. 3. Call itself to traverse the node’s right subtree Traversing the tree shown in Figure 8.11 using preorder would generate the expression *A+BC

34 Traversing the Tree The third kind of traversal, postorder, contains the three steps arranged in yet another way: 1. Call itself to traverse the node’s left subtree. 2. Call itself to traverse the node’s right subtree. 3. Visit the node. For the tree in Figure 8.11, visiting the nodes with a postorder traversal would generate the expression ABC+*

35 Finding Maximum and Minimum Values
The minimum 63 47 71 53 22 67 50 60 11 33 17 49 51

36 Finding Maximum and Minimum Values
public Node minimum() // returns node with minimum key value { Node current, last; current = root; // start at root while(current != null) // until the bottom, last = current; // remember node current = current.leftChild; // go to left child } return last; How to find the maximum value in the tree？ For the maximum value in the tree, follow the same procedure, but go from right child to right child until you find a node with no right child.

37 Deleting a Node How many cases should we consider? 10 5 3 7 10 5 7 10
… Leaf 10 5 7 … One child 10 3 5 7 … Two children

38 Deleting a Node Case 1: The Node to Be Deleted Has No Children
To delete a leaf node, you simply change the appropriate child field in the node’s parent to point to null. 10 10 5 5 null 3 7 3 7 a) Before deletion b) After deletion

39 Deleting a Node Using the Workshop Applet to Delete a Node with No Children Java Code to Delete a Node with No Children public boolean delete(int key) // delete node with given key { // (assumes non-empty list) Node current = root; Node parent = root; // finding… // … // delete it }

40 -如果找到要删除的结点，返回其parent以及isLeftChild标志；
Node current = root; Node parent = root; boolean isLeftChild = true; while(current.iData != key) {// search for node parent = current; if(key < current.iData) {// go left? isLeftChild = true; current = current.leftChild; } else{ // or go right? isLeftChild = false; current = current.rightChild; if(current == null) // end of the line, return false; // didn’t find it } // end while Java Code to find key 目的： -如果找到要删除的结点，返回其parent以及isLeftChild标志； -否则返回false

41 Java Code to delete if(current.leftChild==null && current.rightChild==null) { if(current == root) // if root, root = null; // tree is empty else if(isLeftChild) parent.leftChild = null; // disconnect else // from parent parent.rightChild = null; }

42 Deleting a Node Case 2: The Node to Be Deleted Has One Child
No matter how complicated this subtree is, it’s simply moved up and plugged in as the new child of the deleted node’s parent. 不论以此节点为根的substree有多复杂，只要将其孩子（包括子树）上移一层，作为被删节点父节点的新孩子即可。 80 52 48 71 67 63 62 … … … …

43 Java Code to Delete a Node with One Child
// delete() continued... // if no right child, replace with left subtree else if(current.rightChild==null) if(current == root) root = current.leftChild; else if(isLeftChild) // left child of parent parent.leftChild = current.leftChild; else // right child of parent parent.rightChild = current.leftChild; // if no left child, replace with right subtree else if(current.leftChild==null) if(current == root) root = current.rightChild; else if(isLeftChild) // left child of parent parent.leftChild = current.rightChild; else // right child of parent parent.rightChild = current.rightChild; // continued...

44 Now the fun begins. Case 3: The Node to Be Deleted Has Two Children
If the deleted node has two children, you can’t just replace it with one of these children, at least if the child has its own children. Why not? Which node goes here? 80 80 35 25 30 15 35 15 40 5 20 30 40 5 20 a) Before deletion b) After deletion Cannot replace with subtree.

45 Deleting a Node ? ? ? ? Node replaced by its successor. 80 25 15 35 5
谁来继承已故皇帝的大位呀? 15 35 ? ? 5 20 30 40 Successor to 25 ? ?

46 To find successor of this node
Deleting a Node Finding the Successor To find successor of this node 38 26 72 55 90 What we’re really looking for is the smallest of the set of nodes that are larger than the original node. Successor 41 60 78 92 No left child 49 74

47 Deleting a Node Using the Workshop Applet to Delete a Node with Two Children Java Code to Find the Successor Code for a method getSuccessor(), which returns the successor of the node specified as its delNode argument. Fact about successor 一定没有左孩子； 如果不是被删节点的孩子，就一定是某个节点的左孩子.

48 private Node getSuccessor(Node delNode){
Node successorParent = delNode; Node successor = delNode; Node current = delNode.rightChild; // go to right child while(current != null) {// until no more left children, successorParent = successor; successor = current; current = current.leftChild; // go to left child } if(successor!=delNode.rightChild) {//if successor not //right child, make connections successorParent.leftChild=successor.rightChild;//原地善后 successor.rightChild = delNode.rightChild;//新领导组阁 return successor;

49 Deleting a Node Successor Is Right Child of delNode
We can simply move the subtree of which successor is the root and plug it in where the deleted node was. This operation requires only two steps: . 1. Unplug current from the rightChild field of its parent (or leftChild field if appropriate), and set this field to point to successor. 2. Unplug current’s left child from current, and plug it into the leftChild field of successor 1. parent.rightChild = successor; 2. successor.leftChild = current.leftChild;

50 Deleting a Node

51 // delete() continued else // two children, so replace with inorder successor { // get successor of node to delete (current) Node successor = getSuccessor(current); // connect parent of current to successor instead if(current == root) root = successor; else if(isLeftChild) parent.leftChild = successor; else parent.rightChild = successor; // connect successor to current’s left child successor.leftChild = current.leftChild; } // end else two children // (successor cannot have a left child) return true; } // end delete()

52 Deleting a Node Q：需要修改谁、改为什么？修改的次序？
Successor Is Left Descendant of Right Child of delNode 总结：Four steps are required to perform the deletion 1.把successor父结点的IeftChild字段置为successor的右子结点。 2.把successor的rightChild字段置为要删除结点的右子结点。 3.把current从它父结点的rightChild字段移除，把这个字段置为successor. 4.把current的左子结点从current移除，successor的leftChild字段置为current的左子结点. 要点：第1步和第2步由getSuccessor()方法完成，第3步和第4步由delete()方法完成。 Q：需要修改谁、改为什么？修改的次序？

53 Deleting a Node 1.把successor父结点的IeftChild字段置为successor的右子结点。
2.把successor的rightChild字段置为要删除结点的右子结点。 3.把current从它父结点的rightChild字段移除，把这个字段置为successor. 4.把current的左子结点从current移除，successor的leftChild字段置为current的左子结点.

54 Deleting a Node Here’s the code for these four steps
1. successorParent.leftChild = successor.rightChild; 2. successor.rightChild = delNode.rightChild; 3. parent.rightChild = successor;(or parent.leftChild = successor;) 4. successor.leftChild = current.leftChild;

55 Deleting a Node Is Deletion Necessary?
Deletion操作是如此的复杂，一些程序员都尝试着避开它。他们在node类中加了一个boolean的字段，名为isDeleted。要删除一个结点时，就把此结点的这个字段置为true。其他操作，像find()，在查找之前先判断这个结点是不是标志为“已删除”。 这样，删除的结点不会改变树的结构。当然，这样做存储中还保留着这种“己经删除”的结点。

56 The Efficiency of Binary Trees
操作的花费的时间取决于树的level多少. N ≤ 2L – 1 L ≥ log2(N + 1)

57 多叉树的应用 XML XML 是可扩展标记语言（Extensible Markup Language）的缩写，其中的 标记（markup）是关键部分。您可以创建内容，然后使用限定标记标记它，从而使每个单词、短语或块成为可识别、可分类的信息。您创建的文件，或文档实例 由元素（标记）和内容构成。 示例 <?xml version="1.0" encoding="UTF-8"?> <recipe> <recipename>Ice Cream Sundae</recipename> <preptime>5 minutes</preptime> </recipe> 数据结构？

58 多叉树的应用 XML文档的常见操作 Java的XML文件操作 查询 修改 删除 插入 Dom4J
package com.test.xml;import java.io.File; import java.io.FileWriter; import java.io.IOException; import java.io.Writer; import java.util.List;import org.dom4j.Attribute; import org.dom4j.Document; import org.dom4j.DocumentException; import org.dom4j.DocumentHelper; import org.dom4j.Element; import org.dom4j.io.OutputFormat; import org.dom4j.io.SAXReader; import org.dom4j.io.XMLWriter; public class Dom4jDemo implements XmlDocument {   public void createXml(String fileName) {   //创建文档对象   Document document = DocumentHelper.createDocument();   //添加元素，第一个元素为根元素   Element employees = document.addElement("employees");   //在根元素下添加其它元素   Element employee = employees.addElement("employee");   //为元素添加数据(第一个参数为属性名称，第二个参数为属性值)   employee.addAttribute("dept", "sale");      Element name = employee.addElement("name");   //设置该元素的文本值   name.setText("andrew");      Element sex = employee.addElement("sex");   sex.setText("m");      Element age = employee.addElement("age");   age.setText("29");      try {    //创建写XML文档的Writer对象    Writer fileWriter = new FileWriter(fileName);    //创建美化文档的format对象，如果没有这个对象，生成的XML文档的元素不会换行，不太美观    OutputFormat format = OutputFormat.createPrettyPrint();       XMLWriter xmlWriter = new XMLWriter(fileWriter, format);    xmlWriter.write(document);    xmlWriter.close();   } catch (IOException e) {    e.printStackTrace();   }  }   public void parserXml(String fileName) {   File inputXml = new File(fileName);   SAXReader saxReader = new SAXReader();   try {    Document document = saxReader.read(inputXml);    //获取文档的根元素    Element employees = document.getRootElement();        parseElement(employees);   } catch (DocumentException e) {    System.out.println(e.getMessage());   }   System.out.println("dom4j parserXml");  }      private void parseElement(Element element) {   System.out.println("元素名:" + element.getName());      //获得该元素的所有属性   List attributes = element.attributes();   for (int i = 0; i < attributes.size(); i++) {    Attribute arrribute = (Attribute)attributes.get(i);    //获得属性名    String name = arrribute.getName();    //获得属性值    String value = arrribute.getValue();    System.out.println("属性" + name + "的值:" + value);   }      //获得元素的文本的值，并且去掉空格   String text = element.getTextTrim();   if (text != null && text.length() > 0) {    System.out.println("元素的文本值:" + text);   }      //获得元素下的所有子元素，递归调用以获取子元素下的属性及元素信息   List childElements = element.elements();   for (int i = 0; i < childElements.size(); i++) {    Element childElement = (Element)childElements.get(i);    parseElement(childElement);   }  }    public static void main(String[] args) {   Dom4jDemo demo = new Dom4jDemo();   String fileName1 = Dom4jDemo.class.getResource("example.xml").getPath();   demo.parserXml(fileName1);   String fileName2 = Dom4jDemo.class.getResource("").getPath() + "example3.xml";   demo.createXml(fileName2);  }} 示例程序中解析的example.xml文件的内容如下所示： <?xml version="1.0" encoding="UTF-8"?>  <employees>   <employee id="F " groupName="Theam1">    <name oldName="zhangliang">andrew</name>    <sex>M</sex>    <age>30</age>   </employee>  </employees> 示例程序中创建的example3.xml文件的内容如下所示： <?xml version="1.0" encoding="UTF-8"?><employees>   <employee dept="sale">     <name>andrew</name>     <sex>m</sex>     <age>29</age>   </employee> </employees>

59 The Huffman Code Algorithm that uses a binary tree to compress data.
It’s called the Huffman code, after David Huffman who discovered it in 1952.

60 The Huffman Code Character Codes
Characters are represented in binary using the ASCII code. Every character takes 8 bits.

61 GAME TIME 牛郎织女的通讯方式 规则：双方各持一份码表，有两张标示分别为0,1，两边不许说话，一方举牌，一方记录。 步骤：
00001 N 01110 B 00010 O 01111 C 00011 P 10000 D 00100 Q 10001 E 00101 R 10010 F 00110 S 10011 G 00111 T 10100 H 01000 U 10101 I 01001 V 10110 J 01010 W 10111 K 01011 X 11000 L 01100 Y 11001 M 01101 Z 11010 空格 11011 牛郎织女的通讯方式 规则：双方各持一份码表，有两张标示分别为0,1，两边不许说话，一方举牌，一方记录。 步骤： 发信息的把字母翻译为0，1序列 收信息的记录下0,1序列，翻译为字母 牛郎对织女说了什么？

62 The Huffman Code A 00001 N 01110 B 00010 O 01111 C 00011 P 10000 D 00100 Q 10001 E 00101 R 10010 F 00110 S 10011 G 00111 T 10100 H 01000 U 10101 I 01001 V 10110 J 01010 W 10111 K 01011 X 11000 L 01100 Y 11001 M 01101 Z 11010 空格 11011 有很多压缩数据的方法。对文本来说，最常用的方法是减少表示最频繁出现的字符的位数（bits）。如在英语中，E是最常用的字母，所以用尽可能少的位为E编码是很合理的。反之，Z是很少用到的，所以用多些位表示也无所谓。 假设只用两位表示E，如01。那么就不能给字典中其他每个字母都用两位编码了，因为2位只有四种组合: 00, 01, 10和11。 Q：可以用这四种组合表示四个最常用的字符吗?

63 The Huffman Code 很遗憾，不可以。 在编码序列中，如果用起始位组合相同的代码表示不同的字符，这样的情况是不应该出现的。比如：
X： 那么解码是就搞不清楚 起始的01是表示E还是表示x的开始部分了。 每个代码都不能是其他代码的前缀。 规则:

64 The Huffman Code 下面就来解决这个问题:为每种信息根据其特别的信息定制新的编码。 假设要发送消息:
Something else to consider is that in some messages E might not be the most-used character. If the text is a Java source file, for example, the ; (semicolon) character might appear more often than E. 下面就来解决这个问题:为每种信息根据其特别的信息定制新的编码。 假设要发送消息: SUSIE SAYS IT IS EASY 字母S出现得最多，其次是空格。用表格来列出每种字符出现的次数。这样的表叫频率表。

65 The Huffman Code The characters with the highest counts should be coded with a small number of bits. Table 8.5 shows how we might encode the characters in the Susie message. We use 10 for S and 00 for the space. We can’t use 01 or 11 because they are prefixes for other characters.

66 The Huffman Code Decoding（解码） with the Huffman Tree

67 The Huffman Code Creating the Huffman Tree
1.为每个字符创建一个Node对象(像tree.java中的那样)。在Susie示例中有九个结点。每个结点有两个数据项:字符和字符在消息中出现的频率。表8.4中列出了Susie消息中每个字符出现的频率。 2.为这些结点创建tree对象。这些结点就是树的根。 3.把这些树都插入到一个优先级队列中(第4章中讲过)。它们按频率排序，频率最小的结点有最高的优先级。

68 The Huffman Code 接着完成下面的步骤：
1.从优先级队列中删掉两棵树，并把它们作为一个新根结点的子结点。新结点的频率是子结点频率的和;它的字符字段可以是空的。 2.把这个新的三结点树插回优先级队列里。 3.反复重复第一步和第二步。树会越变越大，队列中的数据项会越来越少。当队中只有一棵树时，它就是所建的哈夫曼树了。

69 The Huffman Code 7 5 9 A 2 I 3 sp 4 4 Y 2 E S 6 3 2 lf 1 U T 13 22

70 The Huffman Code Coding the Message 怎样建立哈夫曼编码并把它插入代码表中?
这个过程类似于对一条信息解码的过程。从哈夫曼树的根开始并顺着哈夫曼树沿每一条可能的路径到达叶结点。在顺着树往下走时，记录向左和向右的顺序，向左的边用0表示，向右的边就用1表示。到达某个叶结点后，0和1的序列就是这个字符的哈夫曼编码。把这个代码插入代码表的正确位置就可以了。 这个过程的实现可以从根开始调用一个方法，然后对它的每个子结点递归地调用方法本身。最后，所有到叶结点的路径都被遍历了，代码表也完成了。

71 一种简单的压缩文件格式 Huffman码表 编码后的 文件内容

72 Summary 树由边(直线)连接的结点(圆)组成。 根是树中最顶端的结点;它没有父结点。 二叉树中，结点最多有两个子结点。
二叉搜索树中，所有A结点左边子孙结点的关键字值都比A小;所有右边子孙结点的关键字值都大于(或等于)A。 树执行查找、插入、删除的时间复杂度都是O ( logN ) 。 结点表示保存在树中的数据对象。 程序中通常用结点到子结点的引用来表示边(有时也用到结点的父结点的引用)。 遍历树是按某种顺序访问树中所有的结点。 最简单的遍历方法是前序、中序和后序。 非平衡树是指根左边的后代比右边多，或者相反，右边的后代比左边多。

73 查找结点需要比较要找的关键字值和结点的关键字值，如果要找结点关键值小就转向那个结点的左子结点，如果大就转向右子结点。
插入需要找到要插入新结点的位置并改变它父结点的子字段来指向它。 中序遍历按照关键值的升序访问结点。 前序和后序遍历对解析代数表达式是有用的。 如果一个结点没有子结点，删除它只要把它的父结点的子字段置为null即可。 如果一个结点有一个子结点，把它父结点的子字段置为它的子结点就可以删除它。 如果一个结点有两个子结点，删除它要用它的后继来代替它。

74 A结点的后继是以A的右子结点为根的子树中关键值最小的那个结点。
删除操作中，如果结点有两个子结点，要分后继的两种情况考虑：（1）后继是被删结点的右子结点（2）后继是被删结点右子结点的左子孙。 数组中重复关键字值的结点会产生一些问题，因为只有第一个能被查找到。 在计算机存储时可以用数组表示树，不过基于引用的方法更常用。 哈夫曼树是二叉树(但不是二叉搜索树)，用于数据压缩算法，这种方法称为哈夫曼编码。 哈夫曼编码中，最经常出现的字符的编码位数最少，很少出现的字符编码位数要多一些。

75 The End