数据结构二叉树-EW帮帮网

本节目标：

掌握树的基本概念

掌握二叉树概念及特性

掌握二叉树的基本操作

1.树型结构

1.1 概念

树是一种非线性的数据结构，它由n（n>0）个有限结点组成的一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树通常有以下特点：

有一个特殊的结点，称为根结点，根结点没有前驱结点，例如上图中A，它就是一个根结点。
除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每一个集合Ti (1 <= i <= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。比如说上图中的树，B、C、D分别是各自树的根结点。
树是递归定义的（稍后会理解）。
除了根结点外，每个结点有且仅有一个父结点。
一棵有N个节点的树有N - 1条边。

注意：树型结构中，子树之间不能有交集，否则就不是树型结构，像这样的就不是：

1.2 关于树的一些专有名词

现在有这么一棵树：

则：

节点的度：一个结点含有子树的个数称为该结点的度。如图中：A的度为3。

树的度：一棵树中，所有结点度的最大值称为树的度。如图中：树的度为3。

叶子结点或终端结点：度为0的结点称为叶结点。如图中：J、F、K、L、H、I均为叶结点。

双亲结点或父结点：若一个结点含义子结构，则这个结点称为其子结点的父结点。如图中：A是B的父结点。

孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点。如图中：B是A的子结点。

根结点：一棵树中，没有父结点的结点称为根结点。如图中：A。

结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，由此类推。

树的高度或深度：树中结点的最大层次。如图中：树的高度为4。

以下树的专有名词仅需了解即可

非终端结点或分支结点：度不为0的结点。如图中：B、C、D、E、G均是。

兄弟结点：具有相同父结点的结点。如图中：B、C、D互为兄弟结点。

堂兄弟结点：双亲在同一层的节点。如图中：E、G互为堂兄弟结点。

结点的祖先：从根到该结点所经分支上的所有结点。如图中：A是所有结点的祖先。

子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如图中：所有结点都是A的子孙。

森林：由m（m>=0）棵互不相交的树组成的集合称为森林。

1.3 树的表示形式

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，但实际上，树有很多种表示方法，比如说：双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。

例如孩子兄弟表示法：

class Node {

        int value; //树中储存的数据

        Node firstChild; //第一个孩子引用

        Node nextBrother; //下一个兄弟引用

}

1.4 树的应用

文件系统管理（目录和文件）

2.二叉树

2.1 概念

一棵二叉树是结点的一个有限集合，该集合：

由一个根结点加两棵分别称为左子树和右子树的二叉树组成，或者为空。

从图中可以看出：

二叉树不存在度大于2的结点。
二叉树的子树有左右之分，次序不能颠倒，所以二叉树是有序树。

【注意】

对于任一的二叉树都是由以下几种情况复合而成的：

2.2 两种特殊的二叉树

1.满二叉树：一棵二叉树，如果每层的结点数都达到最大值，那么这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是2^k - 1，则它就是满二叉树。像这样的：

2.完全二叉树:完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。像这样的：

2.3 二叉树的性质

1.若规定根结点的层数为1，则一棵非空二叉树的第i层是最多有 2^(i - 1) （i>0）个结点。

2.若规定只有根结点的二叉树的深度为1，那么深度为K的二叉树的最大结点数为 2^K - 1（K>0）。

3.具有n个结点的完全二叉树的深度K为 log(n + 1)（底数为2）向上取整。

4.对于具有n个结点的完全二叉树，如果按照从上到下、从左到右的顺序对所有结点从0开始编号，则对于序号为i的结点有：

若 i > 0，双亲序号：(i - 1) / 2；i = 0,i 为根结点编号，无双亲结点。
若2i + 1 < n，那么左孩子序号：2i + 1，否则无左孩子。
若2i + 2 < n，那么右孩子序号：2i + 2，否则无右孩子。

5.对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1。

2.4 二叉树的存储

二叉树的存储结构分为：顺序存储和类似于链表的链式存储。

这里介绍链式存储，二叉树的链式存储是通过一个一个结点引用起来的，常见的表示方式有二叉和三叉表示方式，具体如下：

//孩子表示法

class Node {

        int val; // 数据域

        Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树

        Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树

}

//孩子双亲表示法

class Node {

        int val; // 数据域

        Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树

        Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树

        Node parent; // 当前结点的根结点

}

现在通过孩子表示法创建二叉树结点如下：

public class TreeNode {
    public char val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(char val) {
        this.val = val;
    }
}

2.5 二叉树的遍历

在实现二叉树的基本操作之前，先来了解二叉树的遍历方式有哪些，因为基本操作的实现离不开遍历。所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容、节点内容加 1)。

