我们之前学习了树的遍历体会到了递归的暴力美学。现在我们来实现剩下的二叉树操作关于二叉树我们知道一般有不止一个叶子结点所以这里不讲删除和插入结点的操作因为可以插入和删除结点的位置太多了没有什么意义后面讲红黑树的时候会学到。头文件声明#pragmaonce#includestdio.h#includestdlib.h#includestdbool.htypedefcharBTDataType;//类型重命名//二叉树结点的结构typedefstructBinaryTreeNode{BTDataType data;//数据域structBinaryTreeNode*left;//指向左孩子的指针structBinaryTreeNode*right;//指向右孩子的指针}BTNode;//先序遍历voidPreOrder(BTNode*root);//中序遍历voidInOrder(BTNode*root);//后序遍历voidPostOrder(BTNode*root);//二叉树结点个数intBinaryTreeSize(BTNode*root);//叶子结点个数intBinaryTreeLeafSize(BTNode*root);//二叉树高度intBinaryTreeLevel(BTNode*root);//二叉树第k层结点个数intBinaryTreeLevelkSize(BTNode*root,intk);//查找值为x的结点BTNode*BinaryTreeFind(BTNode*root,BTDataType x);//销毁二叉树voidBinaryTreeDestroy(BTNode**root);//层序遍历voidLevelOrder(BTNode*root);//判断是否为完全二叉树boolCompleteBinaryTree(BTNode*root);我们每个函数实现后都用之前创建好的二叉树来进行简单功能测试同时因为之前在讲树的遍历的时候有说明过详细递归过程这里不再赘述可以参考我之前发布的博客数据结构树的遍历。二叉树结点个数二叉树的总结点个数根结点左子树结点个数右子树结点个数。对于递归式结构的二叉树来说我们就可以去递归遍历它的左右子树如果结点不存在则返回0。代码来说就很简单了//二叉树结点个数intBinaryTreeSize(BTNode*root){//如果结点不存在则直接返回0if(rootNULL){return0;}return1BinaryTreeSize(root-left)BinaryTreeSize(root-right);}往下递归它的左右子树并返回结点个数这个代码就完成了。我们测试一下结果与预期符合说明代码逻辑没什么问题。二叉树叶子结点个数我们知道叶子结点就是度为0也可以说没有左右孩子结点的结点。叶子结点的个数左子树叶子结点个数右子树叶子结点个数。所以我们还是左右子树往下递归去查找我们传进去一个根结点保证它存在如果它的左右结点都不存在为NULL那么就说明这个结点是一个叶子结点返回1如果根结点不存在那就直接返回0没有查找的必要了。函数代码如下//叶子结点个数intBinaryTreeLeafSize(BTNode*root){//根结点不存在无需往下查找if(rootNULL)return0;//根结点存在判断是否为叶子结点if(rootroot-leftNULLroot-rightNULL)return1;//返回左右子树叶子结点之和returnBinaryTreeLeafSize(root-left)BinaryTreeLeafSize(root-right);}我们来测试一下结果符合预期代码逻辑没有什么问题。二叉树的高度二叉树的高度深度实际上就是根结点左右子树高的那个的高度。按图来理解就是这样的因为要比较左右子树的高度所以我们需要两个变量left_level和right_level来存储左右子树的高度然后max来存储高度比较高那个值和根结点相加作为二叉树的高度返回来。同样的如果根结点不存在我们则返回0。代码如下//二叉树高度intBinaryTreeLevel(BTNode*root){if(rootNULL)return0;//存储左右子树高度intleft_levelBinaryTreeLevel(root-left);intright_levelBinaryTreeLevel(root-right);//比较哪个高度高intmaxleft_levelright_level?left_level:right_level;//返回二叉树高度return1max;}我们简单测试一下结果符合预期代码逻辑没什么问题。二叉树第k层的结点个数二叉树第k层结点个数可以这样找因为根结点是第一层所以第k层的结点个数就是根结点的左右子树第k-1层的结点个数左右子树一直往下递归直到变成左右子树第1层的结点个数就可以找到第k层的结点个数了。如果是第一层那么就是根结点返回1如果根结点不存在直接返回0。代码如下//二叉树第k层结点个数intBinaryTreeLevelkSize(BTNode*root,intk){//边界防护if(k0)return0;if(k1root)return1;if(rootNULL)return0;returnBinaryTreeLevelkSize(root-left,k-1)BinaryTreeLevelkSize(root-right,k-1);}我们简单测试一下结果符合预期代码逻辑没什么问题。查找值为x的结点查找这个结点先从根结点开始如果根结点不是则往左右子树开始遍历如果左子树中找到了则不用遍历右子树返回该结点指针没找到则遍历右子树看是否能找到都找不到则说明该结点不存在返回NULL。如果根结点为NULL则不用查找了直接返回NULL。代码如下//查找值为x的结点BTNode*BinaryTreeFind(BTNode*root,BTDataType x){if(root-datax)returnroot;if(rootNULL)returnNULL;//根结点不是从左右子树中去找BTNode*LeftFindBinaryTreeFind(root-left,x);//找到则返回该结点停止从右子树中去查找if(LeftFind)returnLeftFind;BTNode*RightFindBinaryTreeFind(root-right,x);if(RightFind)returnRightFind;//都找不到则返回NULLreturnNULL;}我们简单测试一下结果符合预期说明代码没什么问题。二叉树的销毁因为我们的二叉树是由一个个结点组成的每个结点都是一个一级指针要销毁二叉树我们就需要传过去根结点的地址也就是一个二级指针。希望形参的改变可以影响实参释放后要把root置为NULL如果我们先释放根结点的内存那么就找不到它的左右子树并释放了所以我们可以按左右根的顺序销毁二叉树跟后序遍历一样。如果根结点为空则说明二叉树为空销毁完成直接返回。代码如下/销毁二叉树voidBinaryTreeDestroy(BTNode**root){if(*rootNULL)return;//先释放左右子树//注意传过来的是二级指针BinaryTreeDestroy((*root)-left);BinaryTreeDestroy((*root)-right);//最后释放根结点free(*root);*rootNULL;}层序遍历层序遍历就是按顺序遍历打印每层的结点。如这棵二叉树按层序遍历顺序就是A B C D NULL E F G NULL NULL NULL NULL NULL NULL NULL NULLNULL也可以不打印那么如何来实现呢按照层序遍历顺序来看我们打印完根结点要拿到根结点的左孩子结点打印完再拿到根结点的右孩子结点。打印完再拿到B的左孩子然后右孩子然后是C的左右孩子一直到遍历完整个二叉树。要达成层序遍历我们就需要借助数据结构队来实现。实现思路是这样的我们先把根结点入队然后拿到它的左右孩子不为空则入队列。然后我们取队头元素打印队头元素然后执行出队操作把A出队。然后取队头结点B将B的左右孩子不为空入队。再把B打印一下然后执行出队操作然后再取队头将队头的左右孩子入队列再打印队头然后出队这样一直循环往复直到队列为空层序遍历就结束了。我们把之前实现队列的接口函数的文件添加进去将队列中存放的元素类型改为结点类型BTNode*再包含一下头文件。该函数先定义一个队列初始化和销毁中间写主要思路。我们先把根结点入队保证队列不为空为空则不会执行下列循环队列不为空则执行以下循环操作取队头、入队头左右结点、打印队头、出队。直到队列为空时跳出循环层序遍历结束。代码实现如下//层序遍历voidLevelOrder(BTNode*root){Queue q;QueueInit(q);//根结点入队if(root)QueuePush(q,root);while(!QueueEmpty(q)){//取队头BTNode*topQueueHead(q);//入左右孩子结点if(top-left)QueuePush(q,top-left);if(top-right)QueuePush(q,top-right);//打印队头然后出队printf(%c ,top-data);QueuePop(q);}printf(\n);QueueDestroy(q);}我们简单测试一下结果符合预期代码逻辑没什么问题。判断是否为完全二叉树我们知道完全二叉树的结点和序号是一一对应的关系要判断是否是完全二叉树同样地我们也要借助队列来实现但和层序遍历有所区分的是不管左右结点是否为空我们都要入队列。比如说这棵二叉树很明显不是一棵完全二叉树我们来看入队列的过程先入根结点然后我们入队头的左右结点取出根结点继续入队头的左右结点取出队头下一次取到的就是NULL了此时我们结束第一次循环进入第二次取队头循环我们会发现第二次循环中取到了不为空的结点。接下来我们举个完全二叉树的例子第一次循环中入队头左右结点出队头一直到遇到结点为空的情况是这样的此时队头为空跳出第一次循环进入第二次循环取队头发现全取出来了没有遇到结点不为空的情况。从以上两个例子中我们可以看出来完全二叉树和非完全二叉树在第一次循环中没有差别重点在于第二次循环完全二叉树取队头不会遇到队头不为空的情况而非完全二叉树会。所以在第二次循环中如果遇到top!NULL的情况则说明该树是非完全二叉树返回false。第二次循环顺利结束则说明是完全二叉树返回true。这两次循环条件都是队列不为空。代码如下//判断是否为完全二叉树boolCompleteBinaryTree(BTNode*root){Queue q;QueueInit(q);//根结点入队QueuePush(q,root);//第一次循环while(!QueueEmpty(q)){//取队头BTNode*topQueueHead(q);//取到队头为空跳出循环if(topNULL)break;//入左右孩子结点QueuePush(q,top-left);QueuePush(q,top-right);QueuePop(q);}while(!QueueEmpty(q)){//取队头BTNode*topQueueHead(q);//取到队头不为空说明是非完全二叉树if(top!NULL)returnfalse;QueuePop(q);}QueueDestroy(q);}我们简单测试一下结果符合预期代码没什么问题。