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