二叉樹---待完善

myTree.h

創(chuàng)新互聯(lián)建站服務項目包括南沙網(wǎng)站建設(shè)、南沙網(wǎng)站制作、南沙網(wǎng)頁制作以及南沙網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，南沙網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務的客戶以成都為中心已經(jīng)輻射到南沙省份的部分城市，未來相信會繼續(xù)擴大服務區(qū)域并繼續(xù)獲得客戶的支持與信任！

#ifndef MYTREE_H_INCLUDED
#define MYTREE_H_INCLUDED

/*
二叉樹性質(zhì)：
在二叉樹上的第i（i >= 1）層最多有2^(i - 1)個節(jié)點。
深度為k（K >= 1）的二叉樹最多有2^k - 1個節(jié)點
第i層節(jié)點的序號從2^(i - 1) - 1到2^i - 1
需要為i的節(jié)點的雙親的序號為(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;

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

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

#endif // MYTREE_H_INCLUDED

myTree.c

#include "myTree.h"


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

    pTreeRoot = NULL;
}

//思考如何使用循環(huán)銷毀一棵樹
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;
    }

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

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

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

    return;
}

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

    nexOrderTraverse(pTreeRoot->pLeft);
    nexOrderTraverse(pTreeRoot->pRight);
    //訪問根節(jié)點
    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;
}

當前文章：二叉樹---待完善
鏈接地址：http://www.muchs.cn/article34/jpcdse.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)網(wǎng)站建設(shè)、云服務器、網(wǎng)站排名、商城網(wǎng)站、網(wǎng)站設(shè)計公司、電子商務

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

成都網(wǎng)頁設(shè)計公司