前面我們講過(guò)[雙向鏈表][1]的數(shù)據(jù)結(jié)構(gòu)。每一個(gè)循環(huán)節(jié)點(diǎn)有兩個(gè)指針，一個(gè)指向前面一個(gè)節(jié)點(diǎn)，一個(gè)指向后繼節(jié)點(diǎn)，這樣所有的節(jié)點(diǎn)像一顆顆珍珠一樣被一根線穿在了一起。然而今天我們討論的數(shù)據(jù)結(jié)構(gòu)卻有一點(diǎn)不同，它有三個(gè)節(jié)點(diǎn)。它是這樣定義的：

typedef struct _TREE_NODE
{
    int data;
    struct _TREE_NODE* parent;
    struct _TREE_NODE* left_child;
    struct _TREE_NODE* right_child;
}TREE_NODE;

根據(jù)上面的數(shù)據(jù)結(jié)構(gòu)，我們看到每一個(gè)數(shù)據(jù)節(jié)點(diǎn)都有三個(gè)指針，分別是：指向父母的指針，指向左孩子的指針，指向右孩子的指針。每一個(gè)節(jié)點(diǎn)都是通過(guò)指針相互連接的。相連指針的關(guān)系都是父子關(guān)系。那么排序二叉樹又是什么意思呢？其實(shí)很簡(jiǎn)單，只要在二叉樹的基本定義上增加兩個(gè)基本條件就可以了：（1）所有左子樹的節(jié)點(diǎn)數(shù)值都小于此節(jié)點(diǎn)的數(shù)值；（2）所有右節(jié)點(diǎn)的數(shù)值都大于此節(jié)點(diǎn)的數(shù)值。

既然看到了節(jié)點(diǎn)的定義，那么我們并可以得到，只要按照一定的順序遍歷，可以把二叉樹中的節(jié)點(diǎn)按照某一個(gè)順序打印出來(lái)。那么，節(jié)點(diǎn)的創(chuàng)建、查找、遍歷是怎么進(jìn)行的呢，二叉樹的高度應(yīng)該怎么計(jì)算呢？我們一一道來(lái)。

1）創(chuàng)建二叉樹節(jié)點(diǎn)

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;
}

分析：我們看到，二叉樹節(jié)點(diǎn)的創(chuàng)建和我們看到的鏈表節(jié)點(diǎn)、堆棧節(jié)點(diǎn)創(chuàng)建沒(méi)有什么本質(zhì)的區(qū)別。首先需要為節(jié)點(diǎn)創(chuàng)建內(nèi)存，然后對(duì)內(nèi)存進(jìn)行初始化處理。最后將輸入?yún)?shù)data輸入到tree_node當(dāng)中即可。

2）數(shù)據(jù)的查找

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);
}

分析：我們的查找是按照遞歸迭代進(jìn)行的。因?yàn)檎麄€(gè)二叉樹是一個(gè)排序二叉樹，所以我們的數(shù)據(jù)只需要和每一個(gè)節(jié)點(diǎn)依次比較就可以了，如果數(shù)值比節(jié)點(diǎn)數(shù)據(jù)小，那么向左繼續(xù)遍歷；反之向右繼續(xù)遍歷。如果遍歷下去遇到了NULL指針，只能說(shuō)明當(dāng)前的數(shù)據(jù)在二叉樹中還不存在。

3）數(shù)據(jù)統(tǒng)計(jì)

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);
}

分析：和上面查找數(shù)據(jù)一樣，統(tǒng)計(jì)的工作也比較簡(jiǎn)單。如果是節(jié)點(diǎn)指針，那么直接返回0即可，否則就需要分別統(tǒng)計(jì)左節(jié)點(diǎn)樹的節(jié)點(diǎn)個(gè)數(shù)、右節(jié)點(diǎn)樹的節(jié)點(diǎn)個(gè)數(shù)，這樣所有的節(jié)點(diǎn)總數(shù)加起來(lái)就可以了。

4）按照從小到大的順序打印節(jié)點(diǎn)的數(shù)據(jù)

void print_all_node_data(const TREE_NODE* pTreeNode)
{
    if(pTreeNode){
        print_all_node_data(pTreeNode->left_child);
        printf("%dn", pTreeNode->data);
        print_all_node_data(pTreeNode->right_child);
    }
}

分析：因?yàn)槎鏄浔旧淼奶厥庑?，按順序打印二叉樹的函?shù)本身也比較簡(jiǎn)單。首先打印左子樹的節(jié)點(diǎn)，然后打印本節(jié)點(diǎn)的數(shù)值，最后打印右子樹節(jié)點(diǎn)的數(shù)值，這樣所有節(jié)點(diǎn)的數(shù)值就都可以打印出來(lái)了。

5）統(tǒng)計(jì)樹的高度

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);
}

分析：樹的高度其實(shí)是指所有葉子節(jié)點(diǎn)中，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最大高度可以達(dá)到多少。當(dāng)然，程序中表示得已經(jīng)很明白了，如果節(jié)點(diǎn)為空，那么很遺憾，節(jié)點(diǎn)的高度為0；反之如果左子樹的高度大于右子樹的高度，那么整個(gè)二叉樹的節(jié)點(diǎn)高度就是左子樹的高度加上1；如果右子樹的高度大于左子樹的高度，那么整個(gè)二叉樹的高度就是右子樹的高度加上1。計(jì)算樹的高度在我們?cè)O(shè)計(jì)平衡二叉樹的時(shí)候非常有用，特別是測(cè)試的時(shí)候，希望大家多多理解，熟練掌握。

總結(jié)：

1）二叉樹是所有樹的基礎(chǔ)，后續(xù)的平衡二叉樹、線性二叉樹、紅黑樹、復(fù)合二叉樹、b樹、b+樹都以此為基礎(chǔ)，希望大家好好學(xué)習(xí)；

2）二叉樹很多的操作是和堆棧緊密聯(lián)系在一起的，如果大家暫時(shí)理解不了遞歸，可以用循環(huán)或者堆棧代替；

3）實(shí)踐出真知，大家可以自己對(duì)排序二叉樹的代碼多多練習(xí)。不瞞大家說(shuō)，我個(gè)人寫平衡二叉樹不下20多遍，即使這樣也不能保證每次都正確；即使這樣，我每次寫代碼的都有不同的感覺。