一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 953|回复: 11
收起左侧

[树/链表/图] 求Java BST 插入一个新节点的方法

[复制链接] |试试Instant~ |关注本帖
oldman09 发表于 2014-12-29 10:47:13 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 oldman09 于 2014-12-29 11:14 编辑

本人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的左支没有被我成功赋值,那么应该如何改进呢?虚心求教

tree

tree
你不知道这个id 发表于 2015-1-8 14:38:49 | 显示全部楼层
是我对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 反对 0

使用道具 举报

圆梦梦剧场 发表于 2014-12-29 11:45:28 | 显示全部楼层
本帖最后由 圆梦梦剧场 于 2014-12-29 11:49 编辑

求加大米

第一种方法不对

应该改成这样:
  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.     }
复制代码

评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

flyaway25 发表于 2014-12-29 10:58:14 | 显示全部楼层
第一个code参数声明的是两个去为啥递归的时候是四个?
回复 支持 反对

使用道具 举报

 楼主| oldman09 发表于 2014-12-29 11:14:36 | 显示全部楼层
flyaway25 发表于 2014-12-29 10:58
第一个code参数声明的是两个去为啥递归的时候是四个?

不好意思刚才代码粘错了,现在改过来了
回复 支持 反对

使用道具 举报

犬座 发表于 2014-12-29 11:34:51 | 显示全部楼层
通俗点就是,第一种写法只告诉root它的是值是多少,但没有告诉它的parent(也就是node 4)这个node的存在。第二种写法就明确告诉它的parent新插进去的值是什么了(via left/right.left = n;)
回复 支持 反对

使用道具 举报

 楼主| oldman09 发表于 2014-12-29 11:46:15 | 显示全部楼层
犬座 发表于 2014-12-29 11:34
通俗点就是,第一种写法只告诉root它的是值是多少,但没有告诉它的parent(也就是node 4)这个node的存在。 ...

那么有没有更好地方法呢?第二种四个参数有点复杂
回复 支持 反对

使用道具 举报

 楼主| oldman09 发表于 2014-12-29 11:58:24 | 显示全部楼层
圆梦梦剧场 发表于 2014-12-29 11:45
求加大米

第一种方法不对

谢谢,这种方法很好,但就是不太容易想出来,有点绕。。。可能要么好想出来但是不好用,要么好用但是不好想出来吧
回复 支持 反对

使用道具 举报

狂暴CNM地 发表于 2014-12-29 12:12:01 | 显示全部楼层
LZ 没有理解PASS BY REFERENCE

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

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

wcyz666 发表于 2014-12-29 23:42:09 | 显示全部楼层
本帖最后由 wcyz666 于 2014-12-29 23:44 编辑

话说楼主给的例子不是一个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);
                }
        }
回复 支持 反对

使用道具 举报

 楼主| oldman09 发表于 2014-12-30 00:22:33 | 显示全部楼层
wcyz666 发表于 2014-12-29 23:42
话说楼主给的例子不是一个BST吧,12怎么会插在左子树里头,而且n.data >= root.data是不是应该往右子树插呢 ...

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

使用道具 举报

guojiaqi1027 发表于 2014-12-30 17:20:54 | 显示全部楼层
root=n的时候root已经指向别的地方了 reference变了
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 08:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表