posts - 28,  comments - 15,  trackbacks - 0
    二叉树是数据结构世界中具有重要地位的一种数据结构。它同时具备有序数组和链表的优点,同时又弥补了有序数组插入数据、链表查找的缺点。同时也是各种面试中常见的问题。现通过java实现二叉树,加深对二叉树的理解。
    
    代码实现:
  1package com.zxl.algorithm;
  2
  3import java.util.LinkedList;
  4import java.util.List;
  5import org.apache.log4j.Logger;
  6
  7/**
  8 * 二叉树
  9 * 
 10 * @author zhangxl
 11 * @version 1.0.0
 12 * @param <E>
 13 */

 14public class BinaryTree<extends Comparable<E>>
 15{
 16    private static final Logger logger = Logger.getLogger(BinaryTree.class);
 17    
 18    private Node<E> root;
 19    
 20    public void insert(E e)
 21    {
 22        if(e == null)
 23        {
 24            throw new IllegalArgumentException("BinaryTree's data cann't be null!");
 25        }

 26        
 27        /* 不存在根节点,首先创建根节点 */
 28        if(root == null)
 29        {
 30            root = new Node<E>(null, e);
 31        }

 32        else
 33        {
 34            Node<E> current = root;
 35            Node<E> parent;
 36            while(true)
 37            {
 38                parent = current;
 39                if(e.compareTo(parent.getData()) == 0)
 40                {
 41                    throw new IllegalArgumentException("Node[" + e.toString() + "] to build has already existed!existing obj [" + parent.getData().toString() + "]");
 42                }

 43                else if(e.compareTo(parent.getData()) < 0)
 44                {
 45                    current = current.leftChild;
 46                    if(current == null)
 47                    {
 48                        Node<E> newNode = new Node<E>(parent, e);
 49                        parent.leftChild = newNode;
 50                        return;
 51                    }

 52                }

 53                else
 54                {
 55                    current = current.rightChild;
 56                    if(current == null)
 57                    {
 58                        Node<E> newNode = new Node<E>(parent, e);
 59                        parent.rightChild = newNode;
 60                        return;
 61                    }

 62                }

 63            }

 64        }

 65    }

 66    
 67    /**
 68     * 中序遍历(LDR)
 69     * 
 70     * @return
 71     */

 72    public List<E> inOrder()
 73    {
 74        List<E> list = new LinkedList<E>();
 75        inOrderTraverse(root.leftChild, list);
 76        list.add(root.data);
 77        inOrderTraverse(root.rightChild, list);
 78        
 79        return list;
 80    }

 81    
 82    private void inOrderTraverse(Node<E> node, List<E> list)
 83    {
 84        if(node != null)
 85        {
 86            inOrderTraverse(node.leftChild, list);
 87            list.add(node.data);
 88            inOrderTraverse(node.rightChild, list);
 89        }

 90    }

 91    
 92    /**
 93     * 前序遍历(DRL)
 94     * 
 95     * @return
 96     */

 97    public List<E> preOrder()
 98    {
 99        List<E> list = new LinkedList<E>();
100        if(root == null)
101        {
102            return list;
103        }

104        
105        list.add(root.data);
106        preOrderTraverse(root.leftChild, list);
107        preOrderTraverse(root.rightChild, list);
108        
109        return list;
110        
111    }

112    
113    private void preOrderTraverse(Node<E> node, List<E> list)
114    {
115        if(node != null)
116        {
117            list.add(node.getData());
118            preOrderTraverse(node.leftChild, list);
119            preOrderTraverse(node.rightChild, list);
120        }

121    }

122    
123    /**
124     * 后序遍历(LRD)
125     * 
126     * @return
127     */

128    public List<E> postOrder()
129    {
130        List<E> list = new LinkedList<E>();
131        if(root == null)
132        {
133            return list;
134        }

135        
136        postOrderTraverse(root.leftChild, list);
137        postOrderTraverse(root.rightChild, list);
138        list.add(root.getData());
139        
140        return list;
141    }

142    
143    private void postOrderTraverse(Node<E> node, List<E> list)
144    {
145        if(node != null)
146        {
147            postOrderTraverse(node.leftChild, list);
148            postOrderTraverse(node.rightChild, list);
149            list.add(node.getData());
150        }

151    }

152    
153    /**
154     * 删除节点
155     * 
156     * @param e
157     */

158    public void delete(E e)
159    {
160        if(e == null)
161        {
162            return;
163        }

164        
165        // TODO
166        
167    }

168    
169    /**
170     * 查找节点
171     * 
172     * @param e
173     * @return
174     */

175    public BinaryTree<E>.Node<E> find(E e)
176    {
177        Node<E> current = root;
178        while(e.equals(current.data))
179        {
180            if(e.compareTo(current.data) < 0)
181            {
182                current = current.leftChild;
183            }

184            else
185            {
186                current = current.rightChild;
187            }

188            
189            if(current == null)
190            {
191                return null;
192            }

193        }

194        return current;
195    }

196    
197    /**
198     * 二叉树Node节点
199     * 
200     * @author Administrator
201     * 
202     * @param <E>
203     */

204    class Node<E>
205    {
206        private Node<E> parent;
207        
208        private Node<E> leftChild;
209        
210        private Node<E> rightChild;
211        
212        private E data;
213        
214        public Node(Node<E> parent, E data)
215        {
216            this.parent = parent;
217            this.data = data;
218        }

219        
220        public Node<E> getParent()
221        {
222            return parent;
223        }

224        
225        public void setParent(Node<E> parent)
226        {
227            this.parent = parent;
228        }

229        
230        public Node<E> getLeftChild()
231        {
232            return leftChild;
233        }

234        
235        public void setLeftChild(Node<E> leftChild)
236        {
237            this.leftChild = leftChild;
238        }

239        
240        public Node<E> getRightChild()
241        {
242            return rightChild;
243        }

244        
245        public void setRightChild(Node<E> rightChild)
246        {
247            this.rightChild = rightChild;
248        }

249        
250        public E getData()
251        {
252            return data;
253        }

254        
255        public void setData(E data)
256        {
257            this.data = data;
258        }

259        
260    }

261    
262    public static void main(String args)
263    {
264        BinaryTree<Integer> bt = new BinaryTree<Integer>();
265        bt.insert(new Integer(66));
266        bt.insert(Integer.valueOf(50));
267        bt.insert(Integer.valueOf(6));
268        bt.insert(Integer.valueOf(14));
269        bt.insert(Integer.valueOf(88));
270        bt.insert(Integer.valueOf(52));
271        bt.insert(Integer.valueOf(108));
272        bt.insert(Integer.valueOf(76));
273        
274        List<Integer> list = bt.inOrder();
275        StringBuffer buffer = new StringBuffer();
276        for(int i = 0; i < list.size(); i++)
277        {
278            if(buffer.length() > 0)
279            {
280                buffer.append(",");
281            }

282            buffer.append(list.get(i));
283        }

284        
285        System.out.println("中序遍历:" + buffer.toString());
286        
287        list = bt.preOrder();
288        buffer = new StringBuffer();
289        for(int i = 0; i < list.size(); i++)
290        {
291            if(buffer.length() > 0)
292            {
293                buffer.append(",");
294            }

295            buffer.append(list.get(i));
296        }

297        
298        System.out.println("前序遍历:" + buffer.toString());
299        
300        list = bt.postOrder();
301        buffer = new StringBuffer();
302        for(int i = 0; i < list.size(); i++)
303        {
304            if(buffer.length() > 0)
305            {
306                buffer.append(",");
307            }

308            buffer.append(list.get(i));
309        }

310        
311        System.out.println("后序遍历:" + buffer.toString());
312    }

313    
314}

315

输出结果:

中序遍历:6,14,50,52,66,76,88,108
前序遍历:66,50,6,14,52,88,76,108
后序遍历:14,6,52,50,76,108,88,66

/**********************************************/
posted on 2014-04-18 18:34 zhangxl 阅读(328) 评论(0)  编辑  收藏 所属分类: arithmetics

只有注册用户登录后才能发表评论。


网站导航:
 
<2014年4月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

常用链接

留言簿(1)

随笔分类(17)

随笔档案(28)

文章分类(30)

文章档案(30)

相册

收藏夹(2)

hibernate

java基础

mysql

xml

关注

压力测试

算法

最新随笔

搜索

  •  

积分与排名

  • 积分 - 95505
  • 排名 - 602

最新评论

阅读排行榜

评论排行榜