本篇博客主要写了如何完成二叉树的前，中，后序遍历，查找特定值的节点，计算最大深度等。都是对二叉树的一些基本操作。
二叉树基本操作头文件
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* 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);
// 判断二叉树是否是完全二叉树
//是返回真否返回假
bool BinaryTreeComplete(BTNode* root);创建一个二叉树
既然要学会对二叉树的操作，那么首要操作自然是要创建一个二叉树，创建一颗二叉树。
下面是我们要创建的一颗二叉树（图里面的N代表的是NULL即空节点）
创建一颗二叉树有两种方法
创建二叉树方法一
可以直接手撕一个二叉树
BTNode* Buynode(char a)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if (newnode == NULL)
{
perror("malloc fai");
return;
}
newnode->data = a;
newnode->left = NULL;
newnode->right = NULL;
}
BTNode* BinaryTreeCreate()
{
//首先要创建一个节点
BTNode* newnode = BuyNode('A');//先创建非空的节点
BTNode* newnnode2 = Buynode('B');
BTNode* newnode3 = BuyNode('C');
BTNode* newnode3 = Buynode('D');
BTNode* newnode4 = Buynode('E');
BTNode* newnode5 = Buynode('F');
BTNode* newnode6 = Buynode('G');
BTNode* newnode7 = Buynode('H');
newnode->left = newnnode2;//将每一个非空节点的左右孩子赋值
newnode->right = newnode3;
newnnode2->left = newnode3;
newnnode2->right = newnode4;
newnode3->left = NULL;//对于叶子节点直接将左右赋值为空
newnode3->right = NULL;
newnode4->left = NULL;
newnode4->right = NULL;
newnode3->left = newnode5;
newnode3->right = newnode6;
newnode5->left = NULL;
newnode5->right = NULL;
newnode6->left = NULL;
newnode6->right = NULL;
//这样我们就手撕了一个二叉树
}当然这种办法不是很灵活，现在还可以通过将一个二叉树前序或是中序后序遍历的结果，放进数组里面。再通过读取数组里面的值创建数组。我先将上面那个二叉树前序遍历的结果写出来。
创建二叉树的方法二
前序遍历结果ABD##E#H##CF##G##
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)//这里的pi指针作用就是用于读取数组的下标
{//这里我们要使用递归的方式去写，所以这里考虑的就是递归的结束出口
if (*pi < n || a[*pi] == '#')//当下标大于数组长度，或是遇到'#'后即代表这里的这个节点应该为空
{
(*pi)++;
return NULL;//我们就将空传递给上一个栈帧
}
BTNode* newnode = Buynode(a[*pi]);//使用数组里面的值创建一个节点
(*pi)++;//现在数组里面上一个值已经被使用了，要使用的下一个值了
newnode->left = BinaryTreeCreate(a, n, pi);//使用递归的方式为这个节点的左节点赋值
newnode->right = BinaryTreeCreate(a, n, pi);//使用递归的方式为这个节点的右节点赋值
return newnode;//最后将头节点返回
}直接这么看代码的话是很难理解的，我下面就将递归展开图画(非完全)出来。
得到二叉树的节点总个数
任然是使用递归来实现。首先我们要考虑到我们要求的是整个二叉树的所有非空节点个数，所以当我们读取到一个非空节点的时候，我们就要往上返回1，直到读取到NULL的时候返回0。
下面是函数实现：
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;//如果节点为空向上返回0
}
//如果这个节点不为空就要去计算这个节点的左右子树有多少节点求出来
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
我们依旧使用递归展开图（非完全）来理解这个代码。
上面的两幅图我都只画了二叉树的一方的子树而且也没有画完请见谅。我也推荐自己去动手画一下这样的展开图能让我们更易于理解递归的运行方式
得到二叉树的叶子节点个数
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
//首先要知道叶子节点也就是没有左右子树的根节点
if (root == NULL)
return 0;//当遇到的节点为空时照旧返回0
if (root->left == NULL && root->right == NULL)
return 1;
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
这里我就不用物理递归展开图了，我使用逻辑展开图来解释。
我们只需要考虑到如果该节点为空节点，自然不是叶子节点返回0，如果该节点是叶子节点返回1，如果该节点既不是空节点，也不是叶子节点，就去这个节点的左右子树里面去寻找。
二叉树第k层节点个数
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
return 0;//和上面的函数一样当所选节点为空时，代表的自然也不是第k层的节点个数。
//对于这个函数的递归我们假设要求的是第4层的节点个数，那么对于第一层而言要求的是第四层的节点个数，对于第二层而言要求的也就是第三层的节点个数（这里将原本的第二层变为了第一层）
//依次而下那么对于原本第三层的节点而言要求的也就是第二层的节点个数
if (k == 1)
return 1;
//如果该节点不满足上面的条件就去该节点的左右子树去寻找。
//这个函数运用了一个相对的概念，对于第三层而言要求的第四层也即是第二层。
//所以当该节点即不为空也不是目标节点的时候我们就直接，去该节点的左右子树去寻找，而对于左右字数而言要找的第k层自然会少1
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}下面我还是使用逻辑递归展开图来表示。
二叉树查找值为x的节点
这里有两种实现的方法，先说思路对于二叉树上的节点，如果该节点为NULL时返回的肯定也是NULL。
如果该节点的值等于我们要寻找的值那就直接返回这个节点指针即可。如果该节点即不是空，也不是我们要寻找的值那么，就要递归使用函数去寻找该节点的左子树或是右子树中是否存在目标节点。
寻找值实现方法一
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
if (BinaryTreeFind(root->left, x))//如果该节点的左子树没有我们要寻找的值那就不返回
return BinaryTreeFind(root->left, x);
if (BinaryTreeFind(root->right, x))//如果我们在根节点的右子树里面找到了要寻找的值
return BinaryTreeFind(root->right, x);//我们就将这个值返回
return NULL;//如果都没有我们就直接返回空
}这种写法是很不推荐的，这种写法对于不大的二叉树是不会有影响的。但是如果这颗树很大呢。我们这里就用一棵三层的树来递归一下上面的这个代码。
下面我给出递归展开图
修改方式也很简单，只需要每一次都将递归结果保留下来即可。
寻找值实现方法二
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;//如果该节点为空直接返回NULL
if (root->data == x)
{
return root;//将满足要求的节点指针返回
}
BTNode* ret = BinaryTreeFind(root->left, x);//去该节点的左子树种寻找是否存在满足条件的节点
if (ret)
return ret;//如果从左子树里面寻找到的值不是空代表找到了直接返回这个节点指针
ret = BinaryTreeFind(root->right, x);//左子树种如果不存在就去右子树种寻找
if (ret)
return ret;
return NULL;//如果左子树和右子树种都不存在则直接返回NULL代表没有找到
}运行截图：
二叉树的前中后序遍历
我们以下面的这棵二叉树举例：
前序遍历也就是我们先打印跟节点的值再去打印左右子树，这里假设空节点会打印N
那么上面的这棵树前序遍历的结果就是：A B D N N E N H N N C F N N G N N
和在数组里面的值一样。
那么中序遍历也就是先访问左子树，在访问根节点，最后方位右子树
那么上面这棵树中序遍历的结果也就是：N D N B N E N H N A N F N C N G N
那么后序遍历也就是先访问左节点，再访问右节点，最后再访问根节点
那么上面的这棵树后续遍历的结果也就是： N N D N N N H E B N N F N N G C A
写出代码之后再来和这些答案作对比。
前序遍历
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%c ", root->data);
BinaryTreePrevOrder(root->left);//去遍历左子树
BinaryTreePrevOrder(root->right);//去遍历右子树
}运行截图：
和我们分析的答案一样
中序遍历
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
BinaryTreeInOrder(root->left);//先去遍历左子树
printf("%c ", root->data);//读取根节点
BinaryTreeInOrder(root->right);//遍历右子树
}运行截图：
依旧和上面的答案一致
后序遍历
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%c ", root->data);
}运行截图：
依旧和上面的答案一样。
二叉树的层序遍历
二叉树的层序遍历，从名字也能看出来要求一层一层的去遍历二叉树。
以上面的那棵二叉树为例它的层序遍历答案也就是 A B C D E F G H。
那么要怎么达成这种效果呢？这里我们就要使用我们队列的机构了，首先队列的特点是先进先出，即你先进入队列中的数据一定是先出来的。下面我画图来解释一下如何运用队列来实现
需要注意队列里面储存的并不是节点而是节点指针，还有就是我们将队列顶部的元素删除释放的并不是，二叉树节点的空间，二叉树的节点任然可以继续访问。下面是代码实现。（如何实现队列请参考我前面的博客）。
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
//既然要使用队列首先我们就要有一个队列
Queue h;
QueueInit(&h);//初始化队列使其能够使用
if (root)//判断根节点是否为空，不为空则将根节点放入队列中
{
QueuePush(&h, root);
}
while (!QueueEmpty(&h))//当队列不为空的时候循环就继续
{
BTNode*front = QueueFront(&h);//获取队顶的元素
QueuePop(&h);//删除队顶的元素
printf("%c ", front->data);
if (front->left)
QueuePush(&h, front->left);//队顶元素的左孩子不为空将左孩子放入队列中
if (front->right)
QueuePush(&h, front->right);//原理同上
}
}
判断二叉树是否为完全二叉树
首先完全二叉树是一种特殊的二叉树，它的每个非叶子节点都有左右两个子节点，并且除了深度最深的层次外，其他层次的节点都是满足节点数最大值的状态。
更具体地说，一棵深度为h的二叉树，如果除了第h层外，其他各层的节点数都达到了最大值，且第h层所有节点都集中在最左边，那么这棵二叉树就是一棵完全二叉树。其中，最大值是2^(h-1)个节点。
那么怎么去判断一颗树是否为完全二叉树呢？我们依旧要依靠队列来实现，
同层序遍历一样我们先将二叉树的节点放入队列中，然后我们获取队顶的元素判断这个元素是否为空（这里的队列即使是空节点我们也需要放入）,如果这个节点为空那么停止放元素去判断，队列中是否存在非空元素，如果队列中还存在非空元素则直接返回false。反之返回true。下面依旧通过画图来解释
如果B的左边还有一个节点并且后面已经没有节点了。此时的二叉树任然是完全二叉树，那么反映到代码中就是在C的后面任然会有一个非空节点，不会对结果造成影响。如果c的左边还有一个孩子，这个孩子自然不会出现在C的后面而是会出现在NULL的后面，那么当进入最后一步的时候，我们就会发现队列中
出现了一个非空的元素证明这不是一颗完全二叉树。
下面是代码实现。
// 判断二叉树是否是完全二叉树
//是返回真否返回假
bool BinaryTreeComplete(BTNode* root)
{
Queue h;//创建一个队列
QueueInit(&h);//初始化队列
QueuePush(&h, root);//将根节点放入队列中
while (!QueueEmpty(&h))
{
BTNode* front = QueueFront(&h);//获取队顶的元素
QueuePop(&h);//删除队顶的元素
if (front == NULL)
break;//如果队顶的元素为空则要进行最后一步判断队列中剩余元素是否为空
else//不为空则将该节点的左右孩子放入队列中
{
QueuePush(&h, front->left);
QueuePush(&h, front->right);
}
}
//进行到这里一定是在队顶遇到了NULL
//需要我们进行最后一步判断队列中是否还存在非空的接待你
while (!QueueEmpty(&h))//在队列为空之前都要进行判断
{
BTNode* front = QueueFront(&h);
QueuePop(&h);//删除队顶元素
if (front)//如果front非空则代表不为完全二叉树
{
return false;
}
}
return true;
}
得到二叉树的最大深度
int maxDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
}//如果这个节点为空，代表不存在这一层返回的是0
int lefthigh = maxDepth(root->left) + 1;//计算左子树的最大深度，并且加上自己这一层
int righhight = maxDepth(root->right) + 1;//原理同上
return lefthigh > righhight ? lefthigh : righhight;//返回深度深的那一层
}这里依旧有另外一种写法就是不记录高度的写法，但是那种写法和在查找那一节所说的缺点是一样的这里也就不写出了。