二叉树的遍历主要有：前序遍历、中序遍历、后序遍历和层序遍历。

现在令N代表根结点，L代表根结点的左子树，R代表根结点的右子树，那么根据遍历根结点的先后次序就引出了前、中、后序三种遍历方式，即：

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

当我们得知了一棵二叉树的前序遍历+中序遍历、后序遍历+中序遍历这两种组合中的一种，我们就可以画出这棵二叉树，因为前序遍历和后序遍历能够确定二叉树的根结点，而中序遍历能确定二叉树的大致结构。

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

2.6 二叉树的基本操作

// 前序遍历

void preOrder(TreeNode root);

// 中序遍历

void inOrder(TreeNode root);

// 后序遍历

void postOrder(TreeNode root);

// 获取树中结点的个数

int size(TreeNode root);

// 获取叶子结点的个数

int getLeafNodeCount(TreeNode root);

// 获取第K层结点的个数

int getKLevelNodeCount(TreeNode root,int k);

// 获取二叉树的高度

int getHeight(TreeNode root);

// 检测值为value的元素是否存在

Node find(TreeNode root, int val);

//层序遍历

void levelOrder(TreeNode root);

// 判断一棵树是不是完全二叉树

boolean isCompleteTree(TreeNode root);

2.6.1 前序遍历、中序遍历、后序遍历

要实现前、中、后序遍历，可以通过递归的方式，也可以通过非递归的方式。这里分别举例，

通过递归实现

实现递归要有两个核心的条件：

递归的终止条件。递归不能无限进行下去，必须存在至少一个 “终止点”，当满足某个条件时，递归停止并返回结果。

递归的递推关系。递归需要将原问题分解为更小的子问题，且子问题的解决方式与原问题一致（即可以通过再次调用自身来解决）。

先来实现前序遍历，它的终止条件是当某个结点为 null时，就回退，递推关系是：遇到根结点先进行打印，接着打印这个根结点的左子树，打印完成后，回退回来，接着打印这个根结点的右子树。

public class MyBinaryTree {

    // 前序遍历
    void preOrder(TreeNode root){
        //回退条件
        if (root == null) {
            return;
        }

        //打印这个根结点的值
        System.out.print(root.val + " ");

        //打印这个根结点的左子树
        preOrder(root.left);

        //打印这个根结点的右子树
        preOrder(root.right);
    }

    // 中序遍历
    void inOrder(TreeNode root) {

    }

    // 后序遍历
    void postOrder(TreeNode root) {

    }
}

现在我们写个方法来构造一个二叉树：

//构造一棵二叉树
public TreeNode func() {
        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');
        
        A.left = B;
        A.right = C;
        B.left = D;
        C.left = E;
        C.right = F;
        
        return A;
    }

进行测试：

public class Test {
    public static void main(String[] args) {
        MyBinaryTree myBinaryTree = new MyBinaryTree();
        TreeNode root = myBinaryTree.func();
        myBinaryTree.preOrder(root);
    }
}

//运行结果
A B D C E F

与我们上述讨论的一致！这样我们就实现了前序遍历了，那么中序遍历和后序遍历就变得很简单了，只不过是打印根结点的顺序发生改变了罢了。

中序遍历与后序遍历：

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

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

这是通过递归的方式实现的，通过非递归的方式如下：

通过非递归实现前、中、后序遍历，我们需要借助栈（Stack）这个数据结构。实现前序遍历的思路通常如下：

1.初始化：定义栈（用于存储二叉树结点），结点变量cur指向二叉树的根结点，此时栈为空。

2.通过循环访问各个结点，当cur != null 或栈不为空时，进入循环。

3.处理左子树：

通过循环处理左子树，当cur != null时：

打印当前cur的值

将cur入栈，暂存。

令cur = cur.left，向左走，继续遍历左子树。

4.回溯处理右子树：当cur == null时，说明左子树已经遍历完毕，此时弹出栈顶结点，用top接收，令cur = top.right，切换到右子树，开始遍历。

5.循环结束：当cur == null并且栈为空时，说明这棵二叉树遍历完成。

