二叉树T：一个有穷的结点集合，这个集合可以为空。它是由根节点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。二叉树的子树有左右顺序之分。
特殊二叉树：
斜二叉树
完美二叉树（满二叉树）：都是两个度
完全二叉树不一定是满二叉树，编号一样就行，可以少
二叉树的几个重要性质
一个二叉树第i层的最大节点数为：2^(i-1)，i>=1。
深度为k的二叉树有最大结点总数为：2^k -1,k>=1。
对任何非空二叉树T，若n0表示叶结点的个数，n2是度为2的非叶结点个数，那么两者满足关系n0=n2+1（叶子结点个数等于两个儿子的结点个数+1）
顺序存储结构
最适用：完全二叉树，按从上至下，从左到右顺序存储n个结点的完全二叉树的结点父子关系；
完全二叉树用数组实现的规律：
（1）非根节点的父结点的序号是[i/2]；
（2）结点的左孩子结点序号是2i（若2i<=n，否则没有左孩子）；
（3）结点的右孩子结点序号是2i+1（若2i+1<=n，否则没有右孩子）；
一般二叉树也可以用数组，但会造成空间浪费
链表存储
typedef struct TreeNode *BinTree; typedef BinTree Position; struct TreeNode{ ElementType Data; BinTree Left; BinTree Right; }
二叉树的遍历
（1）先序遍历：访问根节点->先序遍历其左子树->先序遍历其右子树
void PreOrderTraversal( BinTree BT ){ if ( BT ) { printf("%d", BT->Data); PreOrderTraversal ( BT->Left ); PreOrderTraversal ( BT->Right ); } }
（2）中序遍历：中序遍历其左子树->访问根节点->中序遍历其右子树
void InOrderTraversal( BinTree BT ) { if ( BT ) { InOrderTraversal ( BT->Left ); printf("%d", BT->Data); InOrderTraversal ( BT->Right ); } }
（3）后序遍历：后序遍历其左子树->后序遍历其右子树->访问根节点
void PostOrderTraversal( BinTree BT ) { if ( BT ) { PostOrderTraversal ( BT->Left ); PostOrderTraversal ( BT->Right ); printf("%d", BT->Data); } }
确定一个二叉树至少需要两种遍历序列且一定要有中序遍历
二叉树的非递归遍历
（1）中序遍历非递归遍历算法：使用堆栈。遇到一个结点就压栈，并去遍历它的左子树，当左子树遍历结束后，从栈顶弹出这个结点并访问它，然后按其右指针再去中序遍历该结点的右子树
void InOrderTraversal( BinTree BT ) { BinTree T = BT; Stack S = CreatStack (MaxSize ); //创建并初始化堆栈S while ( T || !IsEmpty(S) ) { //树不空或者堆栈不空 while (T) { //一直向左并将沿途结点压入堆栈 Push(S, T); T = T->Left; } if ( !IsEmpty(S) ) { T = Pop(S); //结点弹出堆栈 printf("%5d", T->Data); //（访问）打印结点 T = T->Right; //转向右子树 } } }
（2）先序遍历的非递归遍历算法：遇到一个结点，就把它压栈并访问它，当左子树遍历结束后，从栈顶弹出这个结点，然后按其右指针再去遍历该结点的右子树
void PreOrderTraversal( BinTree BT ) { BinTree T = BT; Stack S = CreatStack (MaxSize ); //创建并初始化堆栈S while ( T || !IsEmpty(S) ) { //树不空或者堆栈不空 while (T) { //一直向左并将沿途结点压入堆栈 printf("%5d", T->Data); //（访问）打印结点 Push(S, T); T = T->Left; } if ( !IsEmpty(S) ) { T = Pop(S); //结点弹出堆栈 T = T->Right; //转向右子树 } } }
层序遍历：从上至下，从左至右
二叉树遍历的核心问题：二维结构的线性化。
从结点访问其左、右儿子结点。同时需要一个堆栈或者队列保存暂时不访问的结点。
队列实现：遍历从根结点开始，首先将根结点入队，然后开始执行循环：结点出队、访问该结点、其左右儿子入队
层序基本过程：先根节点入队，然后：
（1）从队列中取出一个元素
（2）访问该元素所指结点
（3）若该元素所指结点的左、右孩子结点非空，则将其左、右孩子的指针顺序入队
void LevelOrderTraversal( BinTree BT ) { Queue Q; BinTree T; if ( !BT ) return; //若是空树则直接返回 Q = CreatQueue( MaxSize ); //创建并初始化队列Q AddQ ( Q, BT ); //入队 while ( !IsEmptyQ( Q ) ) { T = DeleteQ ( Q ); printf("%d ", T->Data); //访问取出队列结点 if (T->Left) AddQ( Q, T->Left ); //将其左右孩子入队 if (T->Right) AddQ( Q, T->Right ); } }