【数据结构与算法】初识二叉树(中)

✨hello，进来的小伙伴们，你们好耶！✨

🚀🚀系列专栏：【数据结构与算法】

⛴️⛴️本篇内容:二叉树的三种遍历方式以及二叉树的模拟实现。

⛵⛵作者简介：一名双非本科大三在读的Java编程小白，不行动起来，你永远只是旁观者！

🛰️🛰️码云存放仓库gitee:https://gitee.com/king-zhou-of-java/preliminary-data-structure.git

一、二叉树的遍历

🚀🚀1、前中后序遍历

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容）

遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础。

NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树。
LNR：中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。
LRN：后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点。

 前序遍历结果：1 2 4 5 3 6

 中序遍历结果：4 2 5 1 6 3

 后序遍历结果：4 5 2 6 3 1

✈️✈️2、层序遍历

层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层
上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

对于上图层序遍历结果为：1 2 3 4 5  6

🚠🚠3、选择题练习

🍊1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为(A)
A: ABDHECFG  B: ABCDEFGH  C: HDBEAFCG  D: HDEBFGCA

🍖🍖解答：由题干我们可以知道这是一个完全二叉树，又是层序遍历的结果已经给出，那么我们可以顺势画出该二叉树，层序遍历的第一个节点就是根节点，依次画出得：

 

 🍎2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为(A)
A: E      B: F      C: G      D: H

🍗🍗解答：先序遍历的第一个节点就是我们的根节点，由题意的A。

🍅3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为(D)
A: adbce    B: decab    C: debac    D: abcde

🧀🧀解答：由题意，给出了中序和后续的节点，由后续最后一个节点就是根节点知道a就是根节点，中序第一个节点就是最左侧的节点，那么最左侧的节点就是b，那么看中序的结果是badce，那么根节点a的左孩子就只有一个b，dce都在a的右边，在根据后续遍历的结果dec得出c是右边节点的根节点，于是可以画出我们的二叉树。

🍏 4.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出(同一层从左到右)的序列为(A)
A: FEDCBA   B: CBAFED   C: DEFCBA   D: ABCDEF

🍤🍤解答：我们先来回顾一下后序和中序的遍历方式；后序：左右根   中序：左根右  由题意得知后序与中序的遍历结果相同，那么我们发现舍去右孩子，二者的遍历方式都是左根，也就是说该二叉树是没有右孩子的一颗二叉树。画出效果图如下：

 🍼🍼重要结论：只给出二叉树的前序和后序的结果，是无法推导出该课二叉树的模型的，也就是三种遍历方式，想要通过其中两种得到第三种的结果，则这两种方式中必须存在中序遍历！

二、二叉树的基本操作

接下来博主将通过idea来演示二叉树的基本操作。

我们下面的基本操作都是基于这个二叉树来完成的！

1、首先我们新建一个包名为BinaryTree,在这个包下新建两个类Test 和 TestBinaryTree。

2、我们初始化实现一个内部类：

      public class TreeNode {
         char val;
         TreeNode left;
         TreeNode right;
         TreeNode() {
 
         }
         TreeNode(char val) {
 
             this.val = val;
         }
         TreeNode(char val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
    }
 }
 
    public TreeNode createTree() {//创建二叉树
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
 
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
 
        return A;
    }

 3、三种遍历方式的实现

  public void preOrder(TreeNode root){//前序遍历
         if(root == null){
             return;
         }
         System.out.print(root.val+" ");
         preOrder(root.left);
         preOrder(root.right);
    }
 
    public void inOrder(TreeNode root){//中序遍历
        if(root == null){
            return;
        }
        preOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
 
 
    public void postOrder(TreeNode root){//后序遍历
        if(root == null){
            return;
        }
        preOrder(root.left);
        inOrder(root.right);
        System.out.print(root.val+" ");
    }

运行结果：

4、获取树中节点的个数(2种方法)

   // 获取树中节点的个数 两种方法
    public static int nodeSize = 0;
    public int size(TreeNode root) {
        if(root == null) {
            return 0;
        }
        nodeSize++;
        size(root.left);
        size(root.right);
        return nodeSize;
    }
 
    public int size2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int tmp = size2(root.left)+size2(root.right)+1;
        return tmp;
    }

运行结果：

5、获取叶子节点的个数(两种方法)

int getLeafNodeCount(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            return 1;
        }
        int tmp = getLeafNodeCount(root.left) +
                getLeafNodeCount(root.right);
        return tmp;
    }
 
    public static int leafSize = 0;
    void getLeafNodeCount2(TreeNode root) {
        if(root == null) {
            return ;
        }
        if(root.left == null && root.right == null) {
            leafSize++;
        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);
    }

运行结果：

6、判断第K层节点的个数

    int getKLevelNodeCount(TreeNode root,int k) {
        if(root == null || k <= 0) {
            return 0;
        }
        if(k == 1) {
            return 1;
        }
        int tmp = getKLevelNodeCount(root.left,k-1) +
                getKLevelNodeCount(root.right,k-1);
        return tmp;
    }

运行结果：(这里我们求的是第3层的结果)

7、获取二叉树的高度

 
// 时间复杂度：O(n) 
public int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
    }
 
    // 时间复杂度：O(n)
    public int getHeight2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return getHeight2(root.left) > getHeight2(root.right)
                ? getHeight2(root.left)+1 : getHeight2(root.right)+1;
    }

运行结果：

8、检测值为val的元素是否存在

  public TreeNode find(TreeNode root, char val) {
        if(root == null) {
            return null;
        }
        if(root.val == val) {
            return root;
        }
        TreeNode ret1 = find(root.left,val);
        if(ret1 != null) {
            return ret1;
        }
        TreeNode ret2 =  find(root.right,val);
        if(ret2 != null) {
            return ret2;
        }
        return null;
    }
 
    //时间复杂度：O(min(M,N))  P:M  Q:N
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q != null  || p != null && q == null ) {
            return false;
        }
        if(p == null && q == null) {
            return true;
        }
        if(p.val != q.val) {
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

运行结果：(这里我们检测字符H是否在节点中)

 🥧🥧OK，那么二叉树的中篇就讲到这里，下篇博主将会整合二叉树的面试OJ题，期待你的阅读，一键三连！🤟🤟