// 前序遍历_非递归实现
    void preOrderNor(TreeNode root) {
        //定义栈和cur
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        //进入外部循环，用于遍历整棵树
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                System.out.print(cur.val + " ");
                stack.push(cur);
                cur = cur.left;
            }
            /*
            当走出循环时，说明根结点的左子树的每个结点的左子树都遍历完了
            现在要开始遍历右子树了
            */
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }

知道如何实现非递归的前序遍历了，那么中序遍历也就信手拈来了，只需要把打印结点的值的语句移动到左子树遍历结束后的位置即可：

// 中序遍历_非递归实现
    void inOrderNor(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            //注意，这里打印的是弹出栈顶结点的值！走出上面的循环时，cur == null
            System.out.print(top.val + " ");
            cur = top.right;
        }
    }

后序遍历的非递归实现要比前序、中序遍历要稍微难点，核心原因就一个：它的根节点不能早于右子树访问（顺序是 “左→右→根”）。

前序遍历是 “根→左→右”，只要遇到根就先访问，之后再处理左右子树；中序是 “左→根→右”，左子树遍历完，直接弹出栈里的根就能访问 —— 这两种遍历里，根的访问时机都不用等右子树，逻辑更直接。但后序遍历不行：左子树遍历完后，不能直接访问根，必须先确认 “右子树已经完全遍历结束”，才能回头访问根。这就需要解决一个关键问题：怎么判断 “右子树已经遍历完了”？

因此需要定义一个结点变量prev来记录上一个被访问的节点，用来解决这个问题的 “判断依据”，它能帮我们确认右子树的状态：

如果当前栈顶节点的右子树为空：说明根本没有右子树，自然不用等，直接访问这个根节点就行；

如果当前栈顶节点的右子树 == prev：说明右子树已经遍历完了（因为 prev 就是右子树最后一个被访问的节点），现在可以访问这个根节点了。

只有满足上面两种情况之一，才能访问栈顶的根节点；否则，就必须先去遍历这个根节点的右子树，等右子树遍历完，再回来处理根。那么代码可以这样写：

// 后序遍历_非递归实现
    void postOrderNor(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        //prev 用于记录上一个被访问的结点
        TreeNode prev = null;

        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            //这里不能直接弹出栈顶结点，需要先获取判断一下
            TreeNode top = stack.peek();
            if (top.right == null || top.right == prev) {
                System.out.print(top.val + " ");
                stack.pop();
                //记录上一个被访问结点
                prev = top;
            }else {
                cur = top.right;
            }
        }
    }

如果判断右子树是否遍历结束的条件中没有 top.right == prev，可能会发生死循环：

2.6.2 获取树中结点的个数

思路：可以定义一个成员变量size来记录树中结点的个数，同时通过前序遍历来遍历二叉树的结点，并且每次遍历size++，最后返回size即可。

// 获取树中结点的个数
    private int TreeNodeSize;
    public int size(TreeNode root) {
        //每次调用该方法前，对TreeNodeSize进行重置
        TreeNodeSize = 0;

        countTreeNodeSize(root);
        return TreeNodeSize;
    }
    //通过前序遍历统计结点个数
    private void countTreeNodeSize(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNodeSize++;
        countTreeNodeSize(root.left);
        countTreeNodeSize(root.right);
    }

这是一种思路，还有另一种子问题的思路：我们想要获取一棵二叉树的结点个数，而一棵二叉树的结点个数等于根结点 + 根结点的左子树的结点个数 + 根结点右子树的结点个数，那么代码可以这样写：

// 获取树中结点的个数_子问题思路
    public int size1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 当前结点 + 当前结点的左子树结点数 + 当前结点的右子树结点数
        return 1 + size1(root.left) + size1(root.right);
    }

这种实现更加简洁，通过递归返回值直接累加节点数量，无需额外的成员变量。对于二叉树的基本操作来说，使用子问题思路实现比较好，因为二叉树本身就是递归定义的（每个节点的左右子树也都是二叉树），而 “子问题思路” 就是把 “整棵树的问题” 拆解成 “根 + 左子树子问题 + 右子树子问题”，和树的结构完全匹配。因此后序的其他操作我们都通过子问题思路实现。

对这两个方法分别进行测试：

