辛星算法教程第一節即二叉樹的遞歸遍歷，辛星二叉樹

辛星算法教程第一節即二叉樹的遞歸遍歷，辛星二叉樹

    我們都知道，二叉樹的遞歸遍歷可以分為三種:前序遍歷、中序遍歷和後序遍歷，其實這三種遍歷方式大同小異，由於都是使用遞歸實現的，因此也比較簡單。

    首先是tree.h文件，代碼如下： 

#ifndef TREE_H
#define TREE_H


#include <stdio.h>
#include <malloc.h>
#include <assert.h>


typedef int ElemType;

typedef struct Btree
{
    ElemType val;
    struct Btree* left;
    struct Btree* right;
}Btree, *Pbtree;

#endif

      然後是tree.c，代碼如下:

#include <stdio.h>
#include <stdlib.h>
#include "tree.h"


/**
 * 獲取某個節點的值信息
 * @param  Pbtree  pNode   節點對應的指針信息
 *
 */
static void BtreeVisit(Pbtree pNode){
    if (NULL != pNode){
        printf("當前節點的值為: %d\n", pNode->val);
    }
}




/**
 * 構造一個tree節點，置左右指針為空，並且返回指向新節點的指針
 * @param  ElemType   值的類型
 * @return Pbtree     指向新節點的指針
 *
 */
static Pbtree BtreeMakeNode(ElemType target){
    Pbtree pNode = (Pbtree) malloc(sizeof(Btree));

    assert( NULL != pNode ); 

    pNode->val   = target;
    pNode->left  = NULL;
    pNode->right = NULL;
    
    return pNode;
}



/**
 * 插入一個節點信息
 * @param  ElemType      要插入的數據
 * @Param  Pbtree*       指向某一個節點的指針
 * @return Pbtree        指向新節點的指針 
 *
 */
Pbtree BtreeInsert(ElemType target, Pbtree* ppTree){
    Pbtree pNode;

    assert( NULL != ppTree ); 

    pNode = *ppTree;
    if (NULL == pNode){
        return *ppTree = BtreeMakeNode(target);
    }

    //相同則不允許插入
    if (pNode->val == target){
        return NULL;
    }else if (pNode->val > target){
        return BtreeInsert(target, &pNode->left);
    }else{
        return BtreeInsert(target, &pNode->right);
    }
}





/**
 * 前序遍歷這個樹
 *
 */
void BtreePreOrder(Pbtree pNode){
    if (NULL != pNode){
        BtreeVisit(pNode);
        BtreePreOrder(pNode->left);
        BtreePreOrder(pNode->right);
    }    
}

int main(int argc, char *argv[]){
    int i;
    int num[] = {21,43,2,6,88,9};
    Pbtree root = NULL; 
    
    for (i=0; i<sizeof(num)/sizeof(int); i++){
        BtreeInsert(num[i], &root);
    }

   
    BtreePreOrder(root);
   
    return 0;
}

　　這裡我們的數據在插入的時候是進行了一定的區分的，如果這個數字比較小，則會插入到左邊，如果大於該數字，則會插入到右邊，我們最終插入的結構應該是這樣的：

      21
2          43
     6          88
         9

按照前序的輸出順序是:21 2 6 9 43 88