UC知道求普通树的非递归后续遍历算法
来源：百度知道 编辑：UC知道 时间：2024/06/20 07:41:24
回答时请注意:
1.据我所知,实现该功能 核心部分不会超过10行代码. 所以哪些复制粘贴的长篇大论的答案可以免了.
2. 如果google, baidu , csdn 能搜到现成的答案,我就不会到这来提问了,所以回答些什么"这问题很简单." 或是"google, baidu上一大把"的回答,或是任何对本问题无帮助的回答可以免了.
3. 我想能回答该问题的人,至少是个了解数据结构的懂编程的人,所以回答时,请力求简洁扼要, 更不要说: 你就改用递归实现,或是任何更改我提出条件的要求. 搞技术的人都有点偏执的,我想要的就是这个问题的答案.
我举个例子.
为了让大家更好的回答 ,我举个前序遍历普通树的算法例子:
stack--栈
node--树结点
root--根结点
//前序遍历
node = root;
stack.push(root);
System.out.println("这里是访问结点的代码");
node[] childs; //临时存放某结点的所有孩子
for(int i=childs.length-1;i>=0;i--){ //逆序进栈是为了顺序出栈
stack.push(childs[i]);
}
大家可以看到,前序遍历核心遍历部分只用了7行代码. 请大家按上面的样式写出后续遍历的算法.
不好意思,刚写哪段代码时,写漏了一个外层循环,为了避免误导了大家,我重写一次
stack--栈
node--树结点
root--根结点
node[] childs--临时存放某结点的所有孩子
//前序遍历
node = root;
stack.push(root)
可以给node加上额外的状态信息吗？
如果可以的话，给node设定状态status,0为第一次进栈，1为已展开。
节点第一次进栈的时候，status设为0。在节点出栈的时候，如果status为0，则将status改为1，先将此节点进栈，再将其子节点进栈；如果status为1，说明其子节点已全部访问，即可访问该节点。
//////////////////////////////////////
那么，可以添加一个保存子节点数目的栈n，在孩子进栈之前将父节点再次进栈，同时将子节点数目进栈n，每次访问一个节点后将栈n顶的数字减1。当栈n顶的数字为0时，即可访问该节点，同时将n顶元素出栈。
//////////////////////////////////////
这和前序遍历不一样啊，你把子节点序列入栈的时候，就已经丢失了一部分树的结构信息，这时候如果不添加额外的信息，似乎不能把子节点序列和之前的节点区分开。从入栈时机和访问数据的时机方面我认为是不能做到后续遍历的。
我记得在学校的时候，老师教的非递归后续遍历的标准算法就是我前面说的第一种。而且，只增加一个最大长度只有树深度的int 型栈开销也不是很大阿。
////////////////////////////////////////
node = root;
stack.push(root);
while(!stack.isEmpty()){
node = stack.pop();
if (node 是叶结点){
//访问代码,stack_num栈顶元素减一
while(stack.top()==0){
stack.pop(node1)
//访问node1
stack_num.pop();
//stack_num栈顶减一
}
continue;
}
childs = node.getChilds();
stack.push(node);
for(int i=childs.length-1;i&g