public class Test {
    public static void main(String[] args) {
        MyBinaryTree myBinaryTree = new MyBinaryTree();
        TreeNode root = myBinaryTree.func();
        myBinaryTree.preOrder(root);

        System.out.println();

        System.out.println("树中的结点个数：" + myBinaryTree.size(root));
        System.out.println("树中的结点个数：" + myBinaryTree.size1(root));
    }
}

//运行结果：
A B D C E F 
树中的结点个数：6
树中的结点个数：6

2.6.3 获取叶子结点个数

叶子结点的判断依据：它没有左子树和右子树，即左子树和右子树都为null。一棵二叉树的叶子结点个数 = 根结点的左子树的叶子结点个数 + 根结点的右子树的叶子结点个数，那么代码如下：

// 获取叶子结点的个数
    public int getLeafNodeCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //判断是否是叶子结点
        if (root.left == null && root.right == null) {
            return 1;
        }
        //返回该结点左子树的叶子结点个数与右子树的叶子结点个数之和
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }

进行测试：

ublic class Test {
    public static void main(String[] args) {
        MyBinaryTree myBinaryTree = new MyBinaryTree();
        TreeNode root = myBinaryTree.func();
        myBinaryTree.preOrder(root);

        System.out.println();

        System.out.println("这棵树的叶子结点个数为：" + myBinaryTree.getLeafNodeCount(root));
    }
}

//运行结果
A B D C E F 
这棵树的叶子结点个数为：3

确实是3个叶子结点，符合预期。

2.6.4 获取第K层结点的个数

思路：想要获取第K层结点的个数，可以分解成左子树的第K - 1层结点数 + 右子树的第K - 1层结点数，比如说现在要获取上图中这棵二叉树第3层的结点数，那么需要获取B这棵树第2层的结点数和C这棵树第2层的结点数，再往下走，B这棵树第2层的结点数又等于B的左子树（即D这棵树）的第1层的结点数 + B的右子树（为null）的第1层的结点数，所以B这棵树第2层的结点数 = 1 + 0 = 1；同理C这棵树第2层的结点数也是这样得出的，最终把B这棵树第2层的结点数 + C这棵树第2层的结点数就得到了A这棵树第3层的结点数。代码可以这样写：

// 获取第K层结点的个数
    public int getKLevelNodeCount(TreeNode root,int k) {
        if (root == null) {
            return 0;
        }
        //该结点位于第一层，返回1
        if (k == 1) {
            return 1;
        }
        //返回这个结点的左子树的第K-1层结点数与右子树的第K-1层结点数之和
        return getKLevelNodeCount(root.left,k - 1)
                + getKLevelNodeCount(root.right,k - 1);
    }

进行测试：

public class Test {
    public static void main(String[] args) {
        MyBinaryTree myBinaryTree = new MyBinaryTree();
        TreeNode root = myBinaryTree.func();
        myBinaryTree.preOrder(root);

        System.out.println();

        System.out.println("这棵树第3层的结点个数为：" + myBinaryTree.getKLevelNodeCount(root,3));
    }
}

//运行结果：
A B D C E F 
这棵树第3层的结点个数为：3

2.6.5 获取二叉树的高度

思路：首先二叉树的高度 = 1（当前根节点本身的层级） + 左右子树中高度较大的值，那么同样可以运用子问题思路，这里通过递归分别计算左子树高度和右子树高度，然后取两者的最大值，再加 1 得到当前树的高度。代码可以这样写：

// 获取二叉树的高度
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //分别获取该结点左子树和右子树的高度
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        //通过三目操作符取得该结点左子树和右子树高度的最大值，再+1返回
        return (leftHeight > rightHeight?leftHeight:rightHeight) + 1;
    }

进行测试：

public class Test {
    public static void main(String[] args) {
        MyBinaryTree myBinaryTree = new MyBinaryTree();
        TreeNode root = myBinaryTree.func();
        myBinaryTree.preOrder(root);

        System.out.println();

        System.out.println("这棵树的高度为：" + myBinaryTree.getHeight(root));
    }
}

//运行结果：
A B D C E F 
这棵树的高度为：3

2.6.6 检测值为value的元素是否存在

思路：可通过前序遍历进行查找，若根结点是查找的结点，那么直接返回，如果不是就在左子树中找，若在左子树中找到的结果不为空则返回，为空则去该结点右子树中找，在右子树中查找时，不论结果是什么都直接返回，因为如果右子树查找结果也为空，什么这棵树没有要查找的结点。代码可以这样写：

