二分搜索树add的非递归实现
来源：6-3 向二分搜索树中添加元素
沉迷Cpp的web
2018-08-03
老师，我写了二分搜索树的非递归实现，我感觉我逻辑上没有问题，但是进行toString输出的时候并没有输出完整的一棵树，您可以看看是什么原因吗？
public void add(E e)
{//添加元素的非递归写法
//当这棵树为空的时候
if (root == null) {
size++;
root = new Node(e);
return ;
}
Node cur = root;
while(cur!=null)
{
if (e.compareTo(cur.e) > 0) {
cur = cur.right;
}
else if (e.compareTo(cur.e) < 0) {
cur = cur.left;
}
}
if (cur==null) {
cur = new Node(e);
size++;
return;
}
}写回答
2回答
-
cur是一个局部变量。你让cur等于新的节点，但return以后，cur这个局部变量就消失了。新的节点并没有挂接到二叉树上：）
回忆一下链表中的非递归添加节点，我们必须找到待添加元素之前的节点pre，让pre->next是新的节点，才能将新的节点挂接在链表上：）
012018-08-03 -
沉迷Cpp的web
提问者
2018-08-03
这是我修改调试过的代码 public void add(E e) {//添加元素的非递归写法 //当这棵树为空的时候 if (root == null) { size++; root = new Node(e); return ; } Node cur = root; Node prev = root; while(cur!=null) { if (e.compareTo(cur.e) > 0) { prev = cur; cur = cur.right; if (cur==null) { cur = new Node(e); prev.right = cur; size++; return; } } else if (e.compareTo(cur.e) < 0) { prev = cur; cur = cur.left; if (cur==null) { cur = new Node(e); prev.left = cur; size++; return; } } } }012019-08-15
相似问题