外观
4.7 二叉树的存储结构
按编号放进数组
现在要把二叉树放进内存。要存的不只是每个结点的值,还有结点之间的关系:谁是谁的左孩子,谁是谁的右孩子。程序要靠这些关系,从一个结点走到另一个结点。
本节问题4.5节那棵二叉树有A、B、C、D、G五个结点。把它放进内存,要记下哪些东西?
先看最省事的办法。第2章的顺序表,把元素一个挨一个放进数组。二叉树的结点也可以这样放:按4.6节的编号,几号结点就放进几号格子。先拿6个结点的完全二叉树试:
几号放进几号格。A是1号,放进1号格;F是6号,放进6号格。数组的0号格空着不用,编号和下标就正好相同。
数组里只有值。六个格子里,只有A到F六个字母。B的左孩子是谁?数组里没有写。
可是这棵树的形状并没有丢。只要知道一个结点的编号,就能算出它的孩子在几号格。
学完这一节,你能把二叉树按两种办法放进内存:按编号放进数组,或者用指针连起来;还能说出每种办法适合什么样的二叉树。
从编号算出孩子和双亲
编号是从上到下、每层从左到右排的。顺着这个排法,一步一步算:
每层从几号开始。第1层从1号开始,第2层从2号开始,第3层从4号开始。上面几层排满是2ᵏ⁻¹ − 1个,所以第k层从2ᵏ⁻¹号开始。
B的孩子。B是2号。排在它前面的只有A,A的两个孩子占了2号、3号。B的孩子接着往下编:左孩子4号,右孩子5号。4是2的两倍。
C的孩子。C是3号。排在它前面的A、B,孩子占了2号到5号。C的左孩子接着编,是6号,6是3的两倍。右孩子该是7号,可这棵树只有6个结点,所以C没有右孩子。
反过来找双亲。4号、5号的双亲是2号,6号的双亲是3号。孩子的编号除以2,去掉小数,就是双亲:5除以2是2.5,去掉小数是2。
一般地,编号为i的结点,前面有i − 1个位置,每个位置都排着两个孩子,占掉2号到2i − 1号。它自己的孩子接着往下编。所以:
- 左孩子是2i号,右孩子是2i + 1号。编号超过结点数n,就是没有这个孩子。
- 双亲是i除以2再去掉小数,记作⌊i/2⌋。1号是根,没有双亲。
层数也能算。第k层从2ᵏ⁻¹号开始,到2ᵏ − 1号结束。6号在4号和7号之间,在第3层。写成式子,编号i在第⌊log₂i⌋ + 1层,⌊log₂i⌋是2的几次方不超过i。n个结点的完全二叉树,最后一个是n号,所以高度是⌊log₂n⌋ + 1。6个结点,2²不超过6,高度是2 + 1 = 3。
数组里一个关系也没有存。关系藏在位置里,用下标算出来。把结点按编号放进一组连续的格子,叫二叉树的顺序存储。
下标从0开始的写法
有的书让根放进0号格。那样编号为i的结点,左孩子是2i + 1,右孩子是2i + 2,双亲是⌊(i − 1)/2⌋。本书和考研统考一样,从1开始。
不是完全二叉树的时候
完全二叉树的编号连成一片,放进数组正好不空。不是完全二叉树的呢?
为了让下标还能算出关系,每个结点只能放在自己编号的格子里。看三棵树:
6个结点的完全二叉树。占着1号到6号,用6格,空0格。
4.5节那棵。G是C的右孩子,编号是7。5号、6号没有结点,格子也得留着:要是把G挪进5号,算出来它就成了B的右孩子。用7格,空2格。
4个结点排成一条链。每个结点都只有右孩子,编号是1、3、7、15。数组要用到15号,用15格,空11格。
结点一样多,浪费多少,只看形状。最坏的是排成一条链:高度为h,只有h个结点,却要按满二叉树留够2ʰ − 1格。
所以顺序存储只适合完全二叉树。根源在于关系绑在位置上:一个位置上没有结点,格子也得留着。
顺序存储:用C语言表示
顺序存储就是一个数组,再记下用到的最大编号n。空着的格子放'#'。0号格不存结点,也放'#',正好拿来表示"没有"。
三个函数,各算一个编号。没有这个结点时返回0,取出来就是'#':
c
#include <stdio.h>
#define MAXSIZE 16
#define NIL '#' /* 空着的格子 */
typedef struct {
char data[MAXSIZE]; /* data[0]不用,i号结点放在data[i] */
int n; /* 用到的最大编号 */
} SqBiTree;
/* 没有时返回0:0号格子不放结点,正好表示"没有" */
int LeftChild(SqBiTree *T, int i) {
int c = 2 * i;
return c <= T->n && T->data[c] != NIL ? c : 0;
}
int RightChild(SqBiTree *T, int i) {
int c = 2 * i + 1;
return c <= T->n && T->data[c] != NIL ? c : 0;
}
int Parent(int i) {
return i > 1 ? i / 2 : 0;
}找孩子要看两件事:编号有没有超过n,格子里是不是空的。找双亲不用看数组,只靠编号就算出来了。
把6个结点的完全二叉树和4.5节那棵都存进去,逐个打印每个结点的双亲和孩子:
c
void Show(SqBiTree *T) {
for (int i = 1; i <= T->n; i++) {
if (T->data[i] == NIL) continue;
printf("%c: 双亲%c 左孩子%c 右孩子%c\n", T->data[i], T->data[Parent(i)],
T->data[LeftChild(T, i)], T->data[RightChild(T, i)]);
}
}
int main(void) {
SqBiTree T = { "#ABCDEF", 6 }; /* 6个结点的完全二叉树 */
SqBiTree U = { "#ABCD##G", 7 }; /* 4.5节那棵:5号、6号空着 */
Show(&T);
printf("\n");
Show(&U);
return 0;
}text
A: 双亲# 左孩子B 右孩子C
B: 双亲A 左孩子D 右孩子E
C: 双亲A 左孩子F 右孩子#
D: 双亲B 左孩子# 右孩子#
E: 双亲B 左孩子# 右孩子#
F: 双亲C 左孩子# 右孩子#
A: 双亲# 左孩子B 右孩子C
B: 双亲A 左孩子D 右孩子#
C: 双亲A 左孩子# 右孩子G
D: 双亲B 左孩子# 右孩子#
G: 双亲C 左孩子# 右孩子#第二棵树里,C的左孩子算出来是6号。6号格放的是'#',所以C没有左孩子;右孩子是7号的G。空着的5号、6号,就是为了让这些算式还算得对。
把关系记在结点里
顺序存储的浪费,根源是关系绑在位置上。那就不让位置说明关系,换一个办法:
结点放在哪都行。不再按编号排进一个数组。和第2章的链表一样,每个结点单独用malloc申请,系统给哪就放哪。
关系丢了。位置不再说明任何事。340号的B是谁的孩子?它有没有孩子?只看地址,看不出来。
把孩子的地址记下来。顺序存储靠下标算出孩子,现在算不出来,就明着记在结点里。4.5节说过,每个结点最多两个孩子,左右的位置是固定的。所以每个结点留两格:一格记左孩子的地址,一格记右孩子的地址。
没有孩子就写NULL。B只有左孩子D,右孩子那一格写NULL,图里画成∧。D没有孩子,两格都是NULL。
这样,每个结点有三格:中间放值,两边放左孩子、右孩子的地址。用这样的结点存二叉树,叫二叉树的链式存储,连起来的整体叫二叉链表。
A左边那一格存着340,就是B的地址,图里画成从这一格指向B的箭头。两种说法是同一件事。
整棵树只要记住根A的地址200,就能顺着指针走到每一个结点。关系写在结点里,结点放在哪都不要紧,也不用给没有的结点留格子。
链式存储:用C语言表示
结点有三格,写成结构体。BiTree是指向结点的指针:拿着根的地址,就拿着整棵树。
c
typedef struct BiTNode {
char data;
struct BiTNode *lchild, *rchild; /* 左孩子、右孩子的地址 */
} BiTNode, *BiTree;一个结点一个结点地搭出4.5节那棵树:
第一步:申请A。用malloc申请一个结点,放进A。它还没有孩子,两格都写NULL。T记着它的地址,T就是这棵树。
c
BiTree T = (BiTNode *)malloc(sizeof(BiTNode));
T->data = 'A';
T->lchild = NULL;
T->rchild = NULL;第二步:申请B,挂到A的左边。前四行和A一样。最后一行把B的地址写进A的左孩子格。
c
BiTNode *b = (BiTNode *)malloc(sizeof(BiTNode));
b->data = 'B';
b->lchild = NULL;
b->rchild = NULL;
T->lchild = b;第三步:其余同理。C挂到A的右边,D挂到B的左边,G挂到C的右边。每个都是申请、放值、两格写NULL,再把地址写进双亲的一格里。
完整程序搭好这棵树,再逐个打印每个结点的孩子:
c
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode {
char data;
struct BiTNode *lchild, *rchild; /* 左孩子、右孩子的地址 */
} BiTNode, *BiTree;
void Show(BiTNode *p) {
printf("%c: 左孩子%c 右孩子%c\n", p->data,
p->lchild ? p->lchild->data : '#', p->rchild ? p->rchild->data : '#');
}
int main(void) {
/* 第一步:A */
BiTree T = (BiTNode *)malloc(sizeof(BiTNode));
T->data = 'A';
T->lchild = NULL;
T->rchild = NULL;
/* 第二步:B,挂到A的左边 */
BiTNode *b = (BiTNode *)malloc(sizeof(BiTNode));
b->data = 'B';
b->lchild = NULL;
b->rchild = NULL;
T->lchild = b;
/* 第三步:C挂到A的右边,D挂到B的左边,G挂到C的右边 */
BiTNode *c = (BiTNode *)malloc(sizeof(BiTNode));
c->data = 'C';
c->lchild = NULL;
c->rchild = NULL;
T->rchild = c;
BiTNode *d = (BiTNode *)malloc(sizeof(BiTNode));
d->data = 'D';
d->lchild = NULL;
d->rchild = NULL;
b->lchild = d;
BiTNode *g = (BiTNode *)malloc(sizeof(BiTNode));
g->data = 'G';
g->lchild = NULL;
g->rchild = NULL;
c->rchild = g;
Show(T);
Show(b);
Show(c);
Show(d);
Show(g);
free(d);
free(g);
free(b);
free(c);
free(T);
return 0;
}text
A: 左孩子B 右孩子C
B: 左孩子D 右孩子#
C: 左孩子# 右孩子G
D: 左孩子# 右孩子#
G: 左孩子# 右孩子#和顺序存储打印的第二棵一样,关系一个不差。这回没有空着的格子:5个结点,就申请5个。
空指针和双亲
二叉链表里,有些指针格是空的。数一数4.5节那棵:
一共10个指针格。5个结点,每个两格。
非空的4个。除了根,每个结点恰好有一个双亲,被双亲的一格指着。5个结点去掉根,是4个。
空的6个。10个减4个,剩下6个∧:B右边一个,C左边一个,D、G各两个。
一般地,n个结点有2n个指针格,非空的n − 1个,空的n + 1个。空的比非空的还多,后面会拿这些空格记别的东西。
二叉链表还有一件事做不到:找双亲。顺序存储里,双亲是⌊i/2⌋,一步算出。二叉链表的结点只记着孩子,不记双亲。要找G的双亲,只能从根往下一个一个找。
三叉链表。经常要找双亲时,每个结点再加一格,记双亲的地址。根没有双亲,那一格是NULL。这样的结点有四格,连起来叫三叉链表。
两种存法比一比
两种存法记下的关系一样多,差在关系放在哪里。顺序存储放在位置里,链式存储写在结点里。
空间。完全二叉树用顺序存储,n个结点正好n格,一个指针也不用存。不是完全二叉树时,空着的位置也要留格子,最坏要2ʰ − 1格。二叉链表每个结点多两个指针,可是结点有几个就申请几个,形状再歪也不浪费格子。
找孩子。两种都是一步。顺序存储算2i、2i + 1;二叉链表读lchild、rchild。
找双亲。顺序存储算⌊i/2⌋,一步。二叉链表要从根往下找;加一格成三叉链表,又是一步。
| 顺序存储 | 二叉链表 | |
|---|---|---|
| 关系放在哪 | 位置里,用下标算 | 结点里,用指针记 |
| 空间 | 完全二叉树正好n格;最坏2ʰ − 1格 | 每个结点多两个指针,不留空位 |
| 找孩子 | 2i、2i + 1 | lchild、rchild |
| 找双亲 | ⌊i/2⌋ | 从根找;三叉链表一步 |
| 适合 | 完全二叉树 | 任何二叉树 |
回到本节问题。A、B、C、D、G这棵树,要记下五个值,还有四条父子关系。它不是完全二叉树,顺序存储要7格、空2格;二叉链表5个结点,每个记下值和两个孩子的地址。所以一般的二叉树都用二叉链表存,后面讲遍历也用它。
练习1:编号算关系
填空
一棵有10个结点的完全二叉树,按编号放进数组,下标从1开始:
- 5号结点的双亲是 号
- 5号结点的左孩子是 号
- 5号结点的右孩子
- 这棵树的高度是
5号的双亲是5除以2去掉小数,是2号。左孩子是2 × 5 = 10号;右孩子该是11号,超过了10,所以没有。2³不超过10,高度是3 + 1 = 4。
练习2:顺序存储要几格?
填空
两棵二叉树都按编号放进数组,下标从1开始,0号格不算:
- ①要用 格,其中空着 格
- ②要用 格,其中空着 格
①里D是B的右孩子,编号是2 × 2 + 1 = 5,要用到5号,4号空着。②里B是3号,C是3的右孩子,2 × 3 + 1 = 7号,3个结点用7格,空4格。
练习3:数空指针
填空
一棵二叉树有10个结点:
- 用二叉链表存,空指针有 个,非空的有 个
- 用三叉链表存,空指针有 个
二叉链表有20个指针格。除了根,每个结点被双亲指着一次,非空的是9个,空的是11个。三叉链表再加10个双亲格,只有根的那一格是空的,一共11 + 1 = 12个。
到这里你有了二叉树的两种存储结构。顺序存储把结点按编号放进数组,关系从下标算出来:i号的左孩子2i、右孩子2i + 1、双亲⌊i/2⌋,在第⌊log₂i⌋ + 1层。它只适合完全二叉树。链式存储让每个结点记下左右孩子的地址,就是二叉链表:n个结点有n + 1个空指针;经常要找双亲时加一格,成三叉链表。下一步二叉树存好了,怎么把每个结点都走一遍?