Java创建遍历二叉树（递归）并求树高及叶节点个数（代码全）

在学习树的操作之后，我们就可以对数这种数据结构进行创建和使用了，话不多说，直接上代码

PS：为了代码复用和通用性，采用接口然后打包了整个工程，存储数据定义为泛型

package BinaryTree;

public interface BinaryTreeInterface {
    public void preOrder(linkedNode node);//前序遍历
    public void inOrder(linkedNode node);//中序遍历
    public void postOrder(linkedNode node);//后序遍历
    public void levelOrder();//层序遍历
    public int countHigh(linkedNode node);//输出树高
    public int countNum(linkedNode node);//输出叶子结点个数
}

结点采用链表的方式 

package BinaryTree;

public class linkedNode {
    private linkedNode lChild;
    private linkedNode rChild;
    private T data;
    linkedNode next;

    public linkedNode getNext() {
        return next;
    }

    public void setNext(linkedNode next) {
        this.next = next;
    }

    public linkedNode(T element){
        data = element;
    }

    public linkedNode getlChild() {
        return lChild;
    }

    public void setlChild(linkedNode lChild) {
        this.lChild = lChild;
    }

    public linkedNode getrChild() {
        return rChild;
    }

    public void setrChild(linkedNode rChild) {
        this.rChild = rChild;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }
}

@Override
    public void preOrder(linkedNode node){
        if (node==null)
            return;
        else {
            System.out.print(node.getData()+" ");
            preOrder(node.getlChild());
            preOrder(node.getrChild());
        }
    }

@Override
    public void inOrder(linkedNode node){
        if (node==null)
            return;
        else {
            inOrder(node.getlChild());
            System.out.print(node.getData()+" ");
            inOrder(node.getrChild());
        }
    }

@Override
    public void postOrder(linkedNode node){
        if (node==null)
            return;
        else {
            postOrder(node.getlChild());
            postOrder(node.getrChild());
            System.out.print(node.getData()+" ");
        }
    }

这里多说一句，因为层序遍历的特性，采用队列的方式进行存储，所以我们这里提前定义一个队列类供其使用

package BinaryTree;

public class Queue {
    private linkedNode frist = null;
    private linkedNode rear = null;
    public boolean isEmpty(){
        if(frist==null||rear==null)
            return true;
        return false;
    }
    public void enqueue(T element){
        linkedNode node = new linkedNode(element);
        if(isEmpty()){
            frist = node;
            rear = node;
        }
        else {
            rear.setNext(node);
            rear = node;
        }
    }
    public T outqueue(){
        if(isEmpty())
            throw new NullPointerException("队列为空");
        T ele = frist.getData();
        frist = frist.getNext();
        return ele;
    }
}

@Override
    public void levelOrder(){
        Queue queue = new Queue();
        if(root==null)
            return;
        else {
            queue.enqueue(root);//抽象理解为将一颗树加入到这个队列中
            while(!queue.isEmpty()){
                linkedNode tempNode = queue.outqueue();
                System.out.print(tempNode.getData()+" ");
                if(tempNode.getlChild()!=null)
                    queue.enqueue(tempNode.getlChild());
                if (tempNode.getrChild()!=null)
                    queue.enqueue(tempNode.getrChild());
            }
        }
    }

给定一个树的扩展序列（这里为前序）进行二叉树的创建，我们将虚结点定义为”#“

采用递归的方式进行创建

    public void creatTree(T[] tree){
        root = creatPreTree(tree);
    }
    private int elementCount = 0;
    public linkedNode creatPreTree(T[] tree){
        linkedNode node;
        elementCount++;//索引值，到数组中每一个我们需要添加的点
        if (elementCount > tree.length||tree[elementCount-1].equals("#"))
            node = null;
        else {
            node = new linkedNode(tree[elementCount-1]);
            node.setlChild(creatPreTree(tree));
            node.setrChild(creatPreTree(tree));
        }
        return node;
    }

**还是递归**

    @Override
    public int countHigh(linkedNode node){
        if(node == null)
            return 0;
        else{
            int lhight = countHigh(node.getlChild());
            int rhight = countHigh(node.getrChild());
            return Math.max(lhight,rhight)+1;
        }
    }

    @Override
    public int countNum(linkedNode node){
        if(node==null)
            return 0;
        if(node.getlChild()==null&&node.getrChild()==null){
            return 1;
        }
        return countNum(node.getlChild())+countNum(node.getrChild());
    }

如这样一颗拓展二叉树

我们在主类中传入，输出它的遍历及深度、叶节点的个数验证代码

String[] str = {"A","B","C","#","#","D","E","#","G","#","#","F","#","#","#"};

 以上就是Java二叉树的相关操作，原创不易QAQ，如果对你有帮助的话点个赞再走吧 ~—~

欢迎评论区讨论~