二叉树

图论中的定义

二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根节点的度不大于2。有了根节点之后，每个顶点定义了唯一的父节点，和最多2个子节点。然而，没有足够的信息来区分左节点和右节点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。

存储二叉树的方法

在程序设计语言中能用多种方法来构造二叉树。

顺序存储表示

二叉树可以用数组或链接串列来存储，若是满二叉树就能紧凑排列而不浪费空间。如果某个节点的索引为i，（假设根节点的索引为0）则在它左子节点的索引会是，以及右子节点会是；而它的父节点（如果有）索引则为。这种方法更有利于紧凑存储和更好的访问的局部性，特别是在前序遍历中。然而，它需要连续的存储空间，这样在存储高度为h的n个节点所组成的一般树时，将浪费很多空间。在最糟糕的情况下，如果深度为h的二叉树其每个节点都只有右孩子，则该存储结构需要占用的空间，实际上却有h个节点，浪费了不少空间，是顺序存储结构的一大缺点。

存储结构

/* 二叉树的顺序存储表示*/
 #define MAX_TREE_SIZE 100 /* 二叉树的最大节点数*/
 typedef TElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根节点*/

 typedef struct
 {
   int level,order; /* 即节点的层(按[满二叉树]计算) */
 }position;

二叉链表存储表示

在使用记录或存储器地址指针的程序设计语言中，二叉树通常用树结点结构来存储。有时也包含指向唯一的父节点的指针。如果一个结点的子结点个数小于2，一些子结点指针可能为空值，或者为特殊的哨兵结点。 
使用链表能避免顺序存储浪费空间的问题，算法和结构相对简单，但使用二叉链表，由于缺乏父链的指引，在找回父节点时需要重新扫描树得知父节点的节点地址。

存储结构

/* 二叉樹的二叉鏈表存儲表示*/
 typedef struct BiTNode
 {
   TElemType data;
   struct BiTNode *lchild,*rchild; /* 左右孩子指針*/
 }BiTNode,*BiTree;

三叉链表存储表示

改进于二叉链表，增加父节点的指引，能更好地实现节点间的访问，不过算法相对复杂。
当二叉树用三叉链表表示时，有N个结点，就会有N+2个空指针。

存储结构

/* 二叉樹的三叉鏈表存儲表示*/
 typedef struct BiTPNode
 {
   TElemType data;
   struct BiTPNode *parent,*lchild,*rchild; /* 父、左右孩子指針*/
 }BiTPNode,*BiPTree;

访问二叉树的方法

我们经常希望访问树中的每一个结点并且查看它的值。有很多常见的顺序来访问所有的结点，而且每一种都有有用的性质。

深度优先遍历

在深度优先级中，我们希望从根结点访问最远的结点。和图的深度优先搜索不同的是，不需记住访问过的每一个结点，因为树中不会有环。前序，中序和后序遍历都是深度优先遍历的特例。参见深度优先搜索。

广度优先遍历

和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。二叉树的广度优先遍历又称按层次遍历。算法借助队列实现。参见广度优先搜索。

存储结构与基本操作

树的二叉链表标记法（孩子兄弟标记法）是树和二叉树转换的介质。

树的二叉链表存储表示

/* 樹的二叉鏈表(孩子—兄弟)存儲表示*/
 typedef struct CSNode
 {
   TElemType data;
   struct CSNode *firstchild,*nextsibling;
 }CSNode,*CSTree;

存储结构

二叉树的二叉线索存储表示：在线索链表上添加一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点。令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点的rchild域的指针均指向头结点，这样就创建了一个双向线索链表。二叉树常采用二叉链表方式存储。
 /* 二叉樹的二叉線索存儲表示*/
 typedef enum{Link,Thread}PointerTag; /* Link(0)：指針，Thread(1)：線索 */
 typedef struct BiThrNode
 {
   TElemType data;
   struct BiThrNode *lchild,*rchild; /* 左右孩子指針*/
   PointerTag LTag,RTag; /* 左右標誌*/
 }BiThrNode,*BiThrTree;