一.基本概念
每個節(jié)點最多有2棵子樹，左子樹和右子樹，次序不可顛倒
性質： 1.非空二叉樹的第n層上至多有2^(n-1)個元素 2.深度為h的二叉樹至多有2^h - 1個節(jié)點
滿二叉樹：所有終端都在同一層次，且非中斷結點的度數(shù)為2。
在滿二叉樹中若其深度為h，則包括所包含的結點樹必為2^h - 1
完全二叉樹:除了最大的層次即成為一顆滿二叉樹，且層次最大那層的所有結點均向左靠齊，即集中在左面的位置上，不能有空位置。
對于完全二叉樹，設一個結點為i，則其父結點為i/2, 2i為左子節(jié)點，2i + 1為右子節(jié)點
二.存儲結構
順序存儲：將數(shù)據(jù)結構存在一塊固定的數(shù)組中
`
define LENGTH 100
typedef char datatype;
typedef struct node{
datatype data;
int lchild,rchild;
int parent;
}Node;
Node tree[LENGTH];
int length;
int root;
`
雖然在遍歷速度上有一定的優(yōu)勢，但因所占空間比較大，是非主流二叉樹，二叉樹通常以鏈式存儲
鏈式存儲：
`
typedef char datatype;
typedef struct BinNode{
datatype data;
struct BinNode *lchild;
struct BinNode *rchild;
}BinNode;
typedef BinNode *bintree;
`
三.二叉樹的遍歷
遍歷即將所有結點訪問且僅訪問一次，按照根結點的位置不同分為前序遍歷，中序遍歷，后序遍歷：
前序遍歷： 根結點-> 左子結點 - >右子結點 中序遍歷：左子結點 - > 根結點 ->右子結點 后序遍歷： 左子結點 - >右子結點 - > 根結點
e.g.:
前序遍歷：abdefgc 中序遍歷：debgfac 后序遍歷: edfgbca
