当前位置：首页 > news >正文

二叉树详解-第一篇树以及二叉树的概念

news 来源：原创 2024/9/21 20:39:18

编辑

1.树的概念及结构

1.1树的概念

1.2树的特点

1.3树的相关概念

1.4树的表示

2.二叉树的概念及结构

2.1二叉树的概念

2.2特殊二叉树-满二叉树和完全二叉树

1.满二叉树的概念及性质

2.完全二叉树的概念及性质

2.3二叉树的性质(重点)

2.4二叉树的存储

1.顺序存储：

2.链式存储

1.树的概念及结构

1.1树的概念

树是一种非线性的数据结构，它是由n(n>=0)个有限结点组成的一个具有参差关系的集合，把它叫做树是因为看起来像一倒挂的树，根在上，叶子在下。其中有一个特殊的节点，称为根节点，根节点没有前驱结点。

如图：

1.2树的特点

树形结构中，子树之间不能有交集，否则就不是属树形结构。

子树是不相交的。

除了根节点之外，每个节点有且仅有一个父节点。

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

1.3树的相关概念

加粗要重点记忆！

节点的度：一个节点的出度为该节点的度。

叶节点或终端节点：度(出度)为0的节点。

非终端节点或分支节点：度(出度)不为0的节点。

双亲结点或父节点：若该结点有子节点，则该节点为子节点的父节点。

孩子节点或子节点：根节点的孩子为孩子结点。

兄弟结点：具有相同父节点的结点互相称为兄弟节点。

树的度：一棵树中，所有节点中节点度最大的度称为树的度。

节点的层次：从根开始，根为第一层，根的子节点为第二层,......。

树的高度或深度：树中所有结点的最大层次；

堂兄弟结点：在同一层的结点，但是不同父节点的结点。

森林：n棵互不相交的树的集合为森林。

1.4树的表示

树的表示，既要保存值，又要保存结点和结点之间的关系。树有很多种表示方法：双亲表示法。孩子表示法，孩子双亲表示法，以及孩子兄弟表示法。我这里主要讲孩子兄弟表示法(左孩子右兄弟表示法)。

已知树的度为N

struct TreeNode
{int val;struct TreeNode* num[N];
};

未知树的度

struct TreeNode
{int val;Seqlist num;//动态顺序表num中存储 struct TreeNode*
};

左孩子右兄弟表示法(重点)

struct TreeNode
{int val;struct TreeNode* leftchild;struct TreeNode* rightbrother;
};

2.二叉树的概念及结构

2.1二叉树的概念

二叉树为树的子集，度最大为二(每个节点最多有两个孩子,左孩子，右孩子)，且二叉树的子树有左右之分，不能颠倒，所以二叉树为有序树。

以下都属于二叉树:

2.2特殊二叉树-满二叉树和完全二叉树

1.满二叉树的概念及性质

满二叉树：一个二叉树中，每一层的结点数都达到了最大值，则这个二叉树为吗，满二叉树。

性质：

满二叉树的节点总数为 $2^{k}-1$ 。(k为二叉树层数)。

层数为 $k=\log_{2}(k+1)$

叶子节点数量 $2(k-1)$

2.完全二叉树的概念及性质

完全二叉树：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。(前k-1层都是满的，最后一层不满，但是从左到右必须是连续的)。

性质：

具有n个结点的完全二叉树的深度

满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

2.3二叉树的性质(重点)

1.若规定根节点的层数为1，则一颗非空二叉树的第i层上最多有 $2^{i-1}$ 个节点.

2.若规定根节点的层数为1，则深度为k的二叉树的最大结点数为 $2^{h}-1$ .

3.对任何一颗二叉树，度为0的叶节点数为 $n{_{0}}^{}$ ，度为2的分支节点数为 $n{_{2}}^{}$ ，则有 $n{_{0}}^{}=n{_{2}}^{}+1$

2.4二叉树的存储

二叉树的存储有两种，一种是顺序存储，一种是链式存储。

1.顺序存储：

顺序存储就是使用数组来存储，非常适用于满二叉树和完全二叉树，若是其他数，则会有空间的浪费。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

用下标计算父子关系：

假设已知父亲下标为 $i$ ，则左孩子的下标为 $2*i+1$ ,则右孩子的下标为 $2*i+2$

假设孩子在数组中的下标为j,则父亲下标为 $(j-1)/2$

因为:若为左孩子则父亲下标为 $(j-1)/2$ ,若为右孩子则父亲下标为 $(j-2)/2$ ,又因为 $(j-jishu)/2=(j-oushu)/2$ ，则统一为 $(j-1)/2$ ;

2.链式存储

用链表来表示一棵二叉树，通常方法是链表中每个节点由三个域组成，数据域和左右指针域，左右指针分别用来给出该节点左孩子和右孩子所在节点的存储地址，链式存储又分为二叉链和三叉链，我们一般学习二叉链，三叉链一般用于红黑树。

//二叉链
struct TreeNode
{int val;//值struct TreeNode* left;//左孩子struct TreeNode* right;//右孩子
};//三叉链
struct TreeNode
{int val;//值struct TreeNode* left;//左孩子struct TreeNode* right;//右孩子struct TreeNode* parent;//当前节点的双亲
};

本篇完。