【数据结构】4. 树与二叉树

发布时间：2021-03-31 18:08:55 所属栏目：安全来源：网络整理

导读：目录 4.1 树的基本概念 4.1.1 树的定义 4.1.2 基本术语 4.1.3 树的性质 4.2 二叉树的概念 4.2.1 二叉树的定义及其主要特性（1）二叉树的定义（2）几个特殊的二叉树（3）二叉树的性质 4.2.2 二叉树的存储结构（1）顺序存储结构（2）链式存储结构 4.3 二

前面提到，在有 N 个结点的二叉树中，有 N+1 个空指针。
这是因为每一个叶结点有 2 个空指针，而每一个度为 1 的结点有 1 个空指针，总的空指针数为 (2N_0+N_1)，又有 (N_0=N_2+1)，所以，总
的空指针为 (N_0+N_1+N_2+1 = N+1)。
在二叉树线索化时，通常规定：
若无左子树，令 lchild 指向其前驱结点；若无右子树，令 rchild指向其后继结点。
如图 4-9 所示，还需要增加两个标志域表明当前指针域所指对象是指向左（右）子结点还是直接前驱（后继）。