求二叉树的高度(BTreeHeight)
先比较一下以下的哪种代码更优：
方案一：
在递归调用BTreeHeight函数之后，并没有对返回值进行保存和比较，而是直接返回了当前节点的左子树和右子树的高度中较大的一个加1。这样的实现虽然能够得到正确的结果，但是效率较低。因为在计算左子树的高度和右子树的高度时，每次都会重复递归调用 BTreeHeight函数
int BTreeHeight(BTNode* root) { if (root == NULL) { return 0; } return BTreeHeight(root->left) > BTreeHeight(root->right) ? BTreeHeight(root->left) + 1 : BTreeHeight(root->right) + 1; }
为了更好地理解方案一的解释，这里写出一个不用三目运算符，但是等价于上述代码的代码
画图理解：
这里其实用到的是分治算法,通常分为三个步骤:
- 分解（Divide）：将原问题划分为若干个规模较小的子问题。这一步通常在递归的过程中进行，直到问题足够简单，可以直接求解。
- 解决（Conquer）：递归地解决子问题。对于每个子问题，如果它的规模足够小，可以直接求解；否则，继续递归地将子问题划分为更小的子问题。
- 合并（Combine）：将子问题的解合并得到原问题的解。这一步通常在递归的回溯过程中进行。
代码实现：
int BTreeHeight(BTNode* root) { if (root == NULL) { return 0; } int h = 0; if (BTreeHeight(root->left) > BTreeHeight(root->right)) { h = BTreeHeight(root->left) + 1; } else { h = BTreeHeight(root->right) + 1; } return h; }
力扣执行：
方案二：
使用了两个变量leftHeight和rightHeight分别保存了左子树和右子树的高度。通过递归调用BTreeHeight函数分别计算左子树和右子树的高度，并将结果保存在这两个变量中。然后比较leftHeight和rightHeight的值，将较大值加1作为当前节点的高度返回。这样的实现避免了重复计算，提高了效率。
int BTreeHeight(BTNode* root) { if (root == NULL) { return 0; } int leftHeight = BTreeHeight(root->left); int rightHeight = BTreeHeight(root->right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight+ 1; }
力扣执行：
二叉树第k层节点个数(BTreeLevelKSize)
子问题:
转换成左子树的第k-1层和右子树的右子树的第k-1层
结束条件:
- k == 1且节点不为空
- 节点为空
代码实现:
int BTreeLevelKSize(BTNode* root, int k) { assert(k > 0); if (root == NULL) return 0; if (k == 1) return 1; return BTreeLevelKSize(root->left, k - 1) + BTreeLevelKSize(root->right, k - 1); }
二叉树查找值为x的节点(BTreeFind)
思路：就如果根节点为空，直接返回NULL，如果找到了就返回x这个节点的地址。
从根节点开始遍历，先从左子树开始找，继续循环上述思路，如果节点不为NULL，但是节点不为x，那也是返回NULL，注意这个NULL是返回上一层的，谁调用它就返回给此函数。之后找右子树，也是一样的思路。
左子树整体找完之后，从右子树整体开始找，重复上述过程。特别强调一个点，return返回的时候不会return到最外层，一定是逐层逐层返回的，没有跳跃的一个过程。
画出递归展开图:
代码实现:
BTNode* BTreeFind(BTNode* root,BTDataType x) { if (root == NULL) return NULL; if (root->data == x) return root; int ret1 = BTreeFind(root->left, x); if (ret1) return ret1; int ret2 = BTreeFind(root->right, x); if (ret2) return ret2; return NULL; }
二叉树的层序遍历(LevelOrder)
层序遍历是用队列实现的，所以要使用队列的结构体，以下的结构体都要用到
typedef struct BTNode* QDataType;//注意这个地方的类型 typedef struct QueueNode { QDataType data; struct QueueNode* next; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue;//表示队列整体,一个是出数据，一个是入数据. typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode;
画处解析图：
队列:先进先出
核心思路:上一层出时带下一层进队列
画处解析图：
队列:先进先出
核心思路:上一层出时带下一层进队列
代码实现:
void LevelOrder(BTNode* root) { Queue q;//在函数内部，定义了一个队列q，并通过调用QueueInit函数对队列进行初始化。 QueueInit(&q); //如果根节点root不为空，将根节点入队，即调用QueuePush函数将root指针插入到队列q中。 if (root) QueuePush(&q,root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q);//首先通过调用QueueFront函数获取队列q的队首元素，并将其赋值给指针变量front QueuePop(&q);//调用QueuePop函数将队首元素出队 printf("%d ", front->data);//通过printf函数打印front指向的节点的数据值 //如果front的左子节点不为空，将左子节点入队， //即调用QueuePush函数将front->left指针插入到队列q中 if (front->left) QueuePush(&q, front->left);//后面这个参数是一个值，不是地址 //如果front的右子节点不为空，将右子节点入队， //即调用QueuePush函数将front->right指针插入到队列q中。 if (front->right) QueuePush(&q, front->right);//后面这个参数是一个值，不是地址 //循环体内的操作完成后，继续下一次循环，直到队列q为空。 } //最后，打印换行符表示层序遍历结束， //并调用QueueDestroy函数销毁队列q，释放内存。 printf("\n"); QueueDestroy(&q); }
二叉树的销毁(BTDestroy)
解析：要先判断根节点本身是否为空，为空就不销毁，返回。
销毁是用到后序遍历的，因为中途删掉了根节点，那么左右指针就找不到了，所以后序遍历适合实现二叉树的销毁。
画图：
void BTDestroy(BTNode* root) { if (root == NULL) { return NULL; } BTDestroy(root->left); BTDestroy(root->right); free(root); }
判断一棵树是否为完全二叉树(BinaryTreeComplete)
非完全二叉树
完全二叉树
思路一样的就不画动图了，只要前面遇到一次空，立即跳出循环，停止插入元素，然后检查后面的元素是否为空，后面全是空就是完全二叉树了。
以下这个二叉树就不是完全二叉树了
代码实现:
bool BTreeComplete(BTNode* root) { Queue q; QueueInit(&q); if (root) 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) { QueueDestroy(&q); return false; } } QueueDestroy(&q); return true; }
执行:
本篇到此结束，感谢来访!
