二叉查找树

构成二叉查找树的条件

  • 任意节点的所有左子节点的值小于当前节点的值,右子节点的值大于当前节点的值;

二叉查找树节点简单定义:

 这里只定义值是一个int类型,其实有 java的Comparable,可以把这个值得类型定义为任意Comparable接口实现。

class TreeNode {
    /**
     * 二叉树的节点值
     */
    private int val;

    /**
     *  左子节点
     */
    private TreeNode left;

    /**
     * 右子节点
     */
    private TreeNode right;
}

树的基本操作:

 1 public class BinarySearchTree {
 2 
 3     /**
 4      * 树的根节点
 5      */
 6     private TreeNode root;
 7 
 8     static class TreeNode {
 9 
10         /**
11          * 数据节点的值
12          */
13         private int val;
14 
15         /**
16          * 左子节点
17          */
18         private TreeNode left;
19 
20         /**
21          * 右子节点
22          */
23         private TreeNode right;
24 
25         public TreeNode(int val) {
26             this.val = val;
27         }
28     }
29 
30     /**
31      * 插入指定的节点到树中
32      * @param value  插入的节点的值
33      * @return 插入成功,返回true,插入失败,返回false
34      */
35     public boolean add(int value) {
36         TreeNode t = root;
37         if(root == null) {
38             root = new TreeNode(value);
39             return true;
40         }
41         TreeNode parent = null;
42         while(t != null) {
43             parent = t;
44             if(value < t.val)
45                 t = t.left;
46             else if(value > t.val)
47                 t = t.right;
48             else {
49                 t.val = value;
50                 return false;
51             }
52         }
53         t = new TreeNode(value);
54         if(value < parent.val)
55             parent.left = t;
56         else
57             parent.right = t;
58         return false;
59     }
60 
61     /**
62      * 删除指定的节点
63      * @param value  删除的节点的值
64      * @return 删除成功,返回true,删除失败,返回false
65      */
66     public boolean remove(int value) {
67         //删除一个节点,首先要找到这个节点:我们先实现一个节点的查找
68         TreeNode node = find(value);
69         if(node == null)
70             return false;
71         //todo
72         return false;
73     }
74 
75     public TreeNode find(int value) {
76         //从根节点开始遍历
77         TreeNode node = root;
78         while(node != null) {
79             if(value == node.val)
80                 return node;
81             else if(value < node.val)
82                 node = node.left;
83             else
84                 node = node.right;
85         }
86         return null;
87     }

二叉树的三种遍历方式

原文地址:https://www.cnblogs.com/blentle/p/8142691.html