求Java BST 插入一个新节点的方法

本人Java 不是特别好，这里请教一个简单的问题，向BST(binary search tree) 插入一个新节点的方法 ，我写了一个recursive的，但是要插入的这个节点没有被插上，原树里面这个位置还是null.
原树如图，我的代码如下：

1. /* Insert a node to a binary search tree*/
   
2.         public static void insertNodeBinarySearchTree(TreeNode root, TreeNode n){
   
3.                 if(root == null){
   
4.                         root = n;
   
5.                 }
   
6.                 else if(n.data >= root.data){
   
7.                         insertNodeBinarySearchTree(root.left,n);
   
8.                 }
   
9.                 else if(n.data < root.data){
   
10.                         insertNodeBinarySearchTree(root.right,n);
    
11.                 }
    
12.         }

复制代码

在main 函数里调用的时候：

1. insertNodeBinarySearchTree(t8,t6);

复制代码

t1-t12 代表节点1到12，这里我想插入节点6（t6）,t8为root 节点，按照BST的特性应该被插在t4的左支（这个树本身不是BST，只是我找的一个测试例子），但是这样做没有效果，后来我把代码改成了：

1. /* Insert a node to a binary search tree*/
   
2.         public static void insertNodeBinarySearchTree(TreeNode left, TreeNode right,TreeNode root, TreeNode n){
   
3.                 if(root == null){
   
4.                         if(left!=null){
   
5.                                 left.left = n;
   
6.                         }
   
7.                         if(right!=null){
   
8.                                 right.right = n;
   
9.                         }
   
10.                         root = n;
    
11.                 }
    
12.                 else if(n.data >= root.data){
    
13.                         insertNodeBinarySearchTree(root,null,root.left,n);
    
14.                 }
    
15.                 else if(n.data < root.data){
    
16.                         insertNodeBinarySearchTree(null,root,root.right,n);
    
17.                 }
    
18.         }

复制代码

调用时：

1. insertNodeBinarySearchTree(null,null,t8,t6);

复制代码

这样就可以了，但是我不知道问什么第一种方法不行呢？我觉得可能是节点4的左支没有被我成功赋值，那么应该如何改进呢？虚心求教

是我对BST理解有问题吗？怎么这里的代码都是n.val>root.val之后往左插呢？

应该是下面这个这样的呀。还有，Java没有pass by reference,只有pass by value，所以你pass进去的root,你绝对改不了它的reference(address)的。要不就用global variable,要不就像我这样，返回新的root.

        public static TreeNode insertNode(TreeNode root,TreeNode node)
        {
                if(root==null) return node;
                else if(node.val<root.val)
                {
                        if(root.left==null)
                        {
                                root.left=node;
                        }
                        else insertNode(root.left,node);
                }
                else
                {
                        if(root.right==null)
                        {
                                root.right=node;
                        }
                        else insertNode(root.right,node);
                }
                return root;
        }

求加大米

第一种方法不对

应该改成这样：

1. public static TreeNode insertNodeBinarySearchTree(TreeNode root, TreeNode n){
   
2.         if(root == null){
   
3.             return n;
   
4.         }
   
5.         else if(n.data >= root.data){
   
6.             root.left = insertNodeBinarySearchTree(root.left, n);
   
7.         }
   
8.         else if(n.data < root.data){
   
9.             root.right = insertNodeBinarySearchTree(root.right, n);
   
10.         }
    
11.     }

复制代码

话说楼主给的例子不是一个BST吧，12怎么会插在左子树里头，而且n.data >= root.data是不是应该往右子树插呢？

非CS科班出身。。。楼主看看这个能跑不

/* Insert a node to a binary search tree*/
        public static void insertNodeBinarySearchTree(TreeNode root, TreeNode n){                if (root == null){
                    root = n;
                    return;
                }
                if(n.data >= root.data){
                    if (root.left == null)
                        root.left = n
                    else
                        insertNodeBinarySearchTree(root.left,n);
                }
                else if(n.data < root.data){
                    if (root.right == null)
                        root.right = n
                    else
                        insertNodeBinarySearchTree(root.right,n);
                }
        }

第一个code参数声明的是两个去为啥递归的时候是四个？

flyaway25 发表于 2014-12-29 10:58
第一个code参数声明的是两个去为啥递归的时候是四个？

不好意思刚才代码粘错了，现在改过来了

通俗点就是，第一种写法只告诉root它的是值是多少，但没有告诉它的parent（也就是node 4)这个node的存在。第二种写法就明确告诉它的parent新插进去的值是什么了(via left/right.left = n;)

犬座 发表于 2014-12-29 11:34
通俗点就是，第一种写法只告诉root它的是值是多少，但没有告诉它的parent（也就是node 4)这个node的存在。 ...

那么有没有更好地方法呢？第二种四个参数有点复杂

圆梦梦剧场 发表于 2014-12-29 11:45
求加大米

第一种方法不对

谢谢，这种方法很好，但就是不太容易想出来，有点绕。。。可能要么好想出来但是不好用，要么好用但是不好想出来吧

LZ 没有理解PASS BY REFERENCE

你这里ROOT 只是COPY了一个 Parent.Left的reference 到栈上, 其实就是null

root = n; 只是让栈上面root这个reference指向了n  Parent.Left 没有任何改变

wcyz666 发表于 2014-12-29 23:42
话说楼主给的例子不是一个BST吧，12怎么会插在左子树里头，而且n.data >= root.data是不是应该往右子树插呢 ...

这个树本身不是BST，我上面说了，只是一个我找来测试这个算法的数，而且我要插得是6不是12，我给的图是没有插入之前的树