二叉树Binary Tree是树形结构中最基础、最重要的一种。每个节点最多有两个子节点分别称为左孩子和右孩子。二叉树不仅是数据结构课程的核心内容也是很多高级结构如堆、红黑树、B 树、线段树的基础。二叉树的核心特点每个节点最多有两个孩子左右孩子有严格的顺序不能随意交换天然具有递归结构很多操作都可以用递归描述二叉树的常见术语根节点root最上面的节点叶子节点leaf没有孩子的节点深度depth从根到某节点的边数高度height从某节点到最远叶子的边数满二叉树每一层节点数都达到最大完全二叉树除最后一层外都填满且最后一层节点靠左排列二叉树的应用非常广泛二叉搜索树BST堆优先队列哈夫曼编码表达式树文件系统目录结构数据库索引下面用 C 语言实现二叉树的链式存储、四种遍历方式、二叉搜索树的增删查以及几个经典应用。一、二叉树的存储结构二叉树最常用的存储方式是链式存储。每个节点保存数据域data左孩子指针left右孩子指针right#include stdio.h #include stdlib.h /* 二叉树节点 */ typedef struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; } TreeNode; /* 创建一个新节点 */ 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用的是后序遍历的思想先销毁左右子树再销毁自己。顺序不能反否则会访问到已释放的内存。二、二叉树的四种遍历遍历是二叉树最基本的操作。按照访问根节点的时机不同分为前序遍历Preorder根 → 左 → 右中序遍历Inorder左 → 根 → 右后序遍历Postorder左 → 右 → 根层序遍历Level Order从上到下从左到右逐层访问前三种用递归实现非常简单层序遍历需要借助队列。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); /* 遍历右子树 */ }对二叉搜索树做中序遍历会得到一个升序序列这是 BST 最重要的性质之一。3. 后序遍历void postorder(TreeNode *root) { if (root NULL) { return; } postorder(root-left); postorder(root-right); printf(%d , root-data); }4. 层序遍历层序遍历需要借助队列。这里复用之前博客中的循环队列思路但因为要存的是TreeNode *而不是int所以单独定义一个指针队列。/* 指针队列用于层序遍历 */ #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); } }层序遍历是很多问题的基础例如求树的最大宽度按层打印二叉树判断完全二叉树求树的最小深度三、二叉树的基本属性1. 求节点总数int countNodes(TreeNode *root) { if (root NULL) return 0; return 1 countNodes(root-left) countNodes(root-right); }2. 求叶子节点数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二叉搜索树是最常用的二叉树变体。它的定义是左子树所有节点的值都小于根节点右子树所有节点的值都大于根节点左右子树也分别是二叉搜索树BST 的核心优势是查找效率高平均为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); } /* 相等则不插入避免重复 */ 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 里最复杂的操作分三种情况删除叶子节点直接删除删除只有一个孩子的节点用孩子替代自己删除有两个孩子的节点用右子树最小值或左子树最大值替代再删除那个替代节点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 { /* 找到了要删除的节点 */ /* 情况 1 2最多一个孩子 */ 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两个孩子 */ TreeNode *successor bstMin(root-right); root-data successor-data; root-right bstDelete(root-right, successor-data); } return root; }五、由遍历序列重建二叉树这是一道非常经典的题目已知前序 中序可以唯一确定一棵二叉树已知后序 中序可以唯一确定一棵二叉树已知前序 后序不能唯一确定除非是满二叉树1. 由前序和中序重建思路前序的第一个元素是根在中序中找到根的位置左边是左子树右边是右子树递归重建左右子树/* 在中序数组 [inL, inR] 中查找 value 的下标 */ 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; }测试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);重建后中序遍历应该输出4 2 5 1 6 3 7。六、经典应用一判断完全二叉树思路用层序遍历。遇到第一个空节点后后面不能再出现非空节点如果后面还有非空节点说明不是完全二叉树int isCompleteTree(TreeNode *root) { if (root NULL) return 1; PtrQueue q; initPtrQueue(q); ptrQueueEnqueue(q, root); int seenNull 0; /* 是否遇到过空节点 */ while (!ptrQueueEmpty(q)) { TreeNode *cur ptrQueueDequeue(q); if (cur NULL) { seenNull 1; } else { if (seenNull) { return 0; /* 空节点之后又出现了非空节点 */ } ptrQueueEnqueue(q, cur-left); ptrQueueEnqueue(q, cur-right); } } return 1; }