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

本文名称：二叉树---待完善
当前地址：http://pwwzsj.com/article/jpcdse.html