删除任意节点的非递归代码,请老师帮忙评价一下

来源:5-8 二分搜索树节点的删除(Hubbard Deletion)

慕粉3197494

2017-04-07

	// 非递归的算法,借助了栈
			Node* removeKey2(Node* node , Key key)
			{
				stack<Node*> stacknode;

				Node* newnode = node;

				while(newnode->key != key)
				{
					stacknode.push(newnode);
					if (key < newnode->key)
					{
						newnode = newnode->left;
					}else 
					{
						newnode = newnode->right;
					}
				}

				if (newnode->left == NULL)
				{
					stacknode.top()->left = newnode->right;
					delete newnode;
					count--;
					return node;
				}else if (newnode->right == NULL)
				{
					stacknode.top()->left = newnode->left;
					delete newnode;
					count--;
					return node;
				}else
				{
					Node* sucessor = new Node(mininum(newnode->right));
					sucessor->left = newnode->left;
					sucessor->right = removeMin(newnode->right);
					stacknode.top()->left = sucessor;
					delete newnode;
					count--;
					return node;
				}
			}


写回答

1回答

liuyubobobo

2017-04-08

赞实践!简单看来,有两个小地方可以优化。


首先,在你的代码的第一部分,你试图找到待删除的节点。但是整个代码假设待删除的节点在二叉树中。不过如果待删除的结点不在二叉树中,你的这个代码就有一些问题了:)应该有一个逻辑,如果待删除节点不在二叉树中,对这棵二叉树不需要做任何操作,直接返回NULL就好了:)


另外,你使用了栈来记录搜索这个待删除节点的路径,但是,你可以看到,在下面的具体删除过程中,你只需要使用这个stack的栈顶节点 stacknode.top(),所以,其实你可以使用一个Node* preNode或者叫parentNode来记录搜索过程中待删除节点的父节点就可以了:)


再次赞实践精神!加油:)

1
1
慕粉3197494
非常感谢!谢谢老师帮我看代码
2017-04-08
共1条回复

算法与数据结构(C++版) 面试/评级的算法复习技能包

课程专为:短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

查看课程