二叉樹---待完善

myTree.h

#ifndef MYTREE_H_INCLUDED
#define MYTREE_H_INCLUDED

/*
二叉樹性質：
在二叉樹上的第i（i >= 1）層最多有2^(i - 1)個節點。
深度為k（K >= 1）的二叉樹最多有2^k - 1個節點
第i層節點的序號從2^(i - 1) - 1到2^i - 1
需要為i的節點的雙親的序號為(i + 1) / 2，它的左右孩子的序號為2i + 1和2i + 2
*/

#undef NULL
#ifdef __cplusplus
    #define NULL 0
#else
    #define NULL ((void *)0)
#endif

typedef struct tag_myTree
{
    int data;
    struct tag_myTree* pLeft;
    struct tag_myTree* pRight;
}myTree;

//為樹分配一個新節點
myTree* getNewTreeNode();
//初始化樹的根節點
void initBiTree(myTree *pTreeRoot);
//銷毀樹----遞歸
void destoryBiTree(myTree *pTreeRoot);
//前序遍歷樹----遞歸
void  preOrderTraverse(myTree *pTreeRoot);
//中序遍歷----遞歸
void inOrderTraverse(myTree *pTreeRoot);
//后序遍歷----遞歸
void nexOrderTraverse(myTree *pTreeRoot);
//獲取樹的深度---遞歸
int getTreeDepth(myTree* pTreeRoot);

//構造一棵樹
void createBiTree(myTree** pTreeRoot);

#endif // MYTREE_H_INCLUDED

myTree.c

#include "myTree.h"


void initBiTree(myTree *pTreeRoot)
{
    //如果根節點不為空說明樹在使用中，需要先銷毀
    if (NULL != pTreeRoot)
    {
        destoryBiTree(pTreeRoot);
    }

    pTreeRoot = NULL;
}

//思考如何使用循環銷毀一棵樹
void destoryBiTree(myTree *pTreeRoot)
{
    if (NULL != pTreeRoot)
    {
        if (NULL != pTreeRoot->pLeft)
        {
            //遞歸，從最后一層向上銷毀左孩子
            destoryBiTree(pTreeRoot->pLeft);
        }
        //能用else if 嗎？？？
        if (NULL != pTreeRoot->pRight)
        {
            destoryBiTree(pTreeRoot->pRight);
        }

        free(pTreeRoot);
        pTreeRoot = NULL;
    }
}

void  preOrderTraverse(myTree *pTreeRoot)
{
    if (NULL == pTreeRoot)
    {
        return;
    }

    //訪問根節點
    printf("%d\t", pTreeRoot->data);
    preOrderTraverse(pTreeRoot->pLeft);
    preOrderTraverse(pTreeRoot->pRight);
    return;
}

void inOrderTraverse(myTree *pTreeRoot)
{
    if (NULL == pTreeRoot)
    {
        return;
    }

    inOrderTraverse(pTreeRoot->pLeft);
    //訪問根節點
    printf("%d\t", pTreeRoot->data);
    inOrderTraverse(pTreeRoot->pRight);

    return;
}

void nexOrderTraverse(myTree *pTreeRoot)
{
    if (NULL == pTreeRoot)
    {
        return;
    }

    nexOrderTraverse(pTreeRoot->pLeft);
    nexOrderTraverse(pTreeRoot->pRight);
    //訪問根節點
    printf("%d\t", pTreeRoot->data);

    return;
}

int getTreeDepth(myTree* pTreeRoot)
{
    int leftDepth;
    int rightDepth;

    if (NULL == pTreeRoot)
    {
        return 0;
    }

    if (NULL != pTreeRoot->pLeft)
    {
        leftDepth = getTreeDepth(pTreeRoot->pLeft);
    }
    else
    {
        leftDepth = 0;
    }

    if (NULL != pTreeRoot->pRight)
    {
        rightDepth = getTreeDepth(pTreeRoot->pLeft);
    }
    else
    {
        rightDepth = 0;
    }

    return ((leftDepth > rightDepth) ? leftDepth + 1 : rightDepth + 1);
}

myTree* getNewTreeNode()
{
    myTree *pNewNode = NULL;

    pNewNode = (myTree*)malloc(sizeof(myTree));
    if (NULL == pNewNode)
    {
        return NULL;
    }

    memset(pNewNode, 0, sizeof(myTree));

    return pNewNode;
}

void createBiTree(myTree** pTreeRoot)
{
    int data;
    myTree *pTmp = NULL;

    scanf("%d", &data);

    if (0 != data)
    {
        pTmp = getNewTreeNode();
        if (NULL == pTmp)
        {
            exit(0);
        }
        pTmp->data = data;

        *pTreeRoot = pTmp;

        createBiTree(&((*pTreeRoot)->pLeft));
        createBiTree(&((*pTreeRoot)->pRight));
    }
}

main.c

#include <stdio.h>
#include "myTree.h"

int main()
{
    myTree *g_TreeRoot = NULL;

    createBiTree(&g_TreeRoot);

    printf("pre:\t");
    preOrderTraverse(g_TreeRoot);
    printf("\nin:\t");
    inOrderTraverse(g_TreeRoot);
    printf("\nnex:\t");
    nexOrderTraverse(g_TreeRoot);
    return 0;
}