文章目录
- 一、树的概念及结构
- 二、二叉树的概念及结构
- 1.二叉树的概念
- 2.特殊的二叉树
- 3.二叉树的性质
- 三、二叉树的存储
- 顺序存储
- 链式存储
- 四、二叉树的实现
- 1.创建二叉树
- 2.二叉树的遍历
- 前序遍历
- 中序遍历
- 后序遍历
- 层序遍历
- 根据遍历顺序创建二叉树
- 3.二叉树的基本操作
- 1.总结点个数
- 2.二叉树高度
- 3.第K层结点个数
- 4.查找
- 5.判断二叉树是否是完全二叉树
- 4.销毁二叉树
一、树的概念及结构
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。它看起来像一棵倒挂的树，根朝上，而叶子朝下，所以我们把它叫做为树。
- 根结点：没有前驱结点，是当前树中所有结点的祖先。
- 除根节点外，其余结点被分成一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
- 因此，树是递归定义的。
节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的度为3。
叶子节点：度为0的节点称为叶子节点； 如上图：E、F、G为叶子节点。
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点，B是E的父节点。
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的子节点，F是D的子节点。
兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C、D是兄弟节点。
树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为3.
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次/深度； 如上图：树的高度为3
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：E、F互为堂兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林；
二、二叉树的概念及结构
1.二叉树的概念
二叉树是一种特殊的树，每个结点最多只能有两个子结点，即二叉树不存在度大于2的结点。
二叉树可以分为三个部分：根、左子树、右子树，每颗子树又可以划分为这三个部分，一直递归到叶子结点，叶子结点是其本身的根结点。
二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。
二叉树有五种基本形态：空树(B的右子树)、只有根节点(D、E、F)、只有左子树(B)、只有右子树、左右子树(A、C)都存在。
2.特殊的二叉树
满二叉树：除了叶子结点之外的所有结点都有两个子结点。如果一个满二叉树的层数为K，那么结点总数是20 + 21 + … + 2k-1 = 2k - 1个。
完全二叉树：除了最后一层，完全二叉树的每一层从左到右都是满的。也就是说，如果完全二叉树的层数为 h，那么前 h-1 层一定是一个满二叉树。
满二叉树是一种特殊的完全二叉树。
斜二叉树：除了叶子结点外，所有结点都只有一个结点，且是一个方向的结点，要么都只有左结点，要么都只有右结点。
3.二叉树的性质
1.任意二叉树第 i 层最多有2i-1个结点。 ( i ≥ \geq ≥ 1)
2.深度为 h 的任意二叉树的最大结点总数为2h-1。( h ≥ \geq ≥ 1)
3.任意二叉树中，度为0的叶子结点个数永远比度为2的结点个数多一个。
4.对于一个有n个结点的满二叉树，其深度 h= l o g 2 log_2 log2(n+1)（向上取整）三、二叉树的存储
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
顺序存储
二叉树的顺序结构存储就是使用数组来存储。按照层序遍历的顺序（从上到下，从左到右）依次将结点存储在数组中，如果某个结点的左结点或者右结点不存在，则对应的数组的位置就为空，不存储元素。
- 二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
- 二叉树以数组方式存储，父子结点下标的关系：左结点下标 = 2*父结点下标+1，右结点下标 = 2*父结点下标+2，父结点下标 = （任意孩子结点下标-1）/ 2。
- 由上图可以看出，如果是非完全二叉树用数组来表示，则会存在空间浪费，所以使用数组一般只适合表示完全二叉树。而对于一般的二叉树，常用链式存储结构。
链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来存储该结点左孩子和右孩子所在结点的存储地址 。
四、二叉树的实现
接下来我们用链表来实现二叉树的创建与遍历。
二叉树定义
typedef char BTDataType; typedef struct BinaryTreeNode { BTDataType data;//数据 struct BinaryTreeNode* left;//左孩子结点 struct BinaryTreeNode* right;//右孩子结点 }BTNode;1.创建二叉树
以上图为例建立一棵二叉树。
以下代码并不是真正创建二叉树的方式，只是为了方便大家理解，所以手动快速创建一棵简单的二叉树。等后面学完二叉树遍历之后，我们再讲解二叉树的真正创建方式。//动态申请结点 BTNode* BuyNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (NULL == node) { perror("malloc"); return NULL; } node->data = x; node->left = node->right = NULL; return node; } //创建二叉树 BTNode* CreatTree() { BTNode* node1 = BuyNode('A'); BTNode* node2 = BuyNode('B'); BTNode* node3 = BuyNode('C'); BTNode* node4 = BuyNode('D'); BTNode* node5 = BuyNode('E'); BTNode* node6 = BuyNode('F'); node1->left = node2; node1->right = node3; node2->right = node4; node3->left = node5; node4->left = node6; return node1; }2.二叉树的遍历
- 前面我们讲过，二叉树分为：根、左子树、右子树。每个结点的左右子树又可以划分为这三个部分，直到最后一层的叶子结点，叶子结点是其本身的根结点，左右结点为空。根据这一特点，可以看出，二叉树定义是递归式的。
- 二叉树遍历是按照某种特定的规则，依次访问每个节点，并且每个节点只访问一次。根据根节点的访问顺序分为三种遍历方式：前序遍历、中序遍历和后序遍历。
前序遍历
前序遍历的访问顺序：根结点、左子树、右子树。
其中，对于每棵子树，访问顺序也是根结点、左子树、右子树，一直递归到空结点。
相同颜色框的是相同根节点的左右子树比如上图的前序遍历访问顺序为：A B NULL D F NULL NULL NULL C E NULL NULL NULL
而我们一般不打印空结点，所以前序遍历结果为：A B D F C E//前序遍历 void PreOrder(BTNode* root) { if (NULL == root) { //printf("NULL "); return; } printf("%c ", root->data);//打印根节点的值 PreOrder(root->left);//遍历子树 PreOrder(root->right);//遍历右子树 }中序遍历
中序遍历的访问顺序：左子树、根结点、右子树。
还是拿上图示例，中序遍历访问顺序为：NULL B NULL F NULL D NULL A NULL E NULL C NULL
去掉空结点后，中序遍历结果为：B F D A E C
//中序遍历 void InOrder(BTNode* root) { if (NULL == root) { //printf("NULL "); return; } InOrder(root->left); printf("%c ", root->data); InOrder(root->right); }后序遍历
中序遍历的访问顺序：左子树、右子树、根结点。
上图二叉树的后序遍历访问顺序为：NULL NULL NULL F NULL D B NULL NULL E NULL C A
去掉空结点后，后序遍历结果为：F D B E C A//后序遍历 void PostOrder(BTNode* root) { if (NULL == root) { //printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%c ", root->data); }层序遍历
二叉树的层次遍历最好理解，从二叉树的根结点开始，从上到下每一层按照从左到右的顺序遍历。比如上图中二叉树的层序遍历为：A B C D E F
前面三种遍历都是以递归的形式，而层序遍历可以用队列来实现非递归遍历。前面我们已经用C语言写过队列（点击跳转文章）结构，可以在vs中直接将队列的相关代码copy过来使用，在源文件和头文件中直接添加现有项即可。
并将队列中的类型改为二叉树类型
//typedef int QDataType; typedef struct BinaryTreeNode* QDataType;具体过程是：先将当前节点入队列，访问当前结点，再将当前结点出队列。然后将当前结点的左结点和右结点按顺序入队，如果为空结点则不用入队，直到队列为空。
//层序遍历 void LevelOrder(BTNode* root) { assert(root); Queue q; QueueInit(&q); QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); printf("%c ", front->data); if(front->left != NULL) QueuePush(&q, front->left); if (front->right != NULL) QueuePush(&q, front->right); } QueueDestroy(&q); printf("\n"); }根据遍历顺序创建二叉树
数组a存储前序遍历的顺序，比如通过前面我们知道二叉树的前序遍历结果为A B NULL D F NULL NULL NULL C E NULL NULL NULL ；我们将
NULL替换成字符#表示空。数组下标用指针接收，否则递归函数中不会改变实参。//根据前序遍历的顺序二叉树创建 BTNode* BTreeCreate_PreOrder(BTDataType* a, int* pi) { // 通过前序遍历的数组"AB#DF###CE###"构建二叉树 if (a[*pi] == '#') { (*pi)++;//数组下标+1 return NULL; } BTNode* node = BuyNode(a[*pi]);//根据数组元素构建二叉树结点 (*pi)++; node->left = BTreeCreate_PreOrder(a, pi); node->right = BTreeCreate_PreOrder(a, pi); return node; }根据中序/后序顺序来构建二叉树同理。
int main() { char a[] = "AB#DF###CE###"; int i = 0; BTNode* root = BTreeCreate_PreOrder(a, &i); //BTNode* root = BTreeCreate(); PreOrder(root); printf("\n"); InOrder(root); printf("\n"); PostOrder(root); printf("\n"); return 0; }3.二叉树的基本操作
在前面二叉树递归遍历的基础上，我们可以实现一些二叉树的基本操作。
1.总结点个数
转换成子问题：二叉树总结点个数=1（根节点个数）+ 左子树的结点个数 + 右子树的节点个数。很容易想到递归。
//二叉树的总结点个数 int BTreeSize(BTNode* root) { if (NULL == root) { return 0; } return 1 + BTreeSize(root->left) + BTreeSize(root->right); }2.二叉树高度
当前树的高度 = 左右子树中比较高的高度+1
//二叉树的高度 int BTreeLevel(BTNode* root) { if (NULL == root)//空结点则返回0 { return 0; } int leftLevel = BTreeLevel(root->left);//左子树的高度 int rightLevel = BTreeLevel(root->right);//右子树的高度 return leftLevel > rightLevel ? leftLevel + 1 : rightLevel + 1; }最好不要写成下面这样，会造成重复递归，判断时遍历左右子树递归两次，返回结果时又递归一次，栈帧开销会很大。
return BTreeLevel(root->left) > BTreeLevel(root->right) ? BTreeLevel(root->left) + 1 : BTreeLevel(root->right) + 1;3.第K层结点个数
求第K层结点个数，转换成子问题：求左子树第K-1层结点个数 + 右子树第K-1层结点个数
//第k层结点的个数 int BTreeLevelKSize(BTNode* root, int k) { assert(k > 0);//默认根节点为第一层，所以不存在第0层 if (NULL == root)//空结点 { return 0; } if (1 == k)//遍历到第k层 { return 1; } return BTreeLevelKSize(root->left, k-1)+BTreeLevelKSize(root->right, k-1); }4.查找
//查找值为x的结点 BTNode* BTreeFind(BTNode* root, BTDataType x) { if (NULL == root) return NULL; if (root->data == x) return root; BTNode* left = BTreeFind(root->left, x); if (left)//左子树找到则返回 return left; //左子树未找到，只可能存在于右子树 return BTreeFind(root->right, x); }5.判断二叉树是否是完全二叉树
完全二叉树按层序走，非空结点一定是连续的。每次将当前结点的左右结点入队列，不用判空，空结点也入队列。遇到第一个空结点时，停止入队，开始判断队列中的元素是否都为空，若出现非空结点，说明不是完全二叉树，反之则是完全二叉树。
//判断二叉树是否是完全二叉树 bool BTreeComplete(BTNode* root) { assert(root); Queue q; QueueInit(&q); QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); //完全二叉树按层序走，非空结点一定是连续的 if (NULL == front)//遍历到第一个空结点则退出循环，进入下个while循环判断 { break; } else { //不为空则将左右孩子结点入队 QueuePush(&q, front->left); QueuePush(&q, front->right); } } //如果是完全二叉树，则队列中元素全是NULL while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); //有非空结点则说明非空结点不是完全连续，说明不是完全二叉树 if (front != NULL) { QueueDestroy(&q);//返回之前及时释放空间,防止内存泄露 return false; } } QueueDestroy(&q); return true; }4.销毁二叉树
根节点最后释放，否则无法访问左右子树。
//二叉树销毁（后序遍历） void BTreeDestroy(BTNode* root) { if (NULL == root) return; BTreeDestroy(root->left); BTreeDestroy(root->right); free(root); root = NULL; }点此跳转二叉树完整代码