// 检测值为value的元素是否存在
    public TreeNode find(TreeNode root, char val) {
        if (root == null) {
            return null;
        }
        //如果当前结点就是要查找的结点，直接返回
        if (root.val == val) {
            return root;
        }
        //对该结点的左子树进行查找
        TreeNode leftNode = find(root.left,val);
        if (leftNode != null) {
            return leftNode;
        }
        //对该节点的右子树进行查找
        TreeNode rightNode = find(root.right,val);
        return rightNode;
    }

进行测试：

public class Test {
    public static void main(String[] args) {
        MyBinaryTree myBinaryTree = new MyBinaryTree();
        TreeNode root = myBinaryTree.func();
        myBinaryTree.preOrder(root);

        System.out.println();

        System.out.println("这棵树上是否有值为'D'的结点："
                + myBinaryTree.find(root,'D'));
    }
}

//运行结果：
A B D C E F 
这棵树上是否有值为'D'的结点：TreeNode@5fd0d5ae

2.6.7 层序遍历

要实现层序遍历，我们需要用到队列（Queue），用来储存结点，一开始令根结点先入队，当队列不为空时，进入循环，将此时的队头结点弹出，结点变量cur接收，并打印它的值，接着若cur的左子树不为null，则入队，右子树不为空，则入队。当循环结束时，二叉树每个结点到遍历到了。代码这样写：

//层序遍历
    public void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

进行测试：

public class Test {
    public static void main(String[] args) {
        MyBinaryTree myBinaryTree = new MyBinaryTree();
        TreeNode root = myBinaryTree.func();
        myBinaryTree.preOrder(root);

        System.out.println();

        System.out.println("层序遍历的结果为");
        myBinaryTree.levelOrder(root);
    }
}

//运行结果：
A B D C E F 
层序遍历的结果为
A B C D E F

2.6.8 判断一棵树是不是完全二叉树

要判断一棵树是否是完全二叉树，我们可以通过层序遍历去判断，在进行分析之前，需要明确一件事——队列可以放空指针null！看下面的图：

根据这个图，可以得出结论：

完全二叉树：遍历结束后，队列中所有结点都为null（因为完全二叉树的结点是 “连续” 的，后续无有效结点）。

非完全二叉树：遍历结束后，队列中仍存在非null的结点（说明结点分布不 “连续”，中间有缺失后还存在有效结点）。

那么代码可以这样写：

// 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        //空树默认为完全二叉树
        if (root == null) {
            return true;
        }
        //进行层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            
            if (cur == null) {
                break;
            }
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        //循环结束后判断队列中是否存在有效结点，存在则返回false
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                return false;
            }
        }
        return true;
    }

进行测试：

public class Test {
    public static void main(String[] args) {
        MyBinaryTree myBinaryTree = new MyBinaryTree();
        TreeNode root = myBinaryTree.func();
        myBinaryTree.preOrder(root);

        System.out.println();

        System.out.println("这棵树是完全二叉树吗：" + myBinaryTree.isCompleteTree(root));
    }
}

//运行结果
A B D C E F 
这棵树是完全二叉树吗：false

显然，确实不是完全二叉树，符合预期！

