---

一、链式二叉树结点定义

typedef char BTDataType;
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType data;
}BTNode;

二、二叉树的遍历

前序 PreOrder：

中序 InOrder（MidOrder）：

后续 PostOrder：

首先需要手动构建一颗二叉树：

BTNode* CreatBinaryTree()
{/*AB				CD				E		F*/BTNode* nodeA = CreateNode('A');BTNode* nodeB = CreateNode('B');BTNode* nodeC = CreateNode('C');BTNode* nodeD = CreateNode('D');BTNode* nodeE = CreateNode('E');BTNode* nodeF = CreateNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}

2.1 前序遍历：根左右

// 二叉树前序遍历
void PreOrder(BTNode* root)
{if (root == NULL){//printf("NULL ");return;}printf("%c ", root->data);PreOrder(root->left);PreOrder(root->right);
}

2.2 中序遍历：左根右

void InOrder(BTNode* root)
{if (root == NULL){//printf("NULL ");return;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}

2.3 后序遍历：左右根

void PostOrder(BTNode* root)
{if (root == NULL){//printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}

2.4 层序遍历

借助于队列实现。推荐使用C++的Queue。

#include "Queue.h"
void LevelOrder(BTNode* root)
{assert(root);Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%c ", front->data);if(root->left)QueuePush(&q, root->left);if(root->right)QueuePush(&q, root->right);}QueueDestroy(&q);
}

三、二叉树中结点个数

使用遍历计数的方法，可以有以下两个代码：

int BinaryTreeSize(BTNode* root)
{if (root == NULL){return;}// 遍历计数思想：多次调用存在问题static int count = 0;++count;BinaryTreeSize(root->left);BinaryTreeSize(root->right);return count;
}void BinaryTreeSize(BTNode* root, int* pn)
{if (root == NULL){return;}++(*pn);BinaryTreeSize(root->left, pn);BinaryTreeSize(root->right, pn);
}

上面代码存在的问题是多次调用会出错。

使用递归方法：

int BinaryTreeSize(BTNode* root)
{/*if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);*/return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

四、二叉树中叶子结点个数

按照递归写法，首先上来需要判断结点为空的情况：

if (root == NULL)
{return 0;
}

转换为递归求解方法：分别求左右子树的叶子结点的和

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(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层结点数

按照递归写法，首先上来需要判断结点为空的情况：

if (root == NULL)
{return 0;
}

转换为递归求解方法：求第root的第k层的结点数，为root左子树的k-1层结点数加上root右子树的k-1层结点数。例如：求A的第四层，可以转换为求A的左子树的第三层加上A的右子树的第三层。

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

给出递归结束条件，如果k等于1，则返回1

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{assert(k >= 1);if (root == NULL){return 0;}// 找到第k层结点if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

六、求树的深度-高度

首先给出root为空的情况，然后转换为用递归求解，因为根节点深度为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;
}

七、二叉树按值查找

首先给出root为空的处理：

if (root == NULL)
{return NULL;
}

如果该结点就是查找的值，返回该节点：

if (root->data == x)
{return root;
}

如果该结点不是查找的值，则从左子树查找，如果左子树结点是，则返回左子树。右子树类似。

if (BinaryTreeFind(root->left, x))
{return root->left;
}if (BinaryTreeFind(root->right, x))
{return root->right;
}

都找不到返回NULL：

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

好像没什么问题，但是当我们测试时发现有错误，自己动手调试就知道哪里有错误了。

修改左右子树查找的代码：

BTNode* leftRet = BinaryTreeFind(root->left, x);
if (leftRet)
{return leftRet;
}BTNode* rightRet = BinaryTreeFind(root->right, x);
if (rightRet)
{return rightRet;
}

最终代码：

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftRet = BinaryTreeFind(root->left, x);if (leftRet){return leftRet;}BTNode* rightRet = BinaryTreeFind(root->right, x);if (rightRet){return rightRet;}return NULL;
}

八、二叉树的销毁

后序遍历销毁：左右根

void BinaryTreeDestroy(BTNode* root)
{if (root == NULL){return;}BinaryTreeDestroy(root->left);BinaryTreeDestroy(root->right);free(root);
}

九、判断二叉树是否为完全二叉树

判断二叉树是否是完全二叉树，我们可以考虑层序遍历，层序遍历过程中，没有间断便是完全二叉树。

间断表示什么意思？如果该二叉树不是完全二叉树，在遍历的过程中，我们还将左右为空的结点也加入到队列中，则会出现，队列中第一个空节点的后面还会有非空结点。如果该二叉树是一棵完全二叉树，则队列中第一个空节点后边全是空节点。

因此在层序遍历过程中，遇到第一个空节点便结束，然后将队列中的剩余节点元素依次弹出，遇到非空节点就不是完全二叉树。

bool BinaryTreeComplete(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, root->left);QueuePush(&q, root->right);}// 检查队列中还有没有非空节点，有非空节点就不是完全二叉树while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

源码

Gitee-BinaryTree

总结

1.第一步需要上来就对空树情况进行处理。
2.递归的方法进行问题转换：求树的问题，转换为求左树和右树的问题，进行递归处理。
3.第二步空树情况处理完之后，需要给出递归结束条件。或满足当前节点判断的条件。
4.第三步需要给出递归表达式。

---