二叉樹Binary Tree是樹形結(jié)構(gòu)中最基礎(chǔ)、最重要的一種。每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)分別稱為左孩子和右孩子。二叉樹不僅是數(shù)據(jù)結(jié)構(gòu)課程的核心內(nèi)容也是很多高級(jí)結(jié)構(gòu)如堆、紅黑樹、B 樹、線段樹的基礎(chǔ)。二叉樹的核心特點(diǎn)每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子左右孩子有嚴(yán)格的順序不能隨意交換天然具有遞歸結(jié)構(gòu)很多操作都可以用遞歸描述二叉樹的常見術(shù)語根節(jié)點(diǎn)root最上面的節(jié)點(diǎn)葉子節(jié)點(diǎn)leaf沒有孩子的節(jié)點(diǎn)深度depth從根到某節(jié)點(diǎn)的邊數(shù)高度height從某節(jié)點(diǎn)到最遠(yuǎn)葉子的邊數(shù)滿二叉樹每一層節(jié)點(diǎn)數(shù)都達(dá)到最大完全二叉樹除最后一層外都填滿且最后一層節(jié)點(diǎn)靠左排列二叉樹的應(yīng)用非常廣泛二叉搜索樹BST堆優(yōu)先隊(duì)列哈夫曼編碼表達(dá)式樹文件系統(tǒng)目錄結(jié)構(gòu)數(shù)據(jù)庫(kù)索引下面用 C 語言實(shí)現(xiàn)二叉樹的鏈?zhǔn)酱鎯?chǔ)、四種遍歷方式、二叉搜索樹的增刪查以及幾個(gè)經(jīng)典應(yīng)用。一、二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹最常用的存儲(chǔ)方式是鏈?zhǔn)酱鎯?chǔ)。每個(gè)節(jié)點(diǎn)保存數(shù)據(jù)域data左孩子指針left右孩子指針right#include stdio.h #include stdlib.h /* 二叉樹節(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; } /* 銷毀整棵樹 */ void destroyTree(TreeNode *root) { if (root NULL) { return; } destroyTree(root-left); destroyTree(root-right); free(root); }destroyTree用的是后序遍歷的思想先銷毀左右子樹再銷毀自己。順序不能反否則會(huì)訪問到已釋放的內(nèi)存。二、二叉樹的四種遍歷遍歷是二叉樹最基本的操作。按照訪問根節(jié)點(diǎn)的時(shí)機(jī)不同分為前序遍歷Preorder根 → 左 → 右中序遍歷Inorder左 → 根 → 右后序遍歷Postorder左 → 右 → 根層序遍歷Level Order從上到下從左到右逐層訪問前三種用遞歸實(shí)現(xiàn)非常簡(jiǎn)單層序遍歷需要借助隊(duì)列。1. 前序遍歷void preorder(TreeNode *root) { if (root NULL) { return; } printf(%d , root-data); /* 訪問根 */ preorder(root-left); /* 遍歷左子樹 */ preorder(root-right); /* 遍歷右子樹 */ }2. 中序遍歷void inorder(TreeNode *root) { if (root NULL) { return; } inorder(root-left); /* 遍歷左子樹 */ printf(%d , root-data); /* 訪問根 */ inorder(root-right); /* 遍歷右子樹 */ }對(duì)二叉搜索樹做中序遍歷會(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); } }層序遍歷是很多問題的基礎(chǔ)例如求樹的最大寬度按層打印二叉樹判斷完全二叉樹求樹的最小深度三、二叉樹的基本屬性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. 求樹的高度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. 交換左右子樹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); }四、二叉搜索樹BST二叉搜索樹是最常用的二叉樹變體。它的定義是左子樹所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)右子樹所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)左右子樹也分別是二叉搜索樹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)用右子樹最小值或左子樹最大值替代再刪除那個(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; }五、由遍歷序列重建二叉樹這是一道非常經(jīng)典的題目已知前序 中序可以唯一確定一棵二叉樹已知后序 中序可以唯一確定一棵二叉樹已知前序 后序不能唯一確定除非是滿二叉樹1. 由前序和中序重建思路前序的第一個(gè)元素是根在中序中找到根的位置左邊是左子樹右邊是右子樹遞歸重建左右子樹/* 在中序數(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)用一判斷完全二叉樹思路用層序遍歷。遇到第一個(gè)空節(jié)點(diǎn)后后面不能再出現(xiàn)非空節(jié)點(diǎn)如果后面還有非空節(jié)點(diǎn)說明不是完全二叉樹int isCompleteTree(TreeNode *root) { if (root NULL) return 1; PtrQueue q; initPtrQueue(q); ptrQueueEnqueue(q, root); int seenNull 0; /* 是否遇到過空節(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; }