二叉树（链式结构）

一、实现方式

在上一章已经知道了树的图形样子，而这里主要讲解以链式结构实现二叉树
二叉树是没有规则的，因此二叉树很难实现插入等操作，更多的是遍历

typedef int BTDataType;
// ⼆叉链
typedef struct BinaryTreeNode
{
struct BinTreeNode* left; // 指向当前结点左孩⼦
struct BinTreeNode* right; // 指向当前结点右孩⼦
BTDataType val; // 当前结点值域
}BTNode;

二、遍历

//前序遍历 — 根左右
void preOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->data);
preOrder(root->left);
preOrder(root->right);
}

//中序遍历 — 左根右
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}

//后序遍历–左右根
void postOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
postOrder(root->left);
postOrder(root->right);
printf("%c ", root->data);
}

// ⼆叉树结点个数
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

// ⼆叉树叶⼦结点个数
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层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)//从最上面开始减，减到第k层
{
return 1;
}
return BinaryTreeLevelKSize(root->left, k – 1)
+ BinaryTreeLevelKSize(root->right, k – 1);
}

//⼆叉树的深度/⾼度
//根节点加上max(左子树，右子树)
int BinaryTreeDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int leftDep = BinaryTreeDepth(root->left);
int rightDep = BinaryTreeDepth(root->right);

return 1 + (leftDep > rightDep ? leftDep : rightDep);
}

// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode* leftFind = BinaryTreeFind(root->left, x);
if (leftFind)
{
return leftFind;
}
BTNode* rightFind = BinaryTreeFind(root->right, x);
if (rightFind)
{
return rightFind;
}
return NULL;
}

// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root)
{
if (*root == NULL)
{
return;
}
BinaryTreeDestory(&((*root)->left));
BinaryTreeDestory(&((*root)->right));
free(*root);
*root = NULL;
}

//层序遍历
typedef struct BTNode* QDataTpe;//这里是把二叉树当作一个元素放进去了
typedef struct QueueNode
{
QDataTpe data;
struct QueueNode* next;
}QueueNode;

typedef struct Queue {
QueueNode* phead;//队头（两层包含，Queue包含了队头，队头又包含了二叉树）
QueueNode* ptail;//队尾
int size;//记录有效数据个数
}Queue;

void LevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
//取队头出队头，打印结点值
BTNode* top = QueueFront(&q);//其返回的是队头中的data
QueuePop(&q);
printf("%c ", top->data);
//将队头结点的非空左右孩子结点入队列
if (top->left)
QueuePush(&q, top->left);
if (top->right)
QueuePush(&q, top->right);
}

QueueDestroy(&q);
}

// 判断⼆叉树是否是完全⼆叉树
//完全二叉树在除了最后一层外的每一层都是完全填满的节点。即，从根节点到倒数第二层，每一层的所有位置都有节点
bool BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
//取队头，出队头
BTNode* top = QueueFront(&q);
QueuePop(&q);
if (top == NULL)
{
break;
}
//队头结点的左右孩子入队列
QueuePush(&q, top->left);
QueuePush(&q, top->right);
}
//队列不为空，继续取队头出队头
//1）队头存在非空结点—-非完全二叉树
//2）队头不存在非空结点—-完全二叉树
while (!QueueEmpty(&q))
{
BTNode* top = QueueFront(&q);
QueuePop(&q);
if (top != NULL)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}