数据结构与算法04 之二叉树

   在有序数组中，可以快速找到特定的值，但是想在有序数组中插入一个新的数据项，就必须首先找出新数据项插入的位置，然后将比新数据项大的数据项向后移动一位，来给新的数据项腾出空间，删除同理，这样移动很费时。显而易见，如果要做很多的插入和删除操作和删除操作，就不该选用有序数组。

        另一方面，链表中可以快速添加和删除某个数据项，但是在链表中查找数据项可不容易，必须从头开始访问链表的每一个数据项，直到找到该数据项为止，这个过程很慢。

        树这种数据结构，既能像链表那样快速的插入和删除，又能想有序数组那样快速查找。这里主要实现一种特殊的树——二叉（搜索）树。二叉搜索树有如下特点：一个节点的左子节点的关键字值小于这个节点，右子节点的关键字值大于或等于这个节点。插入一个节点需要根据这个规则进行插入。

        删除节点时二叉搜索树中最复杂的操作，但是删除节点在很多树的应用中又非常重要，所以详细研究并总结下特点。删除节点要从查找要删的节点开始入手，首先找到节点，这个要删除的节点可能有三种情况需要考虑：

         ·该节点是叶节点，没有子节点

         ·该节点有一个子节点

         ·该节点有两个子节点

         第一种最简单，第二种也还是比较简单的，第三种就相当复杂了。下面分析这三种删除情况：

        要删除叶节点，只需要改变该节点的父节点对应子字段的值即可，由指向该节点改为null就可以了。垃圾回收器会自动回收叶节点，不需要自己手动删掉；当节点有一个子节点时，这个节点只有两个连接：连向父节点和连向它唯一的子节点。需要从这个序列中剪断这个节点，把它的子节点直接连到它的父节点上即可，这个过程要求改变父节点适当的引用（左子节点还是右子节点），指向要删除节点的子节点即可；第三种情况最复杂，如果要删除有两个子节点的节点，就不能只用它的一个子节点代替它，比如要删除节点25，如果用35取代它，那35的左子节点是15呢还是30？

        因此需要考虑另一种方法，寻找它的中序后继来代替该节点。下图显示的就是要删除节点用它的后继代替它的情况，删除后还是有序的。（这里还有更麻烦的情况，即它的后继自己也有右子节点，下面再讨论。）

        那么如何找后继节点呢？首先得找到要删除的节点的右子节点，它的关键字值一定比待删除节点的大。然后转到待删除节点右子节点的左子节点那里（如果有的话），然后到这个左子节点的左子节点，以此类推，顺着左子节点的路径一直向下找，这个路径上的最后一个左子节点就是待删除节点的后继。如果待删除节点的右子节点没有左子节点，那么这个右子节点本身就是后继。寻找后继的示意图如下：

        找到了后继节点，现在开始删除了，先看第一种情况，后继节点是delNode右子节点的做后代，这种情况要执行以下四个步骤：

         ·把后继父节点的leftChild字段置为后继的右子节点；

         ·把后继的rightChild字段置为要删除节点的右子节点；

         ·把待删除节点从它父节点的leftChild或rightChild字段删除，把这个字段置为后继；

         ·把待删除的左子节点移除，将后继的leftChild字段置为待删除节点的左子节点。

        如下图所示：

        如果后继节点就是待删除节点的右子节点，这种情况就简单了，因为只需要把后继为跟的子树移到删除的节点的位置即可。如下图所示：

        看到这里，就会发现删除时相当棘手的操作。实际上，因为它非常复杂，一些程序员都尝试着躲开它，他们在Node类中加了一个Boolean字段来标识该节点是否已经被删除，在其他操作之前会先判断这个节点是不是已经删除了，这样删除节点不会改变树的结构，。当然树中还保留着这种已经删除的节点，对存储造成浪费，但是如果没有那么多删除的话，这也不失为一个好方法。下面是二叉搜索树的主要代码：

[java] view plain copy

