大家帮忙看看这个算法的题目该怎么写啊？？？

Question

在二叉树T中，编写一个非递归程序输出该树的所有叶子结点。
在网上找了一些，都是用C写的算法，但是我C 又没有学过，所以，那些都看不太懂，大家帮忙看看能不能用Java写一下。

Answer 1

给你一个别人写的，其中preOrder2(),InOrder2(),PostOrder2()三个方法是三种非递归遍历import java.util.Stack;
import java.util.HashMap;public class BinTree {
private char date;
private BinTree lchild;
private BinTree rchild; public BinTree(char c) {
date = c;
} // 先序遍历递归
public static void preOrder(BinTree t) {
if (t == null) {
return;
}
System.out.print(t.date);
preOrder(t.lchild);
preOrder(t.rchild);
} // 中序遍历递归
public static void InOrder(BinTree t) {
if (t == null) {
return;
}
InOrder(t.lchild);
System.out.print(t.date);
InOrder(t.rchild);
} // 后序遍历递归
public static void PostOrder(BinTree t) {
if (t == null) {
return;
}
PostOrder(t.lchild);
PostOrder(t.rchild);
System.out.print(t.date);
} // 先序遍历非递归
public static void preOrder2(BinTree t) {
Stack<BinTree> s = new Stack<BinTree>();
while (t != null || !s.empty()) {
while (t != null) {
System.out.print(t.date);
s.push(t);
t = t.lchild;
}
if (!s.empty()) {
t = s.pop();
t = t.rchild;
}
}
} // 中序遍历非递归
public static void InOrder2(BinTree t) {
Stack<BinTree> s = new Stack<BinTree>();
while (t != null || !s.empty()) {
while (t != null) {
s.push(t);
t = t.lchild;
}
if (!s.empty()) {
t = s.pop();
System.out.print(t.date);
t = t.rchild;
}
}
} // 后序遍历非递归
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;
}
}
} public static void main(String[] args) {
BinTree b1 = new BinTree('a');
BinTree b2 = new BinTree('b');
BinTree b3 = new BinTree('c');
BinTree b4 = new BinTree('d');
BinTree b5 = new BinTree('e');
/**
 * a / \ b c / \ d e
 */
b1.lchild = b2;
b1.rchild = b3;
b2.lchild = b4;
b2.rchild = b5;
BinTree.preOrder(b1);
System.out.println();
BinTree.preOrder2(b1);
System.out.println();
BinTree.InOrder(b1);
System.out.println();
BinTree.InOrder2(b1);
System.out.println();
BinTree.PostOrder(b1);
System.out.println();
BinTree.PostOrder2(b1);
}
}

Answer 2

回二楼的，你的代码好像是把所有的结点都给打出来了，而不是我想要的叶子结点，我加了一句上去import java.util.Stack;
import java.util.HashMap;public class BinTree {
    private char date;
    private BinTree lchild; //左孩子
    private BinTree rchild; //右孩子    public BinTree(char c) {
        date = c;
    }    // 先序遍历非递归
    public static void preOrder(BinTree t) {
        Stack<BinTree> s = new Stack<BinTree>();
        while (t != null || !s.empty()) {
            while (t != null) {
if(t.lchild== null)
                System.out.print(t.date);
                s.push(t);
                t = t.lchild;
            }
            if (!s.empty()) {
                t = s.pop();
                t = t.rchild;
            }
        }
    }    public static void main(String[] args) {
        BinTree b1 = new BinTree('a');
        BinTree b2 = new BinTree('b');
        BinTree b3 = new BinTree('c');
        BinTree b4 = new BinTree('d');
        BinTree b5 = new BinTree('e');
        /**
         *      a 
         *    / \
         *   b   c 
         *  / \ 
         *      d   e
         */
        b1.lchild = b2;
        b1.rchild = b3;
        b2.lchild = b4;
        b2.rchild = b5;        BinTree.preOrder(b1);
        System.out.println();
    }
}

Answer 3

import java.util.Stack;
import java.util.HashMap;public class BinTree {
    private char date;
    private BinTree lchild; //左孩子
    private BinTree rchild; //右孩子    public BinTree(char c) {
        date = c;
    }    // 先序遍历非递归
    public static void preOrder(BinTree t) {
        Stack<BinTree> s = new Stack<BinTree>();
        while (t != null || !s.empty()) {
            while (t != null) {
        if(t.lchild== null && t.rchild==null)
                System.out.print(t.date);
                s.push(t);
                t = t.lchild;
            }
            if (!s.empty()) {
                t = s.pop();
                t = t.rchild;
            }
        }
    }    public static void main(String[] args) {
        BinTree b1 = new BinTree('a');
        BinTree b2 = new BinTree('b');
        BinTree b3 = new BinTree('c');
        BinTree b4 = new BinTree('d');
        BinTree b5 = new BinTree('e');
        /**
         *      a 
         *    / \
         *   b   c 
         *  / \ 
         *      d   e
         */
        b1.lchild = b2;
        b1.rchild = b3;
        b2.lchild = b4;
        b2.rchild = b5;        BinTree.preOrder(b1);
        System.out.println();
    }
}