日期:2014-05-20  浏览次数:20662 次

对二叉树的一些操作求解.
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, 当前 左子树已经打印了,所以现在应该打印 中节点 然后遍历右子树