【数据结构篇】~链式二叉树（附源码）

前言（含头文件）

之前的堆是特殊的二叉树是顺序结构的二叉树，而链式二叉树使用队列实现的。
二叉树的实现大部分都是递归，不要说看起来简单，写起来也是有一定难度的。但如果能理解的话，其实写起来也很简单

头文件

#pragma once
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
#include"Queue.h"
#include"Queue.c"
#include<stdbool.h>
typedef int btdatatype;
typedef struct binarytreenode {btdatatype data;struct binarytreenode* left;struct binarytreenode* right;
}btnode;
btnode* btbuynode(btdatatype x);
void preorder(btnode* root);//前序遍历(按照 根左右 的顺序)
void inorder(btnode* root);//中序遍历（按照 左根右）
void postorder(btnode* root);//后序遍历（按照 左右根）
int binarytreesize(btnode* root);// 二叉树结点个数 
int binarytreeleafsize(btnode* root);// 二叉树叶子结点个数
int binarytreelevelksize(btnode* root, int k);// 二叉树第k层结点个数 
int binarytreedepth(btnode* root);//二叉树的深度/高度
btnode* binarytreefind(btnode* root, btdatatype x);// 二叉树查找值为x的结点 
void binarytreedestory(btnode** root);// 二叉树销毁
// 层序遍历--要用队列(先进先出，不用递归了)实现
void LevelOrder(btnode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(btnode* root);

1.链式二叉树的组成

节点由三部分组成
1.数据
2.左节点
3.右节点

2.前、中、后、层序遍历

遍历规则​
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：​
1）前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发生在遍历其左右子树之前​
访问顺序为：根结点、左子树、右子树
2）中序遍历(Inorder Traversal)：访问根结点的操作发生在遍历其左右子树之中（间）​
访问顺序为：左子树、根结点、右子树
3）后序遍历(Postorder Traversal)：访问根结点的操作发生在遍历其左右子树之后​
访问顺序为：左子树、右子树、根结点
4）层序遍历（levelorder）：就是一层一层去遍历

1.前序遍历

void preorder(btnode* root)//前序遍历
{if (root == NULL){return;}printf("%d ", root->data);preorder(root->left);preorder(root->right);
}

2.中序遍历

void inorder(btnode* root)//中序遍历
{if (root == NULL){return;}	inorder(root->left);printf("%d ", root->data);inorder(root->right);
}

3.后序遍历

void postorder(btnode* root)//后序遍历
{if (root == NULL){return;}postorder(root->left);postorder(root->right);printf("%d ", root->data);
}```##  4.层序遍历
![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/d72b3b942ac8419288a832c97cd4cc53.png)```c
// 层序遍历--要用队列(先进先出，不用递归了)实现
void LevelOrder(btnode* root)
{qu q;quinit(&q);//初始化队列qupush(&q, root);//循环入队列取队头数据while (!quempty(&q)){btnode* fornt = qufront(&q);printf("%d ", fornt->data);qupop(&q);//把现在的队头出队列，入左右子树if(fornt->left)qupush(&q, fornt->left);if(fornt->right)qupush(&q, fornt->right);}//出循环时队列为空了qudestroy(&q);//销毁队列
}

3.结点个数以及高度等​

二叉树结点个数以及高度等问题最终都要转换为从左右子树入手！

//二叉树结点个数以及高度等问题最终都要转换为从左右子树入手！
// 二叉树结点个数 (这有个坑，不能直接用size)
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层结点个数(k走到第k层时，k=1)(递归下一层时，k要--)
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);
}
//二叉树的深度/高度
int binarytreedepth(btnode* root)
{if (root == NULL){return 0;}int leftdepth = binarytreedepth( root->left);int rightdepth = binarytreedepth(root->right);return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;} 
// 二叉树查找值为x的结点 （转换为从左右子树里找）
btnode* binarytreefind(btnode* root, btdatatype x)
{if (root == NULL)return NULL;if (x == root->data)return root;btnode*left= binarytreefind(root->left, x);if (left){return left;}btnode*right= binarytreefind(root->right, x);if (right){return right;}return NULL;}
// 二叉树销毁(先销毁左右子树，再销毁根节点）
void binarytreedestory(btnode** root)
{if (*root == NULL)return ;binarytreedestory(&(*root)->left);binarytreedestory(&(*root)->right);//最后再把根节点释放掉free(*root);*root = NULL;
}

4.判断二叉树是否为完全二叉树

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(btnode* root)
{qu q;//初始化quinit(&q);//把当前根节点入队列qupush(&q,root);while (!quempty(&q)){btnode* front = qufront(&q);qupop(&q);//然后把现在的数据出队头if (front == NULL){break;}//循环把左右子树入队列qupush(&q, root->left);qupush(&q, root->right);}//出循环了,但队列不一定是空的//出循环有两种可能// （1.是完全二叉树,直接返回true就行）// （2.不是完全二叉树，// 是因为碰到了非完全二叉树的NULL被break才跳出的循环）//接下来循环取队列里剩下的数据，如果全是空，那就说明是完全二叉树//如果队列里剩下的数据不全为空那就不是完全二叉树while (!quempty(&q)){btnode* front = qufront(&q);qupop(&q);if (front == NULL){qudestroy(&q);return false;}}//销毁qudestroy(&q);return true;
}