其中二叉樹節(jié)點類

　　/** 二叉樹節(jié)點 */

　　public class BTNode {

　　private char key;

　　private BTNode left, right;

　　public BTNode(char key) {

　　this(key, null, null);

　　}

　　public BTNode(char key, BTNode left, BTNode right) {

　　this.key = key;

　　this.left = left;

　　this.right = right;

　　}

　　public char getKey() {

　　return key;

　　}

　　填寫下面表單即可預約申請免費試聽java課程!害怕學不會?助教陪讀，隨時解惑!擔心就業(yè)?一地學習，可全國推薦就業(yè)!

　　public void setKey(char key) {

　　this.key = key;

　　}

　　public BTNode getLeft() {

　　return left;

　　}

　　public void setLeft(BTNode left) {

　　this.left = left;

　　}

　　public BTNode getRight() {

　　return right;

　　}

　　public void setRight(BTNode right) {

　　this.right = right;

　　}

　　}

　　遍歷二叉樹

　　/** 二叉樹遍歷 */

　　public class BinTree {

　　protected BTNode root;

　　public BinTree(BTNode root) {

　　this.root = root;

　　}

　　public BTNode getRoot() {

　　return root;

　　}

　　/** 構造樹 */

　　public static BTNode init() {

　　BTNode a = new BTNode('A');

　　BTNode b = new BTNode('B', null, a);

　　BTNode c = new BTNode('C');

　　BTNode d = new BTNode('D', b, c);

　　BTNode e = new BTNode('E');

　　BTNode f = new BTNode('F', e, null);

　　BTNode g = new BTNode('G', null, f);

　　BTNode h = new BTNode('H', d, g);

　　return h;// root

　　}

　　/** 訪問節(jié)點 */

　　public static void visit(BTNode p) {

　　System.out.print(p.getKey() + " ");

　　}

　　/** 遞歸實現(xiàn)前序遍歷 */

　　protected static void preorder(BTNode p) {

　　if (p != null) {

　　visit(p);

　　preorder(p.getLeft());

　　preorder(p.getRight());

　　}

　　}

　　/** 遞歸實現(xiàn)中序遍歷 */

　　protected static void inorder(BTNode p) {

　　if (p != null) {

　　inorder(p.getLeft());

　　visit(p);

　　inorder(p.getRight());

　　}

　　}

　　/** 遞歸實現(xiàn)后序遍歷 */

　　protected static void postorder(BTNode p) {

　　if (p != null) {

　　postorder(p.getLeft());

　　postorder(p.getRight());

　　visit(p);

　　}

　　}

　　/** 非遞歸實現(xiàn)前序遍歷 */

　　protected static void iterativePreorder(BTNode p) {

　　Stack stack = new Stack();

　　if (p != null) {

　　stack.push(p);

　　while (!stack.empty()) {

　　p = stack.pop();

　　visit(p);

　　if (p.getRight() != null)

　　stack.push(p.getRight());

　　if (p.getLeft() != null)

　　stack.push(p.getLeft());

　　}

　　}

　　}

　　/** 非遞歸實現(xiàn)后序遍歷 */

　　protected static void iterativePostorder(BTNode p) {

　　BTNode q = p;

　　Stack stack = new Stack();

　　while (p != null) {

　　// 左子樹入棧

　　for (; p.getLeft() != null; p = p.getLeft())

　　stack.push(p);

　　// 當前節(jié)點無右子或右子已經輸出

　　while (p != null && (p.getRight() == null || p.getRight() == q)) {

　　visit(p);

　　q = p;// 記錄上一個已輸出節(jié)點

　　if (stack.empty())

　　return;

　　p = stack.pop();

　　}

　　// 處理右子

　　stack.push(p);

　　p = p.getRight();

　　}

　　}

　　/** 非遞歸實現(xiàn)中序遍歷 */

　　protected static void iterativeInorder(BTNode p) {

　　Stack stack = new Stack();

　　while (p != null) {

　　while (p != null) {

　　if (p.getRight() != null)

　　stack.push(p.getRight());// 當前節(jié)點右子入棧

　　stack.push(p);// 當前節(jié)點入棧

　　p = p.getLeft();

　　}

　　p = stack.pop();

　　while (!stack.empty() && p.getRight() == null) {

　　visit(p);

　　p = stack.pop();

　　}

　　visit(p);

　　if (!stack.empty())

　　p = stack.pop();

　　else

　　p = null;

　　}

　　}

　　public static void main(String[] args) {

　　BinTree tree = new BinTree(init());

　　System.out.print(" Pre-Order:");

　　preorder(tree.getRoot());

　　System.out.println();

　　System.out.print(" In-Order:");

　　inorder(tree.getRoot());

　　System.out.println();

　　System.out.print("Post-Order:");

　　postorder(tree.getRoot());

　　System.out.println();

　　System.out.print(" Pre-Order:");

　　iterativePreorder(tree.getRoot());

　　System.out.println();

　　System.out.print(" In-Order:");

　　iterativeInorder(tree.getRoot());

　　System.out.println();

　　System.out.print("Post-Order:");

　　iterativePostorder(tree.getRoot());

　　System.out.println();

　　}

　　}

　　輸出結果

　　Pre-Order:H D B A C G F E

　　In-Order:B A D C H G E F

　　Post-Order:A B C D E F G H

　　Pre-Order:H D B A C G F E

　　In-Order:B A D C H G E F

　　Post-Order:A B C D E F G H

　　如果你現(xiàn)在想學習Java，贏取高薪工作機會，非常簡單，填寫下面信息，學好Java技術高薪工作機會唾手可得。