对二叉树的一些操作求解

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

查看更多 下一篇