1. public class BinaryTree {  
2.     private BNode root; //根节点  
3.       
4.     public BinaryTree() {  
5.         root = null;  
6.     }  
7.       
8.     //二叉搜索树查找的时间复杂度为O(logN)  
9.     public BNode find(int key) { //find node with given key  
10.         BNode current = root;  
11.         while(current.key != key) {  
12.             if(key < current.key) {  
13.                 current = current.leftChild;  
14.             }  
15.             else {  
16.                 current = current.rightChild;  
17.             }  
18.             if(current == null) {  
19.                 return null;  
20.             }  
21.         }  
22.         return current;  
23.     }  
24.       
25.     //插入节点  
26.     public void insert(int key, double value) {  
27.         BNode newNode = new BNode();  
28.         newNode.key = key;  
29.         newNode.data = value;  
30.         if(root == null) { //if tree is null  
31.             root = newNode;  
32.         }  
33.         else {  
34.             BNode current = root;  
35.             BNode parent;  
36.             while(true) {  
37.                 parent = current;  
38.                 if(key < current.data) { //turn left  
39.                     current = current.leftChild;  
40.                     if(current == null) {  
41.                         parent.leftChild = newNode;  
42.                         newNode.parent = parent;  
43.                         return;  
44.                     }  
45.                 }  
46.                 else { //turn right  
47.                     current = current.rightChild;  
48.                     if(current == null) {  
49.                         parent.rightChild = newNode;  
50.                         newNode.parent = parent;  
51.                         return;  
52.                     }  
53.                 }  
54.             }  
55.         }  
56.     }  
57.       
58.     //遍历二叉树  
59.     public void traverse(int traverseType) {  
60.         switch(traverseType)  
61.         {  
62.         case 1: System.out.println("Preorder traversal:");  
63.                 preOrder(root);//前向遍历  
64.                 break;  
65.         case 2: System.out.println("Inorder traversal:");  
66.                 inOrder(root);//中向遍历  
67.                 break;  
68.         case 3: System.out.println("Postorder traversal:");  
69.                 postOrder(root);//后向遍历  
70.                 break;  
71.         default: System.out.println("Inorder traversal:");  
72.                 inOrder(root);  
73.                 break;  
74.         }  
75.         System.out.println("");  
76.     }  
77.       
78.     //前向遍历  
79.     private void preOrder(BNode localRoot) {  
80.         if(localRoot != null) {  
81.             System.out.print(localRoot.data + " ");  
82.             preOrder(localRoot.leftChild);  
83.             preOrder(localRoot.rightChild);  
84.         }  
85.     }  
86.       
87.     //中向遍历  
88.     private void inOrder(BNode localRoot) {  
89.         if(localRoot != null) {  
90.             inOrder(localRoot.leftChild);  
91.             System.out.print(localRoot.data + " ");  
92.             inOrder(localRoot.rightChild);  
93.         }  
94.     }  
95.       
96.     //后向遍历  
97.     private void postOrder(BNode localRoot) {  
98.         if(localRoot != null) {  
99.             postOrder(localRoot.leftChild);  
100.             postOrder(localRoot.rightChild);  
101.             System.out.print(localRoot.data + " ");  
102.         }  
103.     }  
104.       
105.     //查找最小值  
106.     /*根据二叉搜索树的存储规则，最小值应该是左边那个没有子节点的那个节点*/  
107.     public BNode minNumber() {  
108.         BNode current = root;  
109.         BNode parent = root;  
110.         while(current != null) {  
111.             parent = current;  
112.             current = current.leftChild;  
113.         }     
114.         return parent;  
115.     }  
116.       
117.     //查找最大值  
118.     /*根据二叉搜索树的存储规则，最大值应该是右边那个没有子节点的那个节点*/  
119.     public BNode maxNumber() {  
120.         BNode current = root;  
121.         BNode parent = root;  
122.         while(current != null) {  
123.             parent = current;  
124.             current = current.rightChild;  
125.         }     
126.         return parent;  
127.     }  
128.       
129.     //删除节点  
130.     /* 
131.      * 删除节点在二叉树中是最复杂的，主要有三种情况： 
132.      * 1. 该节点没有子节点（简单） 
133.      * 2. 该节点有一个子节点（还行） 
134.      * 3. 该节点有两个子节点（复杂） 
135.      * 删除节点的时间复杂度为O(logN) 
136.      */  
137.     public boolean delete(int key) {  
138.         BNode current = root;  
139. //      BNode parent = root;  
140.         boolean isLeftChild = true;  
141.           
142.         if(current == null) {  
143.             return false;  
144.         }  
145.         //寻找要删除的节点  
146.         while(current.data != key) {  
147. //          parent = current;  
148.             if(key < current.key) {  
149.                 isLeftChild = true;  
150.                 current = current.leftChild;  
151.             }  
152.             else {  
153.                 isLeftChild = false;  
154.                 current = current.rightChild;  
155.             }  
156.             if(current == null) {  
157.                 return false;  
158.             }  
159.         }  
160.           
161.         //找到了要删除的节点，下面开始删除  
162.         //1. 要删除的节点没有子节点,直接将其父节点的左子节点或者右子节点赋为null即可  
163.         if(current.leftChild == null && current.rightChild == null) {  
164.             return deleteNoChild(current, isLeftChild);  
165.         }  
166.           
167.         //3. 要删除的节点有两个子节点  
168.         else if(current.leftChild != null && current.rightChild != null) {  
169.             return deleteTwoChild(current, isLeftChild);  
170.         }  
171.           
172.         //2. 要删除的节点有一个子节点，直接将其砍断，将其子节点与其父节点连起来即可，要考虑特殊情况就是删除根节点，因为根节点没有父节点  
173.         else {  
174.             return deleteOneChild(current, isLeftChild);  
175.         }  
176.           
177.     }  
178.       
179.     public boolean deleteNoChild(BNode node, boolean isLeftChild) {  
180.         if(node == root) {  
181.             root = null;  
182.             return true;  
183.         }  
184.         if(isLeftChild) {  
185.             node.parent.leftChild = null;  
186.         }  
187.         else {  
188.             node.parent.rightChild = null;  
189.         }  
190.         return true;  
191.     }  
192.       
193.     public boolean deleteOneChild(BNode node, boolean isLeftChild) {  
194.         if(node.leftChild == null) {  
195.             if(node == root) {  
196.                 root = node.rightChild;  
197.                 node.parent = null;  
198.                 return true;  
199.             }  
200.             if(isLeftChild) {  
201.                 node.parent.leftChild  = node.rightChild;  
202.             }  
203.             else {  
204.                 node.parent.rightChild = node.rightChild;  
205.             }  
206.             node.rightChild.parent = node.parent;  
207.         }  
208.         else {  
209.             if(node == root) {  
210.                 root = node.leftChild;  
211.                 node.parent = null;  
212.                 return true;  
213.             }  
214.             if(isLeftChild) {  
215.                 node.parent.leftChild  = node.leftChild;  
216.             }  
217.             else {  
218.                 node.parent.rightChild = node.leftChild;  
219.             }  
220.             node.leftChild.parent = node.parent;  
221.         }  
222.         return true;  
223.     }  
224.       
225.     public boolean deleteTwoChild(BNode node, boolean isLeftChild) {  
226.         BNode successor = getSuccessor(node);  
227.         if(node == root) {  
228.             successor.leftChild = root.leftChild;  
229.             successor.rightChild = root.rightChild;  
230.             successor.parent = null;  
231.             root = successor;  
232.         }  
233.         else if(isLeftChild) {  
234.             node.parent.leftChild = successor;  
235.         }  
236.         else {  
237.             node.parent.rightChild = successor;  
238.         }  
239.         successor.leftChild = node.leftChild;//connect successor to node's left child  
240.         return true;  
241.     }  
242.       
243.     //获得要删除节点的后继节点（中序遍历的下一个节点）  
244.     public BNode getSuccessor(BNode delNode) {  
245.         BNode successor = delNode;  
246.         BNode current = delNode.rightChild;  
247.         while(current != null) {  
248.             successor = current;  
249.             current = current.leftChild;  
250.         }  
251.         if(successor != delNode.rightChild) {  
252.             successor.parent.leftChild = successor.rightChild;  
253.             if(successor.rightChild != null) {        
254.                 successor.rightChild.parent = successor.parent;//删除后续节点在原来的位置  
255.             }  
256.             successor.rightChild = delNode.rightChild;//将后续节点放到正确位置，与右边连上  
257.         }  
258.         return successor;  
259.     }  
260. }  
261.   
262. class BNode {  
263.     public int key;  
264.     public double data;  
265.     public BNode parent;  
266.     public BNode leftChild;  
267.     public BNode rightChild;  
268.       
269.     public void displayNode() {  
270.         System.out.println("{" + key + ":" + data + "}");  
271.     }  
272. }  

    二叉树就谈论到这吧，如果有错误之处，欢迎留言指正~

转载：http://blog.csdn.net/eson_15/article/details/51138663