对二叉树的一些操作求解.
1.非递归后序遍历二叉树
Java code
// 后序遍历非递归
public static void PostOrder2(BinTree t) {
Stack<BinTree> s = new Stack<BinTree>();
Stack<Integer> s2 = new Stack<Integer>();
Integer i = new Integer(1);
while (t != null || !s.empty()) {
while (t != null) {
s.push(t);
s2.push(new Integer(0));
t = t.lchild;
}
while (!s.empty() && s2.peek().equals(i)) {
s2.pop();
System.out.print(s.pop().date);
}
if (!s.empty()) {
s2.pop();
s2.push(new Integer(1));
t = s.peek();
t = t.rchild;
}
}
}
前序中序非递归我都能理解 后续中多加了一个标志栈
不是很清楚这个算法的具体过程 求详细解释
2.求二叉树中最长的路径
意思就是根节点到某个叶子节点的路径最长 输出这个路径
3.求某个节点(值等于value的节点)的深度(层次数)
最好能告诉我具体的算法思路
------解决方案--------------------2,3用递归可以么
2,返回每棵子树的最长路径,将左右对比取大的那个
3,每递进一层就把计数加一
------解决方案--------------------
第2、3,都可以采用二叉树遍历完成,用深度优先遍历。
第一题嘛……简单说,就是为了表示该节点的右子树是否全部遍历完毕。如果没有,则为0,如果已遍历完,则置1,然后才输出这个节点的值。这就是后序遍历的意思。
------解决方案--------------------
Stack<Integer> s2 是个标志位
=0 表示S里 (s = Stack<BinTree>)压了一个bintree, 当前要打印的是 左子树
=1 表示S里压的是一个bintree, 当前 左子树已经打印了,所以现在应该打印 中节点 然后遍历右子树