看看头文件
这棵二叉树的形状应该是
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef char BTDataType;
typedef struct BTreeNode
{
BTDataType data;
struct BTreeNode* left;
struct BTreeNode* right;
}BTNode;
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);
通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
BTNode* root = (BTNode*)malloc(sizeof(BTNode)); //如果是根据中序和后序遍历呢？，只需要把这两行
root->data = a[(*pi)++]; // 放到root->left和root->right的中间和后面即可
root->left = BinaryTreeCreate(a,n,pi);
root->right = BinaryTreeCreate(a,n,pi);
return root;
}
求树节点的个数
图解
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
return 0;
//1是自己
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
叶子节点的个数
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
求第K层节点的个数
求第K层节点的个数，就是求第K-1层的左右孩子的个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
return 0;
if (k == 1)
return 1;
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
找节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
//不为空就是找到了
BTNode* left= BinaryTreeFind(root->left,x);
if (left != NULL)
return left;
BTNode* right= BinaryTreeFind(root->right,x);
if (right != NULL)
return right;
return NULL;
}
前，中，后序遍历
前序：根，左，右。
中序：左，根，右。
后序：左，右，根。
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->data);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
BinaryTreeInOrder(root->left);
printf("%c ", root->data);
BinaryTreeInOrder(root->right);
}
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%c ", root->data);
}
层序遍历
核心思路：借助队列先进先出的性质，每次出队列的时候，就把它的左右孩子入进去，
孩子为空不入，当队列为空就搞定了，（细节看注释）
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root != NULL)
{
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);
}
判断一颗树是否是完全二叉树
核心思路：出一个节点，入它的左右孩子，这时候孩子是空也要入，当出到空的时候，
只需要判断后面有没有空就可以了，完全二叉树后面肯定是没有空的
int BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root != NULL)
{
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;
}
return true;
QueueDestroy(&q);
}
