= 1)層最多有2^(i - 1)..."/>
您好,登錄后才能下訂單哦!
myTree.h
#ifndef MYTREE_H_INCLUDED #define MYTREE_H_INCLUDED /* 二叉樹性質(zhì): 在二叉樹上的第i(i >= 1)層最多有2^(i - 1)個(gè)節(jié)點(diǎn)。 深度為k(K >= 1)的二叉樹最多有2^k - 1個(gè)節(jié)點(diǎn) 第i層節(jié)點(diǎn)的序號(hào)從2^(i - 1) - 1到2^i - 1 需要為i的節(jié)點(diǎn)的雙親的序號(hào)為(i + 1) / 2,它的左右孩子的序號(hào)為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; //為樹分配一個(gè)新節(jié)點(diǎn) myTree* getNewTreeNode(); //初始化樹的根節(jié)點(diǎn) 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é)點(diǎn)不為空說明樹在使用中,需要先銷毀 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é)點(diǎn) printf("%d\t", pTreeRoot->data); preOrderTraverse(pTreeRoot->pLeft); preOrderTraverse(pTreeRoot->pRight); return; } void inOrderTraverse(myTree *pTreeRoot) { if (NULL == pTreeRoot) { return; } inOrderTraverse(pTreeRoot->pLeft); //訪問根節(jié)點(diǎn) printf("%d\t", pTreeRoot->data); inOrderTraverse(pTreeRoot->pRight); return; } void nexOrderTraverse(myTree *pTreeRoot) { if (NULL == pTreeRoot) { return; } nexOrderTraverse(pTreeRoot->pLeft); nexOrderTraverse(pTreeRoot->pRight); //訪問根節(jié)點(diǎn) 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; }
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。