二叉樹(shù)的諸多操作往往是通過(guò)遞歸調(diào)用來(lái)實(shí)現(xiàn)的，這就決定，不能只通過(guò)main函數(shù)實(shí)現(xiàn)全部過(guò)程，其中還需要調(diào)用main外定義的函數(shù)。也因此，對(duì)main調(diào)用外定義的函數(shù)的參數(shù)傳遞，就有了嚴(yán)格的要求。在網(wǎng)上查找很多關(guān)于二叉樹(shù)建立的程序，但直接拷貝在自己計(jì)算機(jī)上運(yùn)行卻發(fā)現(xiàn)不少錯(cuò)誤，無(wú)法編譯通過(guò)。以下有關(guān)代碼在VS2010上編譯通過(guò)，不涉及二叉樹(shù)的全部操作，本文著重通過(guò)二叉樹(shù)的創(chuàng)建過(guò)程說(shuō)明遞歸實(shí)現(xiàn)與二重指針的相關(guān)問(wèn)題。

1、二叉樹(shù)的定義

二叉樹(shù)的定義結(jié)構(gòu)通常為如下形式：

typedef struct Node

{

char ch;

struct Node *lchild,*rchild;

}Node,*BTree;

Node一般可用來(lái)定義二叉樹(shù)節(jié)點(diǎn)，而*BTree可用來(lái)定義指向二叉樹(shù)(根節(jié)點(diǎn))的指針。

2、內(nèi)存動(dòng)態(tài)分配

采用內(nèi)存動(dòng)態(tài)分配需要用到malloc函數(shù)。值得注意的是，該函數(shù)在成功開(kāi)辟新的內(nèi)存時(shí)，默認(rèn)返回void*指針(即未指定指針)，因此需要強(qiáng)制轉(zhuǎn)換成Node*形式，其調(diào)用形式如：(Node*)malloc(sizeof(Node))

3、遞歸調(diào)用

因?yàn)檫f歸調(diào)用的需要，二叉樹(shù)的一些操作需要獨(dú)立作為一個(gè)函數(shù)。但是，這些函數(shù)是在main中調(diào)用，因此傳遞的參數(shù)和返回的值的處理是非常重要的。另外注意，對(duì)二叉樹(shù)的操作，首先就需要知道二叉樹(shù)的入口，即指向二叉樹(shù)的指針，也即指向二叉樹(shù)根節(jié)點(diǎn)的指針。因此，所傳遞的參數(shù)，則為指向根節(jié)點(diǎn)的指針。又因?yàn)樯婕胺峙鋬?nèi)存的操作，必須傳遞二級(jí)指針才能將實(shí)參指向所分配的內(nèi)存，否則是形參指向了內(nèi)存塊，當(dāng)函數(shù)調(diào)用結(jié)束時(shí)，不復(fù)存在，這在有遞歸調(diào)用的函數(shù)里，采用返回值也是不起作用，同樣在一輪調(diào)用結(jié)束后被銷毀。因此子函數(shù)的參數(shù)形式為二重指針。

如下程序，CreateTree函數(shù)可以是由返回值，也可以不具有返回值(因?yàn)閭鬟f的是地址)。在main函數(shù)中作了測(cè)試，返回的值為二叉樹(shù)根節(jié)點(diǎn)的值。

Node* CreateTree(Node** pTree)

{

char chr;

scanf("%c",&chr);

if(chr=='#')

{

(*pTree)=NULL;

}

else

{

if(!((*pTree)=(Node*)malloc(sizeof(Node))))

{

exit(OVERFLOW);

//#define OVERFLOW -2

}

(*pTree)->ch=chr;

CreateTree(&((*pTree)->lchild));

CreateTree(&((*pTree)->rchild));

}

return *pTree;

}

void main()

{

Node *pRoot;

Node *test;

char ch;

printf("現(xiàn)在開(kāi)始創(chuàng)建二叉樹(shù)...輸入N結(jié)束\n");

test=CreateTree(&pRoot);

//傳遞指針的地址

//printf("所創(chuàng)建的二叉樹(shù)為：\n");

//PrintBinaryTree(test);

//while(1);

}

附注：測(cè)試程序

#include

#include

#define OVERFLOW -2

//定義二叉樹(shù)節(jié)點(diǎn)

typedef struct Node

{

char ch;

struct Node *lchild,*rchild;

}Node,*BTree;

//Node *pRoot=NULL;

//輸出二叉樹(shù)函數(shù)

void PrintBinaryTree(Node *Tree)

{

if(Tree==NULL)

return;

//printf("%c-->",Tree->ch);

PrintBinaryTree(Tree->lchild);

printf("%c-->",Tree->ch);

PrintBinaryTree(Tree->rchild);

}

//創(chuàng)建二叉樹(shù)

Node* CreateTree(Node** pTree)

{

char chr;

scanf("%c",&chr);

if(chr=='#')

{

(*pTree)=NULL;

}

else

{

if(!((*pTree)=(Node*)malloc(sizeof(Node))))

{

exit(OVERFLOW);

}

(*pTree)->ch=chr;

CreateTree(&((*pTree)->lchild));//(*pTree)->lchild為Node *變量，而參數(shù)則是Node **變量，則需要&取址，否則形參無(wú)法保留*lchild值

CreateTree(&((*pTree)->rchild));

}

return *pTree;

}

void main()

{

Node *treehead;

Node *test;

//Node? *bitree=NULL;

char ch;

printf("現(xiàn)在開(kāi)始創(chuàng)建二叉樹(shù)...輸入N結(jié)束\n");

test=CreateTree(&treehead);

printf("所創(chuàng)建的二叉樹(shù)為：\n");

PrintBinaryTree(test);

while(1);

}

相關(guān)閱讀：

總結(jié)

以上是生活随笔為你收集整理的linux二重进程,二叉树递归实现与二重指针的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。