二叉樹(shù)Binary Tree是樹(shù)形結(jié)構(gòu)中最基礎(chǔ)、最重要的一種。每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)分別稱(chēng)為左孩子和右孩子。二叉樹(shù)不僅是數(shù)據(jù)結(jié)構(gòu)課程的核心內(nèi)容也是很多高級(jí)結(jié)構(gòu)如堆、紅黑樹(shù)、B 樹(shù)、線段樹(shù)的基礎(chǔ)。二叉樹(shù)的核心特點(diǎn)每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子左右孩子有嚴(yán)格的順序不能隨意交換天然具有遞歸結(jié)構(gòu)很多操作都可以用遞歸描述二叉樹(shù)的常見(jiàn)術(shù)語(yǔ)根節(jié)點(diǎn)root最上面的節(jié)點(diǎn)葉子節(jié)點(diǎn)leaf沒(méi)有孩子的節(jié)點(diǎn)深度depth從根到某節(jié)點(diǎn)的邊數(shù)高度height從某節(jié)點(diǎn)到最遠(yuǎn)葉子的邊數(shù)滿二叉樹(shù)每一層節(jié)點(diǎn)數(shù)都達(dá)到最大完全二叉樹(shù)除最后一層外都填滿且最后一層節(jié)點(diǎn)靠左排列二叉樹(shù)的應(yīng)用非常廣泛二叉搜索樹(shù)BST堆優(yōu)先隊(duì)列哈夫曼編碼表達(dá)式樹(shù)文件系統(tǒng)目錄結(jié)構(gòu)數(shù)據(jù)庫(kù)索引下面用 C 語(yǔ)言實(shí)現(xiàn)二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)、四種遍歷方式、二叉搜索樹(shù)的增刪查以及幾個(gè)經(jīng)典應(yīng)用。一、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)最常用的存儲(chǔ)方式是鏈?zhǔn)酱鎯?chǔ)。每個(gè)節(jié)點(diǎn)保存數(shù)據(jù)域data左孩子指針left右孩子指針right#include stdio.h #include stdlib.h /* 二叉樹(shù)節(jié)點(diǎn) */ typedef struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; } TreeNode; /* 創(chuàng)建一個(gè)新節(jié)點(diǎn) */ TreeNode *createNode(int value) { TreeNode *node (TreeNode *)malloc(sizeof(TreeNode)); if (node NULL) { return NULL; } node-data value; node-left NULL; node-right NULL; return node; } /* 銷(xiāo)毀整棵樹(shù) */ void destroyTree(TreeNode *root) { if (root NULL) { return; } destroyTree(root-left); destroyTree(root-right); free(root); }destroyTree用的是后序遍歷的思想先銷(xiāo)毀左右子樹(shù)再銷(xiāo)毀自己。順序不能反否則會(huì)訪問(wèn)到已釋放的內(nèi)存。二、二叉樹(shù)的四種遍歷遍歷是二叉樹(shù)最基本的操作。按照訪問(wèn)根節(jié)點(diǎn)的時(shí)機(jī)不同分為前序遍歷Preorder根 → 左 → 右中序遍歷Inorder左 → 根 → 右后序遍歷Postorder左 → 右 → 根層序遍歷Level Order從上到下從左到右逐層訪問(wèn)前三種用遞歸實(shí)現(xiàn)非常簡(jiǎn)單層序遍歷需要借助隊(duì)列。1. 前序遍歷void preorder(TreeNode *root) { if (root NULL) { return; } printf(%d , root-data); /* 訪問(wèn)根 */ preorder(root-left); /* 遍歷左子樹(shù) */ preorder(root-right); /* 遍歷右子樹(shù) */ }2. 中序遍歷void inorder(TreeNode *root) { if (root NULL) { return; } inorder(root-left); /* 遍歷左子樹(shù) */ printf(%d , root-data); /* 訪問(wèn)根 */ inorder(root-right); /* 遍歷右子樹(shù) */ }對(duì)二叉搜索樹(shù)做中序遍歷會(huì)得到一個(gè)升序序列這是 BST 最重要的性質(zhì)之一。3. 后序遍歷void postorder(TreeNode *root) { if (root NULL) { return; } postorder(root-left); postorder(root-right); printf(%d , root-data); }4. 層序遍歷層序遍歷需要借助隊(duì)列。這里復(fù)用之前博客中的循環(huán)隊(duì)列思路但因?yàn)橐娴氖荰reeNode *而不是int所以單獨(dú)定義一個(gè)指針隊(duì)列。/* 指針隊(duì)列用于層序遍歷 */ #define QUEUE_SIZE 1024 typedef struct { TreeNode *data[QUEUE_SIZE]; int front; int rear; int size; } PtrQueue; void initPtrQueue(PtrQueue *q) { q-front 0; q-rear 0; q-size 0; } int ptrQueueEmpty(const PtrQueue *q) { return q-size 0; } int ptrQueueEnqueue(PtrQueue *q, TreeNode *node) { if (q-size QUEUE_SIZE) return 0; q-data[q-rear] node; q-rear (q-rear 1) % QUEUE_SIZE; q-size; return 1; } TreeNode *ptrQueueDequeue(PtrQueue *q) { if (ptrQueueEmpty(q)) return NULL; TreeNode *node q-data[q-front]; q-front (q-front 1) % QUEUE_SIZE; q-size--; return node; } /* 層序遍歷 */ void levelOrder(TreeNode *root) { if (root NULL) return; PtrQueue q; initPtrQueue(q); ptrQueueEnqueue(q, root); while (!ptrQueueEmpty(q)) { TreeNode *cur ptrQueueDequeue(q); printf(%d , cur-data); if (cur-left) ptrQueueEnqueue(q, cur-left); if (cur-right) ptrQueueEnqueue(q, cur-right); } }層序遍歷是很多問(wèn)題的基礎(chǔ)例如求樹(shù)的最大寬度按層打印二叉樹(shù)判斷完全二叉樹(shù)求樹(shù)的最小深度三、二叉樹(shù)的基本屬性1. 求節(jié)點(diǎn)總數(shù)int countNodes(TreeNode *root) { if (root NULL) return 0; return 1 countNodes(root-left) countNodes(root-right); }2. 求葉子節(jié)點(diǎn)數(shù)int countLeaves(TreeNode *root) { if (root NULL) return 0; if (root-left NULL root-right NULL) return 1; return countLeaves(root-left) countLeaves(root-right); }3. 求樹(shù)的高度int treeHeight(TreeNode *root) { if (root NULL) return 0; int leftH treeHeight(root-left); int rightH treeHeight(root-right); return (leftH rightH ? leftH : rightH) 1; }4. 交換左右子樹(shù)void swapChildren(TreeNode *root) { if (root NULL) return; TreeNode *tmp root-left; root-left root-right; root-right tmp; swapChildren(root-left); swapChildren(root-right); }四、二叉搜索樹(shù)BST二叉搜索樹(shù)是最常用的二叉樹(shù)變體。它的定義是左子樹(shù)所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)右子樹(shù)所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)左右子樹(shù)也分別是二叉搜索樹(shù)BST 的核心優(yōu)勢(shì)是查找效率高平均為O(log n)。中序遍歷能得到升序序列。1. 插入TreeNode *bstInsert(TreeNode *root, int value) { if (root NULL) { return createNode(value); } if (value root-data) { root-left bstInsert(root-left, value); } else if (value root-data) { root-right bstInsert(root-right, value); } /* 相等則不插入避免重復(fù) */ return root; }2. 查找TreeNode *bstSearch(TreeNode *root, int value) { if (root NULL || root-data value) { return root; } if (value root-data) { return bstSearch(root-left, value); } return bstSearch(root-right, value); }3. 查找最小值與最大值TreeNode *bstMin(TreeNode *root) { while (root ! NULL root-left ! NULL) { root root-left; } return root; } TreeNode *bstMax(TreeNode *root) { while (root ! NULL root-right ! NULL) { root root-right; } return root; }4. 刪除刪除是 BST 里最復(fù)雜的操作分三種情況刪除葉子節(jié)點(diǎn)直接刪除刪除只有一個(gè)孩子的節(jié)點(diǎn)用孩子替代自己刪除有兩個(gè)孩子的節(jié)點(diǎn)用右子樹(shù)最小值或左子樹(shù)最大值替代再刪除那個(gè)替代節(jié)點(diǎn)TreeNode *bstDelete(TreeNode *root, int value) { if (root NULL) { return NULL; } if (value root-data) { root-left bstDelete(root-left, value); } else if (value root-data) { root-right bstDelete(root-right, value); } else { /* 找到了要?jiǎng)h除的節(jié)點(diǎn) */ /* 情況 1 2最多一個(gè)孩子 */ if (root-left NULL) { TreeNode *tmp root-right; free(root); return tmp; } if (root-right NULL) { TreeNode *tmp root-left; free(root); return tmp; } /* 情況 3兩個(gè)孩子 */ TreeNode *successor bstMin(root-right); root-data successor-data; root-right bstDelete(root-right, successor-data); } return root; }五、由遍歷序列重建二叉樹(shù)這是一道非常經(jīng)典的題目已知前序 中序可以唯一確定一棵二叉樹(shù)已知后序 中序可以唯一確定一棵二叉樹(shù)已知前序 后序不能唯一確定除非是滿二叉樹(shù)1. 由前序和中序重建思路前序的第一個(gè)元素是根在中序中找到根的位置左邊是左子樹(shù)右邊是右子樹(shù)遞歸重建左右子樹(shù)/* 在中序數(shù)組 [inL, inR] 中查找 value 的下標(biāo) */ static int findInInorder(int *inorder, int inL, int inR, int value) { for (int i inL; i inR; i) { if (inorder[i] value) return i; } return -1; } TreeNode *buildFromPreIn(int *preorder, int preL, int preR, int *inorder, int inL, int inR) { if (preL preR || inL inR) { return NULL; } int rootValue preorder[preL]; TreeNode *root createNode(rootValue); int pos findInInorder(inorder, inL, inR, rootValue); int leftSize pos - inL; root-left buildFromPreIn(preorder, preL 1, preL leftSize, inorder, inL, pos - 1); root-right buildFromPreIn(preorder, preL leftSize 1, preR, inorder, pos 1, inR); return root; }2. 由后序和中序重建TreeNode *buildFromPostIn(int *postorder, int postL, int postR, int *inorder, int inL, int inR) { if (postL postR || inL inR) { return NULL; } int rootValue postorder[postR]; TreeNode *root createNode(rootValue); int pos findInInorder(inorder, inL, inR, rootValue); int leftSize pos - inL; root-left buildFromPostIn(postorder, postL, postL leftSize - 1, inorder, inL, pos - 1); root-right buildFromPostIn(postorder, postL leftSize, postR - 1, inorder, pos 1, inR); return root; }測(cè)試int pre[] {1, 2, 4, 5, 3, 6, 7}; int in[] {4, 2, 5, 1, 6, 3, 7}; TreeNode *root buildFromPreIn(pre, 0, 6, in, 0, 6);重建后中序遍歷應(yīng)該輸出4 2 5 1 6 3 7。六、經(jīng)典應(yīng)用一判斷完全二叉樹(shù)思路用層序遍歷。遇到第一個(gè)空節(jié)點(diǎn)后后面不能再出現(xiàn)非空節(jié)點(diǎn)如果后面還有非空節(jié)點(diǎn)說(shuō)明不是完全二叉樹(shù)int isCompleteTree(TreeNode *root) { if (root NULL) return 1; PtrQueue q; initPtrQueue(q); ptrQueueEnqueue(q, root); int seenNull 0; /* 是否遇到過(guò)空節(jié)點(diǎn) */ while (!ptrQueueEmpty(q)) { TreeNode *cur ptrQueueDequeue(q); if (cur NULL) { seenNull 1; } else { if (seenNull) { return 0; /* 空節(jié)點(diǎn)之后又出現(xiàn)了非空節(jié)點(diǎn) */ } ptrQueueEnqueue(q, cur-left); ptrQueueEnqueue(q, cur-right); } } return 1; }