前言
作者：小蜗牛向前冲
名言：我可以接受失败，但我不能接受放弃
如果觉的博主的文章还不错的话，还请点赞，收藏，关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正。
在下面博主将带领大家去探秘二叉树，在讲二叉树之前，我们还要了解在数据结构中的树是这么回事。
一 树的相关概念
1 树的概念
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
- 有一个特殊的结点，称为根结点，根节点没有前驱结点
- 其余节点都是根的子节点，子节点中又可以形成子树，注意：子树是不可相交的。
- 树是由递归形成的
2 树的相关概念
节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为4 |
叶节点或终端节点：度为0的节点称为叶节点； 如上图：I、J、H、C、D.等节点为叶节点 |
非终端节点或分支节点：度不为0的节点； 如上图：B、F、E、G...等节点为分支节点 |
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：B是F的父节点 |
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：F是B的孩子节点 |
兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：F、G是兄弟节点 |
树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为5 |
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推； |
树的高度或深度：树中节点的最大层次； 如上图：树的高度为4 |
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、G互为兄弟节点 |
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先 |
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙 |
森林：由m（m>0）棵互不相交的树的集合称为森林 |
红色重点区分 |
显示详细信息
3 树的表示
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法
表示方式如下：
typedef int DataType; struct Node { struct Node* _firstChild1; // 第一个孩子结点 struct Node* _pNextBrother; // 指向其下一个兄弟结点 DataType _data; // 结点中的数据域 }；
二 二叉树的概念及其结构
1 概念
二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。
2 特殊的二叉树
1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树
3 二叉树的性质
1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2^h-1.
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为n2 ,则有 n0＝n2 ＋1
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log(h+1)(ps： 是log以2
为底，n+1为对数)
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对
于序号为i的结点有：
1. 若i>0，i位置节点的双亲序号：parant = (i-1)/2；i=0，i为根节点编号，无双亲节点
2. 若2i+1eftChild = 2i+1，2i+1>=n否则无左孩子
3. 若2i+2leftChild = 2i+2，2i+2>=n否则无右孩子
我们了解二叉树的性质，我们做一些题目了加深理解吧 ！
这题该如何去解题呢？
我们在看一题目吧！
要深度最小就是所有层都是满的，该树的度为4所以，每个根都有4个孩子节点时深度最小，即是4叉树。
三 二叉树结构的实现
对于二叉树来说其实是有二种结构的，一种是顺序结构，其实也就是堆，我们在上篇博客已经实现了感兴趣的小伙伴可以去看看；另一种结构是链接结构，下面我们重点说明一下链式二叉树是如何构建的，下面我们还对二叉树的各类递归情形做出分享。
1 二叉树链式结构的建树
由于我们刚刚开始接触二叉树，对于建树的操作还不是那么了解，但我们要对于二叉树进行一些基本操作，所以我们可以手动的快速建立二叉树。
代码如下：
//建一个二叉树 BTNode* CreateTree() { BTNode* n1 = (BTNode*)malloc(sizeof(BTNode)); assert(n1); BTNode* n2 = (BTNode*)malloc(sizeof(BTNode)); assert(n2); BTNode* n3 = (BTNode*)malloc(sizeof(BTNode)); assert(n3); BTNode* n4 = (BTNode*)malloc(sizeof(BTNode)); assert(n4); BTNode* n5 = (BTNode*)malloc(sizeof(BTNode)); assert(n5); BTNode* n6 = (BTNode*)malloc(sizeof(BTNode)); assert(n6); //赋值数据 n1->data = 1; n2->data = 2; n3->data = 3; n4->data = 4; n5->data = 5; n6->data = 6; //链接树 n1->left = n2; n1->right = n3; n2->left = n4; n2->right = n5; n4->left = NULL; n4->right = NULL; n5->left = NULL; n5->right = NULL; n3->left = n6; n3->right = NULL; n6->left = NULL; n6->right = NULL; return n1; }
树的形状：
2 二叉树的遍历
二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。二叉树有三种遍历方式：
前序遍历：先遍历根，其次左树，最后右树
中序遍历：先遍历左树，其次根，最后右树
后序遍历：先遍历左树，其次右树，最后根
下面用代码实现：
//前序遍历(根，左，右） void PreTraverseTree(BTNode* root) { if (NULL == root) { printf("NULL "); return; } //根 printf("%d ", root->data); //左 PreTraverseTree(root->left); //右 PreTraverseTree(root->right); } //中序遍历 void MidTraverseTree(BTNode* root) { if (NULL == root) { printf("NULL "); return; } //左 MidTraverseTree(root->left); //根 printf("%d ", root->data); //右 MidTraverseTree(root->right); } //后序遍历 void LastTraverseTree(BTNode* root) { if (NULL == root) { printf("NULL "); return; } //左 LastTraverseTree(root->left); //右 LastTraverseTree(root->right); //根 printf("%d ", root->data); }
下面我们打印一下遍历的路径：
大家可以动手在图中画一画。
3 二叉树的其他问题
下面是二叉树一些常见问题:
我们要求二叉树的有多少个节点，我们又该如何求呢？
对于这里，我们很容易想到遍历二叉树。我们依据这个想法可以写出：dan
int count = 0; //求树有多少个节点 //1遍历求解 void TreeSize(BTNode* root) { if (NULL == root) return; ++count; TreeSize(root->left); TreeSize(root->right); return; }
我们发现没，对于遍历二叉树，那我们就不好返回到底有多少个节点，我们只能通过全局变量count来计算，更为麻烦的是每次统计完成后，我们就要将count 重新置0。
那我们有更好的方法解决这个问题吗?
其实我们可以进行思路的转换 ，将求树的所以节点转换为求左子树的节点+右子树的节点+1(根)。
//2分解成子问题 //总树==左子树+右子树，左树套娃，右树套娃 int TreeSize(BTNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right)+1; }
这种分解成子问题的想法非常重要，大家一定要好好理解。
那么我们又如何去求树的高度呢？
这里我们继续将用到分解成子问题的思路，我们可以将这个问题转换为求左子树高度+1或者右子树高度+1，树的高度就为其中最高的一个。
//求树的高度 int TreeHeight(BTNode* root) { if (root == NULL) return 0; int lh = TreeHeight(root->left); int rh = TreeHeight(root->right); return lh > rh ? lh + 1 : rh + 1; }
我们下面继续思考我们如何求第K层的节点树
继续用子问题分解法，相当于求子树k-1层节点，这个想法是有点神奇的，下面我们画图来理解一下。
// 第K层节点个数 int TreeKLevel(BTNode* root, int k) { assert(k > 0); if (NULL == root) return 0; if (1 == k) return 1; //转变为求子树的k-1层 return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1); }
我们继续求返回x节点，这个我们的思路是先去左树找，没找到就去右数找，在没找到就返回NULL。
BTNode* TreeFind(BTNode* root, BTDataType x) { BTNode* lret,*rret; if (NULL == root) return NULL; if (x == root->data) return root; //去左树找 lret = TreeFind(root->left, x); if (lret) return lret; //左树没找到，就去右树找 rret = TreeFind(root->right, x); if (rret) return rret; //左树和右树都没找到 return NULL; }
