Skip to content
第4章

4.7 二叉树的存储结构 ​

按编号放进数组 ​

现在要把二叉树放进内存。要存的不只是每个结点的值,还有结点之间的关系:谁是谁的左孩子,谁是谁的右孩子。程序要靠这些关系,从一个结点走到另一个结点。

本节问题
4.5节那棵二叉树有A、B、C、D、G五个结点。把它放进内存,要记下哪些东西?

先看最省事的办法。第2章的顺序表,把元素一个挨一个放进数组。二叉树的结点也可以这样放:按4.6节的编号,几号结点就放进几号格子。先拿6个结点的完全二叉树试:

几号放进几号格。A是1号,放进1号格;F是6号,放进6号格。数组的0号格空着不用,编号和下标就正好相同。

A1B2D4E5C3F6
不用0A1B2C3D4E5F6

数组里只有值。六个格子里,只有A到F六个字母。B的左孩子是谁?数组里没有写。

不用0A1B2C3D4E5F6

可是这棵树的形状并没有丢。只要知道一个结点的编号,就能算出它的孩子在几号格。

学完这一节,你能把二叉树按两种办法放进内存:按编号放进数组,或者用指针连起来;还能说出每种办法适合什么样的二叉树。

选中正文里的任意文字,就可以针对它发表评论