删除任意节点的非递归代码,请老师帮忙评价一下
来源: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回答
-
赞实践!简单看来,有两个小地方可以优化。
首先,在你的代码的第一部分,你试图找到待删除的节点。但是整个代码假设待删除的节点在二叉树中。不过如果待删除的结点不在二叉树中,你的这个代码就有一些问题了:)应该有一个逻辑,如果待删除节点不在二叉树中,对这棵二叉树不需要做任何操作,直接返回NULL就好了:)
另外,你使用了栈来记录搜索这个待删除节点的路径,但是,你可以看到,在下面的具体删除过程中,你只需要使用这个stack的栈顶节点 stacknode.top(),所以,其实你可以使用一个Node* preNode或者叫parentNode来记录搜索过程中待删除节点的父节点就可以了:)
再次赞实践精神!加油:)
112017-04-08
相似问题