时间:2008-06-12 14:10:48   来源:论坛整理  作者:  编辑:chinaitzhe

怎么用非递归的方式删除二叉树中值为val的节点，请给出思想即可 谢谢
网友回复:删除节点

先找到该节点
然后判定3种情况...
1:叶子
2:有2个根节点
3:有1个根节点
网友回复:但是怎么可以不用递归调用就把它做完呢
网友回复:非递归的方式寻找值为val的结点，可以用栈来实现，假如要中序遍历，则根结点先进栈，然后左结点进栈，而右结点再根结点出栈后进栈。至于删除这个结点，按照楼上说的，那本清华版的《数据结构》也讲的挺清楚的。
网友回复:什么递归?

你说的查询节点吗?
可以使用非递归找撒
这样复杂啊

递归多快的
网友回复:digu(digu)
＝＝＝＝＝＝＝＝＝
可是要删除它啊
应该怎么考虑呢
网友回复:假如值为 "val "的结点不是叶子，删除了这个结点后，它的子树(subtree)怎么办？题目中并没有指明这个二叉树的类型(BST, Full, Complete).
网友回复:所以就需要说明这个二叉树的具体类型了啊，你题意说的不清，假如是要删除元素，我猜想你哪个二叉树应该是二叉排序树(BST)，似乎再数据结构中的动态查找中讨论过这个问题。
网友回复:谢谢大家
网友回复:那么，递归删除节点的怎么做呢>?