数据结构：二叉树（带图详解）

有一个特殊的结点，称为根结点，根结点没有前驱结点

除根结点外，其余结点被分成M(M > 0)

个互不相交的集合

T1

、

T2

、

……

、

Tm

，其中每一个集合

Ti (1 <= i

<= m)

又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有

0个或多个后继

树是递归定义的。

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

树与非树？

以上三种情况可以得出：

子树是不想交的

除了根结点外，每个结点有且仅有一个父结点

一颗N个结点的树有N-1条边

根据下图详细说明树的概念：

结点的度

：一个结点含有子树的个数称为该结点的度；如上图：

A

的度为

6

树的度

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

6

叶子结点或终端结点

：度为

0

的结点称为叶结点；如上图：

B

、

C

、

H

、

I…

等节点为叶结点

双亲结点或父结点

：若一个结点含有子结点，则这个结点称为其子结点的父结点；如上图：

A

是

B

的父结点

孩子结点或子结点

：一个结点含有的子树的根结点称为该结点的子结点；如上图：

B

是

A

的孩子结点

根结点

：一棵树中，没有双亲结点的结点；如上图：

A

结点的层次

：从根开始定义起，根为第

1

层，根的子结点为第

2

层，以此类推

树的高度或深度

：树中结点的最大层次；如上图：树的高度为

4

非终端结点或分支结点

：度不为

0

的结点；如上图：

D

、

E

、

F

、

G…

等节点为分支结点

兄弟结点

：具有相同父结点的结点互称为兄弟结点；如上图：

B

、

C

是兄弟结点

堂兄弟结点

：双亲在同一层的结点互为堂兄弟；如上图：

H

、

I

互为兄弟结点

结点的祖先

：从根到该结点所经分支上的所有结点；如上图：

A

是所有结点的祖先

子孙

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

A

的子孙

森林

：由

m

（

m>=0

）棵互不相交的树组成的集合称为森林

树的表示形式

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：

双亲表示法

，

孩子表示法

、

孩子双亲表示法

、

孩子兄弟表示法

等等。我们这里就简单的了解其中最常用的

孩子兄弟表示法

。

class Node {
     int value; // 树中存储的数据
     Node firstChild; // 第一个孩子引用
     Node nextBrother; // 下一个兄弟引用
}

二叉树

二叉树的概念

二叉树

（binary tree）是指树中

结点的度不大于2

的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵

空树

，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的

非空树

；左子树和右子树又同样都是二叉树

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

两种特殊的二叉树

1、满二叉树

满二叉树

:

一棵二叉树，如果

每层的结点数都达到最大值，则这棵二叉树就是满二叉树

。也就是说，

如果一棵二叉树的层数为n，且结点总数是

2ⁿ – 1

，则它就是满二叉树

。

2、完全二叉树

完全二叉树

:

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为

K

的，有

n个结点的二叉树，当且仅当其每一个结点都与深度为K

的满二叉树中编号从

0

至

n-1

的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

注意：满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树

二叉树的性质

1.

若规定

根结点的层数为

1

，则一棵

非空二叉树的

第i层上最多

有

2^(i-1) （i>0）

个结点

ps：因为求的是

第i层上最多的结点个数

可以简单

将二叉树理解成满二叉树

2.

若规定只有

根结点的二叉树的深度为

1

，则

深度为

K

的二叉树的最大结点数是

2^k -1（k≥0）

ps：二叉树的

最大结点个数

也可以

将二叉树理解成满二叉树

3.

对任何一棵二叉树

,

如果其

叶结点个数为

n0

,

度为

2

的非叶结点个数为

n2

,

则有

n0＝n2＋1

ps：在任意二叉树中，度为0的结点比度为2的结点多一个

假设：二叉树中总的结点个数为N，度为0的结点有n0个，度为1的结点有n1个，度为2的结点n2有n2个 ——> N = n0 + n1 （1）二叉树中总的结点个数为N，在二叉树中总共有N-1条边 ——从下往上看 n0的结点——叶子结点：往下不可能产生边 n1的结点——只有一个孩子的结点：往下只能产生一条边 n2的结点——两个孩子结点均存在：往下可以产生两条边利用总边数建立一个式子——>N-1 = n1 + 2* n2 （2）结合两个式子得出n0 = n2 + 1

4.

具有

n

个结点的完全二叉树的深度

k为

log₂(n+1)

向上取整

满二叉树也是完全二叉树，而满二叉树总结点个数为：2^h – 1 = n 即 h = log₂(n+1) 如果是满二叉树，h计算出来之后肯定是整数；如果是完全二叉树，h计算出来之后可能是小数（向上取整数）

5.

对于具有

n

个结点的完全二叉树

，如果按照

从上至下从左至右的顺序对所有节点从

0

开始编号

，则对于

序号为i的结点有

：

若

i>0

，

双亲序号：

(i-1)/2

；

i=0

，

i

为根结点编号

，无双亲结点

若

2i+1<n

，左孩子序号：

2i+1

，否则无左孩子

若

2i+2<n

，右孩子序号：

2i+2

，否则无右孩子

二叉树的存储

二叉树的存储结构

分为：

顺序存储

和

类似于链表的链式存储

顺序存储适合存储完全二叉树
类似于链表的链表存储适合存储任意二叉树

二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式

，具体如下：

// 孩子表示法
class Node {
     int val;        // 数据域
     Node left;      // 左孩子的引用，常常代表左孩子为根的整棵左子树
     Node right;     // 右孩子的引用，常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {
     int val;        // 数据域
     Node left;      // 左孩子的引用，常常代表左孩子为根的整棵左子树
     Node right;     // 右孩子的引用，常常代表右孩子为根的整棵右子树
     Node parent;    // 当前节点的根节点
}

二叉树的遍历

1.

前中后序遍历

学习二叉树结构，最简单的方式就是遍历。所谓

遍历

(Traversal)

是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。

访问结点所做的操作依赖于具体的应用问题

(

比如：打印节点内容、节点内容加1)。遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础。

在遍历二叉树时，如果没有进行某种约定，每个人都按照自己的方式遍历，得出的结果就比较混乱，

如果按照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的

。如果

N

代表根节点，

L

代表根节点的左子树，R

代表根节点的右子树，则根据遍历根节点的先后次序有以下遍历方式：

NLR

：前序遍历

(Preorder Traversal

亦称先序遍历

)——

访问根结点

—>

根的左子树

—>

根的右子树。
LNR

：中序遍历

(Inorder Traversal)——

根的左子树

—>

根节点

—>

根的右子树。
LRN

：后序遍历

(Postorder Traversal)——

根的左子树

—>

根的右子树

—>

根节点。

// 前序遍历 - 操作：指的是对节点中的值域进行打印
    private void preOrder(BTNode treeRoot){
        /*
        if(null == treeRoot){
            return;
        }

        // 非空
        // 1. 先遍历根节点
        System.out.print(treeRoot.data + " ");

        // 2. 再遍历根节点的左子树----注意：根节点的左子树也是二叉树，遍历根节点的左子树与遍历原树的规则相同
        preOrder(treeRoot.left);

        // 3. 最后再遍历根节点的右子树----注意：根节点的右子树也是二叉树，遍历根节点的右子树与遍历原树的规则相同
        preOrder(treeRoot.right);
        */

        if(treeRoot != null){
            System.out.print(treeRoot.data + " ");
            preOrder(treeRoot.left);
            preOrder(treeRoot.right);
        }
    }

//中序遍历
    private void inOrder(BTNode treeRoot){
        if(treeRoot != null){
            inOrder(treeRoot.left);
            System.out.print(treeRoot.data + " ");
            inOrder(treeRoot.right);
        }
    }

//后序遍历
    private void postOrder(BTNode treeRoot){
        if(treeRoot != null){
            postOrder(treeRoot.left);
            postOrder(treeRoot.right);
            System.out.print(treeRoot.data + " ");
        }
    }

根据下面的二叉树分析

前序递归遍历图解，中序和后序递归遍历类似。

前序遍历结果：

1 2 3 4 5 6

中序遍历结果：

3 2 1 5 4 6

后序遍历结果：

3 1 5 6 4 1

还原二叉树

通过前序和中序遍历结果还原二叉树

前序：根——左子树——右子树通过前序遍历结果可以找到二叉树或者其子树的根结点

中序：左子树——根——右子树在中序遍历结果中找到根的位置，根位置之前的元素是根左子树中的结点，根位置之后的元素是根右子树中的结点

通过后序和中序遍历结果还原二叉树

后序：左子树——右子树——根先从后序遍历结果中确定二叉树的根结点

中序：左子树——根——右子树在中序遍历结果中找到根的位置，根位置之前的元素是根左子树中的结点，根位置之后的元素是根右子树中的结点。先递归还原根右子树，然后再还原根左子树

通过前序和后序遍历结果能否还原二叉树？

不能

根据前序和后序遍历结果还原二叉树。因为前序和后序可以确定二叉树的根结点，但是无法确定根结点的左右子树。

2、层序遍历

层序遍历

：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1

，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第

2层上的节点，接着是第三层的节点，以此类推，

自上而下，自左至右逐层访问树的结点

的过程就是层序遍历。

层序遍历结果：ABCDEFGHI

下面关于二叉树层序遍历的两道题目

二叉树的层序遍历

import java.util.*;	
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        
        return ret;
    }
}

根据这道题可以尝试一下另一道层序遍历二叉树

二叉树的层序遍历Ⅱ

ps：数组倒置

二叉树的基本操作

// 获取二叉树中节点的个数
    private int size(BTNode treeRoot){
        if(treeRoot == null){
            return 0;
        }

        return 1 + size(treeRoot.left) + size(treeRoot.right);
    }

    // 获取二叉树中叶子节点的个数
    private int getLeafNode(BTNode treeRoot){
        if(treeRoot == null){
            return 0;
        }

        if(treeRoot.left == null && treeRoot.right == null){
            return 1;
        }

        return getLeafNode(treeRoot.left) + getLeafNode(treeRoot.right);
    }

    // 获取二叉树中第k层节点个数----注意：认为根就在第1层
    private int getKLevelNode(BTNode treeRoot, int k){
        if(treeRoot == null || k <= 0){
            return 0;
        }

        // 树一定不为空，k==1说明：获取第一层节点总数，而第一层只有根节点
        if(k == 1){
            return 1;
        }

        return getKLevelNode(treeRoot.left, k-1) + getKLevelNode(treeRoot.right, k-1);
    }

    // 获取树的高度
    private int height(BTNode treeRoot){
        if(treeRoot == null){
            return 0;
        }

        int leftHeight = height(treeRoot.left);
        int rightHeight = height(treeRoot.right);

        return leftHeight > rightHeight? leftHeight+1 : rightHeight+1;
    }

    // 查找值为data的节点，并返回
    private BTNode find(BTNode treeRoot, int data){
        if(treeRoot == null){
            return null;
        }

        if(treeRoot.data == data){
            return treeRoot;
        }

        BTNode ret = find(treeRoot.left, data);
        if(ret != null){
            return ret;
        }

        return find(treeRoot.right, data);
    }

记得点赞和收藏哦！！

原文链接：https://blog.csdn.net/m0_51601105/article/details/121069707

树的概念和结构

树的概念