二分搜索树add的非递归实现

Question

老师，我写了二分搜索树的非递归实现，我感觉我逻辑上没有问题，但是进行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;
		}
		
}

Answer 1

liuyubobobo 2018-08-03 10:52:57

cur是一个局部变量。你让cur等于新的节点，但return以后，cur这个局部变量就消失了。新的节点并没有挂接到二叉树上：）

回忆一下链表中的非递归添加节点，我们必须找到待添加元素之前的节点pre，让pre->next是新的节点，才能将新的节点挂接在链表上：）

• 提问者 沉迷Cpp的web #1

  好的老师，我明白了，谢谢老师

Answer 2

提问者 沉迷Cpp的web 2018-08-03 11:21:49

这是我修改调试过的代码
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;
				}
			}
		}
		
	}

• _潇潇暮雨 #1

  你这个代码有问题，插入一个BST中已经存在的元素会进入死循环