完整代码如下：

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class MyBinaryTree {

    // 前序遍历
    void preOrder(TreeNode root){
        //回退条件
        if (root == null) {
            return;
        }

        //打印这个根结点的值
        System.out.print(root.val + " ");

        //打印这个根结点的左子树
        preOrder(root.left);

        //打印这个根结点的右子树
        preOrder(root.right);
    }

    // 前序遍历_非递归实现
    void preOrderNor(TreeNode root) {
        //定义栈和cur
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        //进入外部循环，用于遍历整棵树
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                System.out.print(cur.val + " ");
                stack.push(cur);
                cur = cur.left;
            }
            /*
            当走出循环时，说明根结点的左子树的每个结点的左子树都遍历完了
            现在要开始遍历右子树了
            */
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }

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

    // 中序遍历_非递归实现
    void inOrderNor(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            //注意，这里打印的是弹出栈顶结点的值！走出上面的循环时，cur == null
            System.out.print(top.val + " ");
            cur = top.right;
        }
    }

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

    // 后序遍历_非递归实现
    void postOrderNor(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        //prev 用于记录上一个被访问的结点
        TreeNode prev = null;

        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            //这里不能直接弹出栈顶结点，需要先获取判断一下
            TreeNode top = stack.peek();
            if (top.right == null || top.right == prev) {
                System.out.print(top.val + " ");
                stack.pop();
                //记录上一个被访问结点
                prev = top;
            }else {
                cur = top.right;
            }
        }
    }

    //构造一棵二叉树
    public TreeNode func() {
        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');

        A.left = B;
        A.right = C;
        B.left = D;
        C.left = E;
        C.right = F;

        return A;
    }

    // 获取树中节点的个数
    private int TreeNodeSize;
    public int size(TreeNode root) {
        countTreeNodeSize(root);
        return TreeNodeSize;
    }
    //通过前序遍历统计结点个数
    private void countTreeNodeSize(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNodeSize++;
        countTreeNodeSize(root.left);
        countTreeNodeSize(root.right);
    }

    // 获取树中结点的个数_子问题思路
    public int size1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 当前结点 + 当前结点的左子树结点数 + 当前结点的右子树结点数
        return 1 + size1(root.left) + size1(root.right);
    }

    // 获取叶子结点的个数
    public int getLeafNodeCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //判断是否是叶子结点
        if (root.left == null && root.right == null) {
            return 1;
        }
        //返回该结点左子树的叶子结点个数与右子树的叶子结点个数之和
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }

    // 获取第K层结点的个数
    public int getKLevelNodeCount(TreeNode root,int k) {
        if (root == null) {
            return 0;
        }
        //该结点位于第一层，返回1
        if (k == 1) {
            return 1;
        }
        //返回这个结点的左子树的第K-1层结点数与右子树的第K-1层结点数之和
        return getKLevelNodeCount(root.left,k - 1)
                + getKLevelNodeCount(root.right,k - 1);
    }

    // 获取二叉树的高度
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //分别获取该结点左子树和右子树的高度
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        //通过三目操作符取得该结点左子树和右子树高度的最大值，再+1返回
        return (leftHeight > rightHeight?leftHeight:rightHeight) + 1;
    }

    // 检测值为value的元素是否存在
    public TreeNode find(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        //如果当前结点就是要查找的结点，直接返回
        if (root.val == val) {
            return root;
        }
        //对该结点的左子树进行查找
        TreeNode leftNode = find(root.left,val);
        if (leftNode != null) {
            return leftNode;
        }
        //对该节点的右子树进行查找
        TreeNode rightNode = find(root.right,val);
        return rightNode;
    }

    //层序遍历
    public void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        //空树默认为完全二叉树
        if (root == null) {
            return true;
        }
        //进行层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();

            if (cur == null) {
                break;
            }
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        //循环结束后判断队列中是否存在有效结点，存在则返回false
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                return false;
            }
        }
        return true;
    }
}

到此，二叉树的学习与基本方法的实现已经全部完成，感谢您的阅读，如有错误，还请指出！

数据结构二叉树

1.树型结构

1.1 概念

1.2 关于树的一些专有名词

1.3 树的表示形式

1.4 树的应用

2.二叉树

2.1 概念

2.2 两种特殊的二叉树

2.3 二叉树的性质

2.4 二叉树的存储

2.5 二叉树的遍历

2.6 二叉树的基本操作

2.6.1 前序遍历、中序遍历、后序遍历

2.6.2 获取树中结点的个数

2.6.3 获取叶子结点个数

2.6.4 获取第K层结点的个数

2.6.5 获取二叉树的高度

2.6.6 检测值为value的元素是否存在

2.6.7 层序遍历

2.6.8 判断一棵树是不是完全二叉树

网站公告

今日签到

热门文章

最新发布

数据结构 二叉树

1.树型结构

1.1 概念

1.2 关于树的一些专有名词

1.3 树的表示形式

1.4 树的应用

2.二叉树

2.1 概念

2.2 两种特殊的二叉树

2.3 二叉树的性质

2.4 二叉树的存储

2.5 二叉树的遍历

2.6 二叉树的基本操作

2.6.1 前序遍历、中序遍历、后序遍历

2.6.2 获取树中结点的个数

2.6.3 获取叶子结点个数

2.6.4 获取第K层结点的个数

2.6.5 获取二叉树的高度

2.6.6 检测值为value的元素是否存在

2.6.7 层序遍历

2.6.8 判断一棵树是不是完全二叉树

网站公告

今日签到

热门文章

最新发布

数据结构二叉树