数据结构6-二叉树-二叉树性质和存储方式

文章目录

一、二叉树的性质

1.二叉树的第i层上最多有i个节点

节点最多的情况就是:完美二叉树。

2.深度为k的二叉树最少有k个节点,最多有 2 k − 1 2^k-1 2k−1个节点

最少:斜二叉树,已经退化为线性结构。
最多:完美二叉树,每一层都塞满了 2 0 + 2 1 + ⋯ + 2 k − 1 = 2 k − 1 2^0+2^1+\dots +2^{k-1}=2^k-1 20+21+⋯+2k−1=2k−1个。

3.对于任意一颗非空的二叉树,若其度为0的节点数为 n 0 n_0 n0​,度为2的节点数为 n 2 n_2 n2​,那么 n 0 = n 2 + 1 n_0=n_2+1 n0​=n2​+1

我们给出证明:
计度为1的节点数为 n 1 n_1 n1​,总节点数为 n n n,,易得出 n = n 0 + n 1 + n 2 n=n_0+n_1+n_2 n=n0​+n1​+n2​。再看二叉树中边数,一方面除了根节点每一个节点都有唯一前驱,另一方面边数由 n 2 , n 1 n_2,n_1 n2​,n1​贡献,因此有 n − 1 = 2 n 2 + n 1 = n 0 + n 1 + n 2 − 1 n-1=2n_2+n_1=n_0+n_1+n_2-1 n−1=2n2​+n1​=n0​+n1​+n2​−1,解出 n 0 = n 2 + 1 n_0=n_2+1 n0​=n2​+1。

我们也给出这种关系的解释:
结点为0的数即为叶子节点的数目。而要想产生叶子几点,每一个度为2的节点才能产生一个叶子节点。

4. n n n个节点组成的完全二叉树的深度为 d e p t h = ⌊ l o g 2 n ⌋ + 1 depth=\lfloor log_2n\rfloor +1 depth=⌊log2​n⌋+1

从性质2显然可得

二、二叉树的存储

二叉树的存储方式主要有两种,分别是顺序存储和链式存储。顺序存储适用于二叉树的形态和大小不发生剧烈变化的情况。顺序存储可以使用一维数组进行实现,通过数组元素的下标作为索引,随机存取二叉树的节点。链式存储则是构造链表,每一个节点中都包含着其他节点的地址信息,只能通过迭代以此访问元素。

1.顺序存储

完全二叉树的顺序存储

数据结构6-二叉树-二叉树性质和存储方式
首先按照完全二叉树的层序顺序依次将数据存入一维数组。那么对于一个节点 ( i n d e x = k ) (index=k) (index=k)来说,他的父亲节点为 ⌊ f r a c k 2 ⌋ \lfloor frac{k}{2} \rfloor ⌊frack2⌋,他的左儿子为 2 k 2k 2k,右儿子为 2 k + 1 2k+1 2k+1,如果发生越界则没有左儿子(右儿子)。

一般二叉树的顺序存储

将缺失的节点补上虚节点,将一般二叉树补齐为完全二叉树,然后按照上述的方法进行存储。
数据结构6-二叉树-二叉树性质和存储方式
但是这种存储方法十分低效。尤其是当二叉树退化为线性结构时,会浪费很多的内存空间。

2.链式存储

二叉链表

每个节点有一个数据域和两个指针域。指针域分别指向它的左儿子和右儿子。如果没有该节点没有左儿子(右儿子),就将相应的指针域赋值为NULL。

typedef struct node {
	int data;
	struct node* lchild;
	struct node* rchild;
}Node;

三叉链表

在二叉链表的基础上又增加了一个父亲节点。这样的好处是,相当于在程序内增加了一个记忆回退的stack,方便从该节点退回到父亲。同样的,记得所有没有被赋值的指针域都要被置空

typedef struct node {
	int data;
	struct node* lchild;
	struct node* rchild;
	struct node* parent;
}Node;
上一篇:1.3.2 空间复杂度


下一篇:Day 24 算法笔记之算法初步4.5 二分