二叉树关键概念理解
二叉树的概念在这里就不进行过多的赘述，那么主要说一下我认为重要的部分，
第一点就是二叉树里面部分概念的理解：
就比如说，你对于如何构建二叉树，掌握的十分深刻，但刷题的时候对于一些题目所给的概念不清楚，导致看不明白题目，这课不好，
二叉树的概念如下图所示,其实都很简单，主要是当给他的名字时，你明不明白。
一颗拥有1000个结点的树度为4，则它的最小深度是？
那么对于二叉树，只掌握这些是远远不够的，我们还需要掌握几个最基本的经典问题，
二叉树的构建
//二叉树
typedef int BTDataType;
typedef struct BTNode
{
BTDataType val;
struct BTNode left;
struct BTNode right;
}BTNode;
BTNode Creat_Node()
{
BTNode Node1 = BuyNode(1);
BTNode Node2 = BuyNode(2);
BTNode Node3 = BuyNode(3);
BTNode Node4 = BuyNode(4);
BTNode Node5 = BuyNode(5);
BTNode Node6 = BuyNode(6);
//BTNode Node7 = BuyNode(7);
Node1->left = Node2;
Node1->right = Node4;
Node2->left = Node3;
Node4->left = Node5;
Node4->right = Node6;
//Node6->right = Node7;
return Node1;
}
BTNode BuyNode(BTDataType x)
{
BTNode node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc fail");
}
node->val = x;
node->left = NULL;
node->right = NULL;
return node;
}
接下来依次介绍
- 求二叉树大小
代码实现：
int BT_Size(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return BT_Size(root->left) + BT_Size(root->right) + 1;
}
或者：
int BT_Size(BTNode* root)
{
return root == NULL ? 0 : BT_Size(root->left) +
BT_Size(root->right) + 1;
}
- 求叶子结点个数
叶子结点有一个特点，那么就是左节点与右节点全为空，只要抓住这一点特点，利于递归，还是很好实现的。
int BT_Leaf_Size(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return BT_Leaf_Size(root->left) +
BT_Leaf_Size(root->right);
}
3.求深度
求二叉树深度可以转化为求左子树的深度，与右子树的深度，然后比比谁的大，然后左子树深度求法又可以分为，求左子树的左子树与右子树的深度，以此类推。
需要注意的是：需要每次存储每次递归的大小， 优化时间
int BT_Depth_Size(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int left_Depth_Size = BT_Depth_Size(root->left);
int right_Depth_Size = BT_Depth_Size(root->right);
return left_Depth_Size > right_Depth_Size ?
BT_Depth_Size(root->left) + 1 :
BT_Depth_Size(root->right) + 1;
}
4.求第k层的结点个数
思路就是首先我们要先找到第k层所在位置，然后每找到一个就利用递归然会去1；
int BT_Size_Levre_k(BTNode root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return BT_Size_Levre_k(root -> left, k - 1) +
BT_Size_Levre_k(root -> right, k - 1);
}
5.寻找值为k的结点
需要注注意的是需要存储每次递归的ret，优化时间
BTNode BTFind_Data_k(BTNode root, int k)
{
if (root == NULL)
{
return NULL;
}
if (root->val == k)
{
return root;
}
BTNode ret1 = BTFind_Data_k(root->left, k);
if (ret1)
{
return ret1;
}
BTNode ret2 = BTFind_Data_k(root->right, k);
if (ret2)
{
return ret2;
}
return NULL;
}
6.层序遍历打印
前序： 根->左子树->右子树
void Prev_Order(BTNode root)
{
if (root == NULL)
{
return;
}
printf("%d ", root->val);
Prev_Order(root->left);
Prev_Order(root->right);
}
中序： 左子树->根->右子树
void In_Order(BTNode root)
{
if (root == NULL)
{
return;
}
In_Order(root->left);
printf("%d ", root->val);
Prev_Order(root->right);
}
后序： 左子树->右子树->根
void Post_Order(BTNode root)
{
if (root == NULL)
{
return;
}
In_Order(root->left);
Prev_Order(root->right);
printf("%d ", root->val);
}
层序 ：一层一层打印
层序打印需要运用到栈，这里不提供栈的实现了，只提供实现层序打印的代码
void Lever_Order(BTNode root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode front = QueueFront(&q);
QueuePop(&q);
printf("%d ", front->val);
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
}
printf("\n");
}
- 判断二叉树是否是完全二叉树
检查是否为完全二叉树，也是利用栈的知识来实现，因为在层序遍历的时候，是出完一层的时候也会在进完下一层，并且顺序是完全按照一层一层从左到右
所以实现思路就为，先找到第一个为空的结点，然后查看他后面的结点是不是为空，如果为空，那么就为完全二叉树，反之不是。
bool BinaryTreeComplete(BTNode root)
{
//层序遍历，从第一个为空开始，向后看是否为空
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)
{
break;
}
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
//检查后面是否为空 ，有非空即不是完全二叉树
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front != NULL)
{
return false;
}
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
}
return true;
}
8.销毁
void BinaryTreeDestory(BTNode* root)//后序顺序释放
{
if (root == NULL)
{
return;
}
BinaryTreeDestory(root->left);
BinaryTreeDestory(root->right);
free(root);
}
还有一些结论：
1：二叉树第i层上的结点数目最多为2i-1(i>=1)
2：深度为k的二叉树至多有2^(k) - 1个结点（k>=1）,叶子节点为 2^(k - 1)
3：包含n个结点的二叉树的高度至少为( log2(n) )+1
4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1
5: 如果度为0结点个数为N0,度为2的个数为N2
那么N0=N2+1；
