资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

二叉树知识点最详细最全讲解

创作时间:

作者:

@小白创作中心

二叉树知识点最详细最全讲解

引用

CSDN

https://m.blog.csdn.net/qq_41404557/article/details/115447169

二叉树是计算机科学中一种重要的数据结构，广泛应用于算法设计和软件开发中。本文将从树的定义开始，逐步深入讲解二叉树的定义、种类、存储方式和遍历方法，帮助读者全面掌握二叉树的相关知识。

1. 树的介绍

1.1 树的定义

树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。

把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个节点有零个或多个子节点
没有父节点的节点称为根节点
每一个非跟节点有且仅有一个父节点
除了根节点以外，每个子节点可以分为多个不想交的子树

1.2 树的基本术语

若一个节点有子树，那么该节点称为子树根节点的“双亲”，子树的跟是该节点的“孩子”。有相同双亲的节点互为“兄弟节点”。一个节点的所有子树上的任何节点都是该节点的后裔。从根节点到某个节点的路径上的所有节点都是该节点的祖先。

节点的度：节点拥有的子树的数目。

叶子：度为零的节点。

分支节点：度不为零的节点。

树的度：树中节点的最大的度。

层次：根节点的层次为1，其余节点的层次等于该节点的双亲节点加1。

树的高度：树中节点的最大层次。

无序数：如果树中节点的各子树之间的次序是不重要的，可以交换位置。

有序数：如果树中结点的各子树的次序是重要的，不可以交换位置。

森林：0个或多个不相交的树组成。对森林加上一个跟，森林即成为树；删去跟，树即成为森林。

1.3 相关性质

2. 二叉树的介绍

2.1 二叉树的定义

二叉树是每个节点最多有两个子树的树结构。它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；活着左、右子树皆为空。

2.2 二叉树与度为2的树的区别

度为2的的树必须有三个节点以上(否则就不叫度为二了，一定要先存在)，二叉树可以为空。
二叉树的度不一定为2,比如斜树。
二叉树有左右节点区分，而度为2的树没有左右节点的区分。

2.3 二叉树的性质

性质1：二叉树第i层上的节点数目最多为 2^i-1 (i≥1)。

性质2：深度为k的二叉树至多有2^k-1个节点（k>=1）。

性质3：包含n个节点的二叉树的高度至少为log₂ (n+1)。

性质4：在任意一颗二叉树中，若终端节点的个数为n0，度为2的节点数为n2，则n0=n2+1。

3. 二叉树的种类

3.1 满二叉树

3.1.1 定义

高度为h，并且由2^h –1个结点的二叉树，被称为满二叉树。

3.2 完全二叉树

3.2.1 定义

一颗二叉树中，只有最下面两层节点的度可以小于2，并且最下层的叶节点集中在靠左的若干位置上。

3.2.2 特点

叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。显然，一颗满二叉树必定是一颗完全二叉树，而完全而二叉树不一定是满二叉树。

3.3 二叉查找树

3.3.1 定义

二叉查找树（Binary Search Tree）,又被称为二叉搜索树。设x为二叉树中的一个节点，x节点包含关键字Key，节点x的Key值记为Key[x]。如果y是x的左子树中的一个节点，则Key[y]<=Key[x]；如果y是x的有子树的一个节点，则Key[y]>=Key[x]。

3.3.2 特点

若任意节点的左子树不空，则左子树上所有的值均小于根节点的值
若任意节点的右子树不空，则右子树上所有节点的值均大于根节点的值（更大于左子树上的值）
任意节点的左、右子树也分别为二叉查找树
没有键值相等的节点

3.3.3 二叉查找树C语言实现

3.3.3.1 节点定义

typedef int Type;
typedef struct BSTreeNode{
    Type   key;//关键字（键值）
    struct BSTreeNode *left;//左孩子
    struct BSTreeNode *right;//右孩子
    struct BSTreeNode *parent;//父节点
}Node ,*BSTree;

二叉查找树的节点包含的基本信息：

key——关键值，是用来对二叉查找树的节点进行排序的。
left——指向当前节点的左孩子。
right——指向当前孩子的右节点。
parent——指向当前节点的父节点。

3.3.3.2 创建节点

struct Node* create_bstree_node(Type key,Node *parent,Node *left, Node* right)
{
    Node* p;
    if ((p = (Node *)malloc(sizeof(Node))) == NULL)
        return NULL;
    p->key = key;
    p->left = left;
    p->right = right;
    p->parent = parent;
    return p;
}

我这里只是写了一部分，本篇文章的重点不在这里，想继续研究或者想更深入了解的可以转一下博主：https://www.cnblogs.com/skywang12345/p/3576328.html#a2

3.4 平衡二叉搜索树

3.4.1 定义

平衡二叉树搜索树：又被称为AVL(Adelson-Velsky and Landis)树，且具有以下性质：它是一颗空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。如图：

4. 二叉树的存储方式

4.1 链式存储

通过指针把分布在散落在各个地址的节点串联在一起，链式存储如图所示：

4.2 顺序存储

其实就是用数组来存储二叉树，顺序存储的方式如图：

4.2.1 数组存储的遍历

如果父节点的数组下标是i,那么它的左孩子就是2 * i + 1,右孩子就是i * 2 + 2。（但是用链式表示的二叉树更有利于我们理解，一般都是用链式存储二叉树）

5. 二叉树的遍历方式

5.1 深度优先遍历

① 前序遍历（递归法，迭代法）中左右

② 中序遍历（递归法，迭代法）左中右

③ 后序遍历（递归法，迭代法）左右中

5.2 广度优先遍历

① 层次遍历（迭代法）

6. 遍历的实现（递归实现）

6.1 递归算法三要素

确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件：写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
确定单层递归的逻辑：确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

以前序遍历为例：

「确定递归函数的参数和返回值」：因为要打印出前序遍历节点的数值，所以参数里需要传入vector在放节点的数值，除了这一点就不需要在处理什么数据了也不需要有返回值，所以递归函数返回类型就是void，代码如下：

void traversal(TreeNode* cur, vector<int>& vec)

「确定终止条件」：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要要结束了，所以如果当前遍历的这个节点是空，就直接return，代码如下：

if (cur == NULL) return;

「确定单层递归的逻辑」：前序遍历是中左右的循序，所以在单层递归的逻辑，是要先取中节点的数值，代码如下：

vec.push_back(cur->val);    // 中
traversal(cur->left, vec);  // 左
traversal(cur->right, vec); // 右

6.2 代码实现（递归）

前序遍历：

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

中序遍历：

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        traversal(cur->left, vec);  // 左
        vec.push_back(cur->val);    // 中
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

后序遍历：

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
        vec.push_back(cur->val);    // 中
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

此时可以做一做leetcode上三道题目练练手，分别是：