Java实现一棵二叉树，并完成二叉树的层次遍历，两种中序遍历 递归 &非递归

使用Java实现一个二叉树。

二叉树是一个递归的数据结构，每个节点最多有两个子节点，且有左右之分，分别称为该节点的左右孩子。二叉树是树形结构的一个重要类型，许多实际问题抽象出来的数据结构往往是二叉树形式，因此二叉树显得特别重要，但它的存储结构和算法都较为简单。

1、模拟实现二叉树

二叉树的结构如下图所示，本篇文章是实现一个字符型的二叉树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PTYiM9O8-1661169037210)(C:/Users/ZHANG/AppData/Roaming/Typora/typora-user-images/image-20220822191113957.png)]

2、定义节点类

根据二叉树的定义，它有两个节点，且有左右之分，称为左孩子和右孩子，则根据定义，可以定义出二叉树的节点类

package tree;

public class TreeNode {

    //为什么是TreeNode类型：因为要创建TreeNode的内存空间
    private TreeNode leftTreeNode;  //左子树
    private TreeNode rightTreeNode;  //右子树
    private Integer value;  //值

    public TreeNode(int value){
        this.value=value;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3、构建有序二叉树

构建方法如下，只要每次调用将值传进来就可构建二叉树

package tree;

import java.util.LinkedList;

/**
 * 如何构建有序二叉树
 */
public class BinaryTree {

    public TreeNode root;  //树的根节点

    /**
     * 数据插入:构建有序树
     * @param value
     */
    public void insert(Integer value){
        //创建一个节点
        TreeNode newNode = new TreeNode(value);
        if(root==null){
            root=newNode;
            return;
        }
        //定义一个游标来遍历整个二叉树
        TreeNode currentNode=root;
        //定义一个游标来记录前一个地址
        TreeNode preNode=null;

        //循环查找
        while (true){
            preNode=currentNode;
            //判断currentNode指向的值和value进行比较
            if(value>currentNode.getValue()){
                currentNode=currentNode.getRightTreeNode();
                if(currentNode==null){
                    preNode.setRightTreeNode(newNode);
                    return;
                }
            }else {
                currentNode=currentNode.getLeftTreeNode();
                if(currentNode==null){
                    preNode.setLeftTreeNode(newNode);
                    return;
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

4、递归构建有序二叉树

package tree;

import java.util.LinkedList;

/**
 * 如何构建有序二叉树
 */
public class BinaryTree {

    public TreeNode root;  //树的根节点

    /**
     * 递归插入：有序二叉树
     * @param node
     * @param value
     */
    public void insertDiGui(TreeNode node,Integer value){
        //创建一个节点
        TreeNode newNode = new TreeNode(value);
        if(root==null){
            root=newNode;
            return;
        }

        //递归开始
        if(value<node.getValue()){
            if(node.getLeftTreeNode()==null){
                node.setLeftTreeNode(newNode);
                return;
            }
            insertDiGui(node.getLeftTreeNode(),value);
        }else{
            if(node.getRightTreeNode()==null){
                node.setRightTreeNode(newNode);
                return;
            }
            insertDiGui(node.getRightTreeNode(),value);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

5、二叉树的层次遍历

输出顺序：

上，左，右

解析：

所谓二叉树的层级遍历：简单地讲就是从二叉树的根节点开始，一层一层递进，逐层遍历二叉树的每个元素
如下图所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5XA9fLL5-1661169037212)(C:/Users/ZHANG/AppData/Roaming/Typora/typora-user-images/image-20220822193609664.png)]

如上所示：该树的层级遍历为：
F、C、E、A、D、H、G、B、M

思路：每次在输出一个结点的同时，把该结点的孩子都存入队列，

例如

1. 刚开始队列为空，
2. F入队，F出队，同时C,E入队，
3. C出队，A,D入队，
4. E出队，H,G入队
5. A出队，D出队，B入队，
6. H出队，G出队，M入队，
7. B出队，M出队

出队顺序为：F、C、E、A、D、H、G、B、M

代码实现：

    /**
     * 层次遍历
     */
    public void levelOrder(){
        LinkedList<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            root  = queue.pop();
            if(root.getLeftTreeNode()!=null){
                queue.add(root.getLeftTreeNode());
            }
            if(root.getRightTreeNode()!=null){
                queue.add(root.getRightTreeNode());
            }
            System.out.print(" "+ root.getValue()+" ");
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

6、中序遍历（递归遍历）

二叉树的中序遍历顺序是左，根，右。

代码实现：

    /**
     * 中序输出
     * @param node
     */
    public void inOrder(TreeNode node){
        if(node==null){
            return;
        }
        inOrder(node.getLeftTreeNode());
        System.out.print(" "+ node.getValue()+" ");
        inOrder(node.getRightTreeNode());
    }
1
2
3
4
5
6
7
8
9
10
11
12

7、非递归中序遍历

​ 非递归的思路是用一个栈，两个while循环，节点非空则入栈，并将其左孩子，左孩子的左孩子，左孩子的左孩子的左孩子。。。入栈，出栈时，记录下当前节点的值，如果有右孩子，则指针指向右孩子，循环，将左孩子入栈。

代码实现：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode temp = root;
        while (temp != null || !stack.isEmpty()) {
            while (temp != null) {
                stack.push(temp);
                temp = temp.left;
            }
            temp = stack.pop();
            res.add(temp.val);
            temp = temp.right;
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18