Java实现二叉树遍历(先序输入Character[] t = {‘a’,’b’,’#’,’d’,’#’,’#’,’c’,’#’,’#’};)

发布于 2021-07-27  36 次阅读


Java是按值传递

如果参数是基本类型,传递的是基本类型的字面量值的拷贝。
如果参数是引用类型,传递的是该参量所引用的对象在堆中地址值的拷贝。

call by sharing

代码如下:

package com.apesblog.BiTree;

public class BiTree<T> {
    private T[] t;
    private BiTNode root;

    private class BiTNode {
        T data;
        BiTNode lchild;
        BiTNode rchild;

        public BiTNode() {
            data = null;
            lchild = null;
            rchild = null;
        }
    }

    public BiTree(T[] t) {
        this.t = t;
        root = creatBiTree(root);

    }

    int i = 0;

    private BiTNode creatBiTree(BiTNode n) {
        if ((Character) t[i] == '#') {
            n = null;
            i++;
        } else {
            n = new BiTNode();
            n.data = t[i];
            i++;
            n.lchild = creatBiTree(n.lchild);
            n.rchild = creatBiTree(n.rchild);
        }
        return n;
    }

    public void preOrder() {
        System.out.print("先序遍历:");
        preOrderTraverse(root);
    }

    private void preOrderTraverse(BiTNode n) {
        if (n == null) {
            return;
        }
        System.out.print(n.data + "   ");
        preOrderTraverse(n.lchild);
        preOrderTraverse(n.rchild);

    }

    public void inOrder() {
        System.out.print("中序遍历:");
        inOrderTraverse(root);
    }

    private void inOrderTraverse(BiTNode n) {
        if (n == null) {
            return;
        }
        preOrderTraverse(n.lchild);
        System.out.print(n.data + "   ");
        preOrderTraverse(n.rchild);

    }

    public void postOrder() {
        System.out.print("后序遍历:");
        postOrderTraverse(root);
    }

    private void postOrderTraverse(BiTNode n) {
        if (n == null) {
            return;
        }
        preOrderTraverse(n.lchild);
        preOrderTraverse(n.rchild);
        System.out.print(n.data + "   ");

    }
}

测试类如下:

package com.apesblog.BiTree;

public class Test {

    public static void main(String[] args) {
        Character[] t = {'a','b','#','d','#','#','c','#','#'};
        BiTree<Character> tree = new BiTree(t);
        tree.preOrder();
        System.out.println();
        tree.inOrder();
        System.out.println();
        tree.postOrder();

    }

}

运行结果: