二叉树的遍历方式和子问题思路

二叉树的遍历方式和子问题思路

引用

CSDN

1.

https://blog.csdn.net/Excuse_lighttime/article/details/145536842

本文详细介绍了二叉树的遍历方式和基本操作，包括前序、中序、后序遍历，以及如何计算结点个数、叶子结点个数、第K层结点个数、树的高度，以及查找特定值的结点是否存在。通过递归和子问题分析的方法，帮助读者深入理解二叉树这一重要数据结构。

下述代码并不是创建二叉树的方式，而是模拟创建一颗二叉树来实现二叉树的遍历方式和体验子问题思路。

public class BinaryTree {
    static class TreeNode {
        public char val;
        //存储左孩子节点的引用
        public TreeNode left;
        //存储右孩子节点的引用
        public TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }
    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;
    }
}  

构成的树如图：

二叉树的遍历：

前序遍历：

此方法访问结点形式：
根 --- > 左子树 --- > 右子树

代码实现：

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;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }  

代码运行结果：

后序遍历：

此方法访问结点形式：
左子树 --- > 右子树 --- >根

代码实现：

public void posOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        posOrder(root.left);
        posOrder(root.right);
        System.out.print(root.val+" ");
    }  

代码运行结果：

这三种遍历方式都是通过递归函数本身来遍历的，通过不断往左和往右边 “递” ，遇到空时return开始 “归” ，所以，分析二叉树递归时可以一直往左递归下去先分析，再往右分析。

二叉树的基本操作：

求树的结点个数（递归遍历思路）：

代码实现：

public int countNode = 0;
public void nodeSize(TreeNode root) {
        if(root == null) {
            return;
        }
        countNode++;
        nodeSize(root.left);
        nodeSize(root.right);
    }  

代码运行结果：
可以看到，求得的结点个数为8是正确的。这种方法是通过边递归边求和的方法。

求树的结点个数（子问题思路）：

对于一棵树，这样分析：
** 一棵树的结点数 = 左子树结点数 + 右子树结点数 + 1。**

要是对一棵树所有结点都这样分析，就可以得到：

public int nodeSize2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return nodeSize2(root.left) + nodeSize2(root.right) + 1;
    }  

代码运行结果：
可以得到结点数也是8 ，子问题思路对于解决二叉树问题很重要，后续也是针对二叉树的子问题思路来解决问题。

求树的叶子结点个数：

对于一棵树，这样分析：
** 一棵树的叶子结点数 = 左子树叶子结点数 + 右子树叶子结点数 。**

public int getLeaf(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            return 1;
        }else {
            return getLeaf(root.left) + getLeaf(root.right);
        }
    }  

求第K层结点个数：

对于一棵树，这样分析：
假如要求根为root的树的第K层结点个数：
以子问题分析得到：
整棵树的第K层结点数 = root.left 的第（K-1）层结点数 + root.right 的第（K-1）层结点数

实现代码：

public int getKLeve(TreeNode root,int k) {
        if(root == null) {
            return 0;
        }
        if(k == 1) {
            return 1;
        }
        return getKLeve(root.left,k-1) + getKLeve(root.right,k-1);
    }  

求树的高度：

对于一棵树， 以子问题分析得到：
** 整棵树的高度 = 取 左子树与右子树 最大的值 + 1.**

代码实现：

public int getHight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftH = getHight(root.left);
        int rightH = getHight(root.right);
        return leftH > rightH ? leftH+1 : rightH + 1;
    }  

判断值为value的结点是否存在：

对于一棵树，分析得到：
先判断左子树是否存在，再判断右子树是否存在，寻找过程中如果找到了就返回当前结点。

代码实现：

public TreeNode find(TreeNode root,char value) {
        if(root == null) {
            return null;
        }
        if(root.val == value) {
            return root;
        }
        TreeNode leftval = find(root.left,value);
        if(leftval != null) {
            return leftval;
        }
        TreeNode rightval = find(root.right,value);
        if(rightval != null) {
            return rightval;
        }
        return null;
    }