双链树

双链树是用"每个结点含两个链域"的方式存储的树，典型代表是二叉树，也是把一般树化为二叉树的标准手段。

定义

双链树指每个结点用两个指针域表示的树结构。最常见的是二叉树：每个结点至多有两个子结点，结点含数据域、左孩子指针与右孩子指针，缺失的孩子指针置空。

一般树可用孩子兄弟表示法转化为双链树：每个结点含"第一个孩子"与"下一个兄弟"两个指针，从而任意树都能用二叉树的形式存储与遍历。

性质

• 二叉树第 $i$ 层至多有 $2^{i-1}$ 个结点；$n$ 个结点的二叉树恰有 $n+1$ 个空指针域
• 遍历（先序、中序、后序）把树转化为序列，是树结构应用的基础

示例

表达式 $a+b\times c$ 对应的表达式树是二叉树：根为 $+$，左孩子为 $a$，右孩子为以 $\times$ 为根的子树。

树作为连通无圈图是图论特例，相关概念见子图与补图。