【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
前面我們講過雙向鏈表的數據結構。每一個循環節點有兩個指針，一個指向前面一個節點，一個指向後繼節點，這樣所有的節點像一顆顆珍珠一樣被一根線穿在了一起。然而今天我們討論的數據結構卻有一點不同，它有三個節點。它是這樣定義的：
typedef struct _TREE_NODE
{
int data;
struct _TREE_NODE* parent;
struct _TREE_NODE* left_child;
struct _TREE_NODE* right_child;
}TREE_NODE;
typedef struct _TREE_NODE
{
int data;
struct _TREE_NODE* parent;
struct _TREE_NODE* left_child;
struct _TREE_NODE* right_child;
}TREE_NODE; 根據上面的數據結構，我們看到每一個數據節點都有三個指針，分別是：指向父母的指針，指向左孩子的指針，指向右孩子的指針。每一個節點都是通過指針相互連接的。相連指針的關系都是父子關系。那麼排序二叉樹又是什麼意思呢？其實很簡單，只要在二叉樹的基本定義上增加兩個基本條件就可以了：（1）所有左子樹的節點數值都小於此節點的數值；（2）所有右節點的數值都大於此節點的數值。
既然看到了節點的定義，那麼我們並可以得到，只要按照一定的順序遍歷，可以把二叉樹中的節點按照某一個順序打印出來。那麼，節點的創建、查找、遍歷是怎麼進行的呢，二叉樹的高度應該怎麼計算呢？我們一一道來。
1）創建二叉樹節點
TREE_NODE* create_tree_node(int data)
{
TREE_NODE* pTreeNode = NULL;
pTreeNode = (TREE_NODE*)malloc(sizeof(TREE_NODE));
assert(NULL != pTreeNode);
memset(pTreeNode, 0, sizeof(TREE_NODE));
pTreeNode->data = data;
return pTreeNode;
}
TREE_NODE* create_tree_node(int data)
{
TREE_NODE* pTreeNode = NULL;
pTreeNode = (TREE_NODE*)malloc(sizeof(TREE_NODE));
assert(NULL != pTreeNode);
memset(pTreeNode, 0, sizeof(TREE_NODE));
pTreeNode->data = data;
return pTreeNode;
} 分析：我們看到，二叉樹節點的創建和我們看到的鏈表節點、堆棧節點創建沒有什麼本質的區別。首先需要為節點創建內存，然後對內存進行初始化處理。最後將輸入參數data輸入到tree_node當中即可。
2）數據的查找
TREE_NODE* find_data_in_tree_node(const TREE_NODE* pTreeNode, int data)
{
if(NULL == pTreeNode)
return NULL;
if(data == pTreeNode->data)
return (TREE_NODE*)pTreeNode;
else if(data < pTreeNode->data)
return find_data_in_tree_node(pTreeNode->left_child, data);
else
return find_data_in_tree_node(pTreeNode->right_child, data);
}
TREE_NODE* find_data_in_tree_node(const TREE_NODE* pTreeNode, int data)
{
if(NULL == pTreeNode)
return NULL;
if(data == pTreeNode->data)
return (TREE_NODE*)pTreeNode;
else if(data < pTreeNode->data)
return find_data_in_tree_node(pTreeNode->left_child, data);
else
return find_data_in_tree_node(pTreeNode->right_child, data);
} 分析：我們的查找是按照遞歸迭代進行的。因為整個二叉樹是一個排序二叉樹，所以我們的數據只需要和每一個節點依次比較就可以了，如果數值比節點數據小，那麼向左繼續遍歷；反之向右繼續遍歷。如果遍歷下去遇到了NULL指針，只能說明當前的數據在二叉樹中還不存在。
3）數據統計
int count_node_number_in_tree(const TREE_NODE* pTreeNode)
{
if(NULL == pTreeNode)
return 0;
return 1 + count_node_number_in_tree(pTreeNode->left_child)
+ count_node_number_in_tree(pTreeNode->right_child);
}
int count_node_number_in_tree(const TREE_NODE* pTreeNode)
{
if(NULL == pTreeNode)
return 0;
return 1 + count_node_number_in_tree(pTreeNode->left_child)
+ count_node_number_in_tree(pTreeNode->right_child);
} 分析：和上面查找數據一樣，統計的工作也比較簡單。如果是節點指針，那麼直接返回0即可，否則就需要分別統計左節點樹的節點個數、右節點樹的節點個數，這樣所有的節點總數加起來就可以了。
4）按照從小到大的順序打印節點的數據
void print_all_node_data(const TREE_NODE* pTreeNode)
{
if(pTreeNode){
print_all_node_data(pTreeNode->left_child);
printf("%d\n", pTreeNode->data);
print_all_node_data(pTreeNode->right_child);
}
}
void print_all_node_data(const TREE_NODE* pTreeNode)
{
if(pTreeNode){
print_all_node_data(pTreeNode->left_child);
printf("%d\n", pTreeNode->data);
print_all_node_data(pTreeNode->right_child);
}
} 分析：因為二叉樹本身的特殊性，按順序打印二叉樹的函數本身也比較簡單。首先打印左子樹的節點，然後打印本節點的數值，最後打印右子樹節點的數值，這樣所有節點的數值就都可以打印出來了。
5）統計樹的高度
int calculate_height_of_tree(const TREE_NODE* pTreeNode)
{
int left, right;
if(NULL == pTreeNode)
return 0;
left = calculate_height_of_tree(pTreeNode->left_child);
right = calculate_height_of_tree(pTreeNode->right_child);
return (left > right) ? (left + 1) : (right + 1);
}
int calculate_height_of_tree(const TREE_NODE* pTreeNode)
{
int left, right;
if(NULL == pTreeNode)
return 0;
left = calculate_height_of_tree(pTreeNode->left_child);
right = calculate_height_of_tree(pTreeNode->right_child);
return (left > right) ? (left + 1) : (right + 1);
} 分析：樹的高度其實是指所有葉子節點中，從根節點到葉子節點的最大高度可以達到多少。當然，程序中表示得已經很明白了，如果節點為空，那麼很遺憾，節點的高度為0；反之如果左子樹的高度大於右子樹的高度，那麼整個二叉樹的節點高度就是左子樹的高度加上1；如果右子樹的高度大於左子樹的高度，那麼整個二叉樹的高度就是右子樹的高度加上1。計算樹的高度在我們設計平衡二叉樹的時候非常有用，特別是測試的時候，希望大家多多理解，熟練掌握。
總結：
1）二叉樹是所有樹的基礎，後續的平衡二叉樹、線性二叉樹、紅黑樹、復合二叉樹、b樹、b+樹都以此為基礎，希望大家好好學習；
2）二叉樹很多的操作是和堆棧緊密聯系在一起的，如果大家暫時理解不了遞歸，可以用循環或者堆棧代替；
3）實踐出真知，大家可以自己對排序二叉樹的代碼多多練習。不瞞大家說，我個人寫平衡二叉樹不下20多遍，即使這樣也不能保證每次都正確；即使這樣，我每次寫代碼的都有不同的感覺。
