一、二叉树的结构了解
二叉树是：
- 空树
- 非空：根节点，根节点的左子树、根节点的右子树组成的。
前序： 根 左子树 右子树 --》先根
中序：左子树 根 右子树 --》中根
后序：左子树 右子树 根 --》后根
层序：一层一层访问
二、二叉树的构建
BTNode* BuyNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc fail");
return NULL;
}
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a,int* pi)//pi访问下标
{
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
BTNode* root = BuyNode(a[*pi]);
(*pi)++;
root->left = BinaryTreeCreate(a, pi);
root->right = BinaryTreeCreate(a, pi);
return root;
}
三、二叉树的遍历
**二叉树遍历(Traversal)**是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
（一）前序、中序以及后序遍历
二叉树的遍历有前序/中序/后序的递归结构遍历：
1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树**。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。**
举例：先序遍历
（二）计算二叉树的结点个数
二叉树的结点个数
//int size = 0；//全局变量
//二叉树结点个数--遍历计数
int BTreeSize(BTNode* root)
{
/*if (root->data == NULL)
{
return size;//全部变量
}
++size;
BTreeSize(root->left);
BTreeSize(root->right);
return size;*/
return root == NULL ? 0 : BTreeSize(root->left) + BTreeSize(root->right) + 1;
}
叶子结点个数
//叶子结点个数 (完全二叉树才能只看左边）
int BTreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right==NULL)
{
return 1;
}
return BTreeLeafSize(root->left)
+ BTreeLeafSize(root->right);
}
求二叉树的高度
// 求二叉树的高度
//方法一
//int BTreeHeight(BTNode* root)
//{
// if (root == NULL)
// return 0;
//
// return BTreeHeight(root->left) > BTreeHeight(root->right)
// ? BTreeHeight(root->left) + 1 : BTreeHeight(root->right) + 1;
//}
//方法一：只知道left和right哪个大，然后再计算了一次大的量+1
//注意考虑时间复杂度
int BTreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
int leftHeight = BTreeHeight(root->left);
int rightHeight = BTreeHeight(root->right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
第K层的结点个数
转换成左子树的第k-1层和右子树的第k-1层
int BTreeLevrelKSize(BTNode* root, int k)
{
assert(k > 0);
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return BTreeLevelKSize(root->left, k - 1) + BTreeLevrelKSize(root->right, k - 1);
}
二叉树查找值为x的结点
//二叉树查找值为 x的结点
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BTNode* left = BTreeFind(root->left, x);
if (!left)
return left;
BTNode* right = BTreeFind(root->right, x);
if (!right)
return right;
return NULL;
}
（三）层序遍历
层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历(一层一层访问)。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
创建一个队列的queue.h queue.c略
#include "quue.h"
void LevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if(root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%d ", front->data);
if(front->left)
QueuePush(&q, front->left);
if(front->right)
QueuePush(&q, front->right);
}
printf("\n");
QueueDestroy(&q);
}
int main()
{
BTNode* root = CreatBinaryTree();
LevelOrder(root);
return 0;
}
判断二叉树是否是完全二叉树
// 判断二叉树是否是完全二叉树
int 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)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}
四、二叉树的销毁
//后序
void TreeDestory(root)
{
if(root == NULL)
return;
TreeDestory(root->left);
TreeDestory(root->right);
free(root);
}
