[数据结构与算法]Java创建遍历二叉树（递归）并求树高及叶节点个数（代码全）

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

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

一、接口及链结点定义

package BinaryTree;

public interface BinaryTreeInterface <T>{
    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<T> {
    private LinkedNode<T> lChild;
    private LinkedNode<T> rChild;
    private T data;
    LinkedNode<T> next;

    public LinkedNode<T> getNext() {
        return next;
    }

    public void setNext(LinkedNode<T> next) {
        this.next = next;
    }

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

    public LinkedNode<T> getlChild() {
        return lChild;
    }

    public void setlChild(LinkedNode<T> lChild) {
        this.lChild = lChild;
    }

    public LinkedNode<T> getrChild() {
        return rChild;
    }

    public void setrChild(LinkedNode<T> rChild) {
        this.rChild = rChild;
    }

    public T getData() {
        return data;
    }

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

?

二、遍历

1.前序（递归）

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

2.中序（递归）

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

3.后序（递归）

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

?4.层序（队列）

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

package BinaryTree;

public class Queue<T> {
    private LinkedNode<T> frist = null;
    private LinkedNode<T> 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<LinkedNode> queue = new Queue<LinkedNode>();
        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<T> creatPreTree(T[] tree){
        LinkedNode<T> node;
        elementCount++;//索引值，到数组中每一个我们需要添加的点
        if (elementCount > tree.length||tree[elementCount-1].equals("#"))
            node = null;
        else {
            node = new LinkedNode<T>(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，如果对你有帮助的话点个赞再走吧 ~—~

欢迎评论区讨论~