数据结构：二叉树（2）
ps：爆更第二期
前言
普通的树的实用价值比较小，将树更一步特殊化成二叉树，将获得更多的特殊性质。
例如搜索二叉树，红黑树等。
这篇博文主要介绍二叉树的基础知识，进阶版高级二叉树，后续会持续更新。
二叉树的概念
一棵二叉树是结点的一个有限集合，
该集合:
- 或者为空
- 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
老规矩，上图
在上一篇博客中，介绍了度的概念，
二叉树救赎一颗树，如果他的度不超过2，那他就是一颗二叉树。
二叉树的几种情况
我们怎么去认识一颗二叉树呢？
对于任意一颗二叉树，我们都要将其这么看：
根，左子树，右子树
左子树也要看成根，左子树，右子树
为什么这么说呢？读下去，你就懂啦
特殊的二叉树
（1）满二叉树
一棵二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是
说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
也就是说，满二叉树的每一层都要是满的。
（2）完全二叉树
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K
的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对
应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。（堆就是一颗完全二叉树）
也就是说，完全二叉树除了最后一层，其他层都必须是满的，而且，就算最后一层没满，也需要从左到右连续。
二叉树的性质
1.若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2i-1 个结点.
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2n -1 .
3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为 n2,则有 n0 ＝ n2 ＋1
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度h= log(N+1). (ps： 是log以2为底，n+1为对数)
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
- 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
- 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
- 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子
这些都比较好理解，比较难理解的是第三点
对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为 n2,则有 n0 ＝ n2 ＋1
为什么这么说呢？
最初的二叉树假设只有根节点，此时
n0 = 1, n2 = 0
在后续添加节点的过程中，只会出现两种情况
- n0 + 1, n2 + 1
- n0 不变，n2不变
读者可以尝试画图证明一下。
二叉树的存储
二叉树的存储分为两种情况
顺序存储
适合用于完全二叉树，其中堆就是采用顺序存储实现。
传送门：数据结构：堆链式存储
对于普通的二叉树，使用链式存储是最佳的方式。
因为二叉树最多只有两个子节点，所以不用使用左孩子右兄弟表示法，直接用两个指针分别表示左孩子和右孩子即可。struct Node {Node* leftchild;Node* rightchild;DataType val; };
二叉树的遍历
二叉树比较复杂，和之前的线性表遍历不太相同。
二叉树的遍历分为前序遍历，中序遍历，后续遍历，以及层序遍历。
前序遍历：根，左孩子，右孩子
中序遍历：左孩子，根，右孩子
后续遍历：左孩子，右孩子，根
前中后序遍历
作者感觉在这个地方没有讲清楚，十分抱歉
前中后序遍历的实现基于分治思想，使用递归实现（也可用非递归）
这里就到了前面说要把一棵树看成根，左子树，右子树的时候了。
以前序遍历为例，三种顺序遍历类似。
先分治成小问题：遍历根，左子树，右子树。
递归还需要结束条件，也就是最小子问题。
这里的子问题是遇到空树，千万不要想成遇到叶子结点
void prevOrder(TreeNode* root)
{if(root == nullptr)return;cout << root->val << endl;//根节点prevOrder(root->leftchild);//左子树prevOrder(root->rightchild);//右子树
}
利用这张图，可以帮助理解一下前序遍历的递归过程。
中序遍历与后序遍历类似，这里就不详细讲解了。
层序遍历
层序遍历的思路非常的巧妙
层序遍历利用队列实现
首先，将根节点进入队列，
每次将队首元素出队列，队首元素的左右非空子节点入队列
直到队列为空，则层序遍历完毕。
void LevelOrder(TreeNode* root)
{ if(root == nullptr)return;queue<TreeNode*> q;
q.push(root);while(!q.empty())
{TreeNode* front = q.front();q.pop();cout << front->val;if(front->leftchild)q,push(front->childleft);if(front->rightchild)q.push(front->rightchild);
}}
二叉树的节点个数及高度等
依旧是采用分治思想，分解成子问题，用递归的方式来解决问题。
- 二叉树节点个树
其实就是左子树节点个数 + 右子树节点个数 + 1 - 二叉树的高度
其实就是左右子树高度的最大值 + 1 - 二叉树叶子结点的个数
其实就是左子树叶子结点个数 + 右子树叶子结点个数 - 二叉树中查找val = k的节点
其实就是根节点查找，左子树查找，右子树查找
size_t size(Node* root)
{if (root == nullptr)return 0;return size(root->leftchild) + size(root->rightchild) + 1;
}size_t height(Node* root)
{if (root == nullptr)return 0;return max(height(root->leftchild), height(root->rightchild)) + 1;
}size_t size_leaf(Node* root)
{if (root == nullptr)return 0;if (root->leftchild == nullptr && root->rightchild == nullptr)return 1;return size_leaf(root->leftchild) + size_leaf(root->rightchild);
}Node* find(Node* root, DataType val)
{if (root == nullptr)return nullptr;if (root->val == val)return root;Node* left = find(root->leftchild, val);if (left)return left;return find(root->rightchild, val);
}