java实现简单二叉树

之前由于只知道二叉树的遍历有前序、中序和后序，但是却不知道用如何用java去实现它，那么以下就是通过java去实现二叉树的前序、中序和后序

在实现之前还是要了解一下什么是二叉树？？？？😊

二叉树的究竟是个啥呀？？？？
二叉树其实是树形结构的一个重要类型，它包括了根结点，而每个根结点的子节点只有两个，用专业术语捏就称为度，二叉树每个结点的度都不能超过两个哟

二叉树中满二叉树和完全二叉树又是啥呀？有啥区别呀？
满二叉树：那顾名思义辣，就是很满的二叉树😝，即每个结点的度都是2，如下图昂

完全二叉树：所有节点集中在树左边的二叉树,就是说除了叶节点,每个节点都只有左节点或者有两个节点,而没有只有右节点情况，在画个图就非常清晰啦✌

最后结个小尾吧~~
满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树哟

了解完二叉树是什么之后，再来了解一下二叉树的前序、中序、后序的是如何遍历的？？？😊

前序：根结点 -> 左孩子 -> 右孩子

中序：左孩子 -> 根结点 -> 右孩子

后序：左孩子 -> 右孩子 -> 根结点

是不是觉得很简单很简单很简单👏👏👏👏👏👏👏

是不是以为结束啦！还没有呢，接下来进入正题-用java实现三种遍历🚀

上面我们了解了二叉树的概念和二叉树前中后序的遍历，现在我们来用java实现这三种遍历吧，三种遍历的实现主要分为递归方法和非递归方法，二话不说我直接贴代码了，大家可以自己debug更容易了解哦

前序

递归方式

public static List<Integer> inorderFirstTraversal(TreeNode root) {
     // 递归的方式
     // 二叉树前序遍历
     if (null != root) {
         System.out.print(root.val + "->");
         inorderFirstTraversal(root.left);
         inorderFirstTraversal(root.right);
     }
}

非递归方式：

public static List<Integer> inorderFirstTraversal(TreeNode root) {
     // 非递归的方式
     LinkedList<TreeNode> linkedList = new LinkedList<>();
     TreeNode node = root;
     while (null != node || linkedList.size() > 0) {
         if( null != node ){
             System.out.print(node.val + "->");
             linkedList.push(node);
             node = node.getLeft();
         }else{
             TreeNode pop = linkedList.pop();
             node = pop.getRight();
         }
     }
     return null;
}

中序

递归方式：

public static List<Integer> inorderMediumTraversal(TreeNode root) {
    // 二叉树中序遍历
    if (null != root) {
        inorderMediumTraversal(root.left);
        System.out.print(root.val + "->");
        inorderMediumTraversal(root.right);
    }
}

非递归方式：

public static List<Integer> inorderMediumTraversal(TreeNode root) {
     // 非递归中序遍历
     LinkedList<TreeNode> linkedList = new LinkedList<>();
     TreeNode node = root;
     while (null != node || linkedList.size() > 0) {
         if( null != node ){
             linkedList.push(node);
             node = node.getLeft();
         }else{
             TreeNode pop = linkedList.pop();
             System.out.print(pop.val + "->");
             node = pop.getRight();
         }
     }
     return null;
 }

后序

递归方式：

public static List<Integer> inorderLastTraversal(TreeNode root) {
        // 二叉树后序遍历
        if (null != root) {
            inorderMediumTraversal(root.left);
            inorderMediumTraversal(root.right);
            System.out.print(root.val + "->");
        }
 }

非递归方式：

public static List<Integer> inorderLastTraversal(TreeNode root) {
     // 非递归后序遍历
     LinkedList<TreeNode> linkedList = new LinkedList<>();
     TreeNode cur, pre = null;
     linkedList.push(root);
     while ( linkedList.size() > 0 ) {
         cur = linkedList.peek();
         if ((cur.left == null && cur.right == null) || (pre != null && (pre == cur.left || pre == cur.right))) {
             System.out.print(cur.val + "->");
             linkedList.pop();
             pre = cur;
         } else {
             if (cur.right != null)
                 linkedList.push(cur.right);
             if (cur.left != null)
                 linkedList.push(cur.left);
         }
     }
     return null;
 }

还有一个TreeNode类：

public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }

    public int getVal() {
        return val;
    }

    public TreeNode getLeft() {
        return left;
    }

    public TreeNode getRight() {
        return right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}

创作不易，希望大家能点个赞给我继续创作下去的动力，让我们共同进步吧💪