二叉樹
樹
概念 ?
樹是 n(n >= 0) 個結點的有限集合。若 n=0 ，為空樹。
? 在任意一個非空樹中：? ? ? ? ? ?
????????（1）有且僅有一個特定的根結點；
????????（2）當 n>1 時，其余結點可分為 m 個互不相交的有限集合T1、T2......Tm，其中每一個集合又是一個樹，并且稱為子樹。
度、度數、深度
結點擁有子樹的個數稱為結點的度。度為 0 的結點稱為葉結點；度不為 0 稱為分支結點。
樹的度數：指在這顆樹中，最大的結點的度數，稱為樹的度數。
樹的深度（高度）：指從根開始，根為第一層，根的孩子為第二層，即樹的層數，稱為樹的深度。
樹的存儲：順序結構、鏈表結構。
二叉樹（binary tree）
概念
二叉樹是 n 個結點的有限集合，集合要么為空樹，要么由一個根節點和兩棵互不相交的樹組成，這兩棵樹分別稱為根節點的左子樹和右子樹。
特點
（1）每個結點最多兩個子樹。
（2）左子樹和右子樹是有順序的，次序不能顛倒。
（3）如果某個結點只有一個子樹，也要區分左、右子樹。
特殊的二叉樹
（1）斜樹
斜樹分為兩種，一種是所有的結點都只有左子樹，稱為左斜樹；另一種是所有的結點都只有右子樹，稱為右斜樹。
（2）滿二叉樹
滿二叉樹是指所有的分支結點都存在左右子樹，并且葉子都在同一層上。
（3）完全二叉樹
完全二叉樹是指：對于一顆具有 n 個結點的二叉樹按照層序編號，如果編號 i( 1<= i <= n )的結點于同樣深度的滿二叉樹中編號為 i 的結點在二叉樹中的位置完全相同，則此樹稱為完全二叉樹。
特性
（1）在二叉樹的第 i 層上最多有 2^(i-1) 個結點，i >= 1。
（2）深度為 k 的二叉樹至多有 2^k-1 個結點，k >= 1。
（3）任意一個二叉樹T，如果其葉子結點的個數為 N，度數為 M，則 N=M+1。
（4）有 n 個結點的完全二叉樹深度為（logn / log2）+ 1。
層序
前序：根左右。先訪問根結點，再訪問左結點，最后訪問右結點。
中序：左根右。先從根結點開始（不是先訪問根結點），從左結點開始訪問，再訪問根結點，最后訪問右結點。
后序：左右根。先從根結點開始（不是先訪問根結點），從左結點開始訪問，再訪問右結點，最后訪問根結點。
二叉樹結構的程序編寫
1.創建二叉樹
#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef char DATATYPE;
typedef struct BiTNode /* 結點結構 */
{DATATYPE data; /* 結點數據 */struct BiTNode *lchild, *rchild; /* 左右孩子指針 */
} BiTNode;char data[] = "Abd#g###ce#h##fi###";
int ind = 0;
void CreateTree(BiTNode **root)
{char c = data[ind++];if ('#' == c){*root = NULL;return;}else{*root = malloc(sizeof(BiTNode));if (NULL == *root){printf("malloc error\n");*root = NULL;return;}(*root)->data = c;CreateTree(&(*root)->lchild);CreateTree(&(*root)->rchild);}return;
}2.三種不同的遍歷方式
根左右
void PreOrderTraverse(BiTNode *root)
{if (NULL == root){return;}else{printf("%c", root->data);PreOrderTraverse(root->lchild);PreOrderTraverse(root->rchild);}return;
}左根右
void InOrderTraverse(BiTNode *root)
{if (NULL == root){return;}InOrderTraverse(root->lchild);printf("%c", root->data);InOrderTraverse(root->rchild);return;
}左右根
void PostOrderTraverse(BiTNode *root)
{if (NULL == root){return;}PostOrderTraverse(root->lchild);PostOrderTraverse(root->rchild);printf("%c", root->data);return;
}銷毀樹結構
void DestroyTree(BiTNode *root)
{if (NULL == root){return;}DestroyTree(root->lchild);DestroyTree(root->rchild);free(root);root = NULL;return;
}
