二叉樹的一些概念
二叉樹就是每個結(jié)點最多有兩個子樹的樹形存儲結(jié)構(gòu)。先上圖，方便后面分析。
1 滿二叉樹和完全二叉樹
上圖就是典型的二叉樹，其中左邊的圖還叫做滿二叉樹，右邊是完全二叉樹。然后我們可以得出結(jié)論，滿二叉樹一定是完全二叉樹，但是反過來就不一定。滿二叉樹的定義是除了葉子結(jié)點，其它結(jié)點左右孩子都有,深度為k的滿二叉樹，結(jié)點數(shù)就是2的k次方減1。完全二叉樹是每個結(jié)點都與深度為k的滿二叉樹中編號從1到n一一對應(yīng)。
2 樹的深度
樹的最大層次就是深度，比如上圖，深度是4。很容易得出，深度為k的樹，擁有的最大結(jié)點數(shù)是2的k次方減1。
3 樹的孩子，兄弟，雙親
上圖中，B,C是A的孩子，B,C之間互為兄弟，A是B,C的雙親。
二如何創(chuàng)建二叉樹
先說說二叉樹的存儲結(jié)構(gòu)，跟很多其它模型一樣，也有順序和鏈?zhǔn)絻煞N方式。前者雖然使用簡單，但是存在浪費空間的問題，舉個例子，下圖的二叉樹，用順序的方式存儲(0表示空，沒有子樹)是:
1 2 3 4 5 6 7 0 0 0 0 8 0 0 0
是不是相當(dāng)浪費空間呢。
鏈?zhǔn)浇Y(jié)構(gòu)可以定義如下:
typedef struct _BiTNode { int data; _BiTNode *leftChild; _BiTNode *rightChild; }BiTNode, *pBiTree; 然后就可以寫一個函數(shù)來創(chuàng)建二叉樹，過程是在控制臺輸入a表示退出當(dāng)前這一層,不再為該層創(chuàng)建左右孩子。輸入其它字母表示繼續(xù)創(chuàng)建。比如下面的輸入序列：
創(chuàng)建了如下結(jié)構(gòu)的二叉樹,
每個結(jié)點里的數(shù)值是隨機(jī)生成的小于100的數(shù)字。同時我也寫了一個自動的命令序列函數(shù)，方便測試，不用手動輸入，非自動和自動創(chuàng)建的函數(shù)如下:
//創(chuàng)建二叉樹, 先序順序 int CreateBiTree(pBiTree *root) { char ch = 0; fflush(stdin); if ((ch = getchar()) == 'a')//控制樹的結(jié)構(gòu) { *root = NULL; } else { *root = (BiTNode *)malloc(sizeof(BiTNode)); if (!(*root)) { return RET_ERROR; } (*root)->data = GetRandom(); CreateBiTree(&(*root)->leftChild); CreateBiTree(&(*root)->rightChild); } return RET_OK; } int g_i = 0; //創(chuàng)建二叉樹,自動執(zhí)行，方便測試 int CreateBiTreeAuto(pBiTree *root) { char szOrder[] = "bbaabaa"; char ch = 0; if (szOrder[g_i++] == 'a')//控制樹的結(jié)構(gòu) { *root = NULL; } else { *root = (BiTNode *)malloc(sizeof(BiTNode)); if (!(*root)) { return RET_ERROR; } (*root)->data = GetRandom(); CreateBiTreeAuto(&(*root)->leftChild); CreateBiTreeAuto(&(*root)->rightChild); } return RET_OK; } 三遍歷順序
先序遍歷
先序遍歷是先訪問根結(jié)點，再左子樹，再右子樹，比如圖1中的右圖，先序遍歷的輸出如下:
A,B,D,H,I,E,J,K,C,F,G
根據(jù)上面的思想，很容易用遞歸的形式寫出先序遍歷的代碼：
//先序遍歷 int PreOrderVisitTree(pBiTree T, VisitType pFuncVisit) { if (T) { (*pFuncVisit)(T->data); if (PreOrderVisitTree(T->leftChild, pFuncVisit) == RET_OK) { if (PreOrderVisitTree(T->rightChild, pFuncVisit) == RET_OK) { return RET_OK; } } return RET_ERROR; } else { return RET_OK; } } 中序遍歷和后序遍歷
有了先序的經(jīng)驗，這兩個就很好理解了，中序是先訪問左子樹, 再根結(jié)點，再右子樹, 后序是先訪問左子樹, 再右子樹，再根結(jié)點。代碼更容易，只要改一下調(diào)用順序就可以了。
不過我這里給出一種非遞歸的實現(xiàn)。遞歸固然是清晰明了，但是存在效率低的問題，非遞歸的方案用棧結(jié)構(gòu)來存結(jié)點信息，通過出棧訪問來遍歷二叉樹。它思想是這樣的，當(dāng)棧頂中的指針非空時，遍歷左子樹，也就是左子樹根的指針進(jìn)棧。當(dāng)棧頂指針為空時，應(yīng)退至上一層，如果是從左子樹返回的，訪問當(dāng)前層，也就是棧頂中的根指針結(jié)點。如果是從右子樹返回，說明當(dāng)前層遍歷完畢，繼續(xù)退棧。代碼如下:
//中序遍歷, 非遞歸實現(xiàn) int InOrderVisitTree(pBiTree T, VisitType pFuncVisit) { ponyStack binaryTreeStack; InitStack(&binaryTreeStack, 4); Push(&binaryTreeStack, &T); pBiTree pTempNode; while (!IsEmptyStack(binaryTreeStack)) { while((GetTop(binaryTreeStack, &pTempNode) == RET_OK) && (pTempNode != NULL)) { Push(&binaryTreeStack, &(pTempNode->leftChild)); } Pop(&binaryTreeStack, &pTempNode); if (!IsEmptyStack(binaryTreeStack)) { Pop(&binaryTreeStack, &pTempNode); (*pFuncVisit)(pTempNode->data); Push(&binaryTreeStack, &(pTempNode->rightChild)); } } return RET_OK; } 代碼下載地址:http://xiazai.VeVB.COm/201701/yuanma/BinaryTreeDemo-master(VeVB.COm).rar
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
圖片精選
