目录
1. 定义
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType _data;
struct BinaryTreeNode* _left;
struct BinaryTreeNode* _right;
}BTNode;回顾下二叉树的概念，二叉树是：
1. 空树
2. 非空：根节点，根节点的左子树、根节点的右子树组成的
从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的
2. 二叉树的遍历
2.1 前序、中序以及后序遍历
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历
前序遍历： 根 左子树 右子树
中序遍历： 左子树 根 右子树
后序遍历： 左子树 右子树 根
注：二叉树的前中后遍历是根据 根节点 的遍历位置判断的
举例：
2.1.1 前序遍历
void PreOrder(BTNode* root)
{
if (root == NULL)//便于测试观察
{
printf("# ");
return;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}2.1.2 中序遍历
void InOrder(BTNode* root){
if (root == NULL)//便于测试观察
{
printf("# ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}2.1.3 后序遍历
void PostOrder(BTNode* root){
if (root == NULL){
printf("# ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}2.2 二叉树的层序遍历
思路：运用队列，将根节点入队列，当队列不为空的时候，将根节点出队列，同时将左右子树根节点入队。
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
printf("%d ", front->data);
QueuePop(&q);
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
}
printf("\n");
QueueDestroy(&q);
}
3. 二叉树节点个数及高度等
3.1 求节点个数
int TreeSize(BTNode* root)
{
return root == NULL ? 0 :
TreeSize(root->left) + TreeSize(root->right) + 1;
}3.2 求叶子节点个数
int TreeLeafSize(BTNode* root)
{
if (root == NULL)//空节点
return 0;
if (root->left== NULL && root->right == NULL)//叶子节点
return 1;
//非空非叶子返回 左子树叶子节点+右子树叶子节点
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}3.3 求第K层节点个数
int TreeKLevel(BTNode* root, int k)
{
assert(k >= 1);
if (root == NULL)//空节点
return 0;
if (k == 1)//递归到了第K层，遇到节点+1
return 1;
//非空非K，返回左子树的K-1层节点数+右子树的K-1层节点数
return TreeKLevel(root->left, k - 1)
+ TreeKLevel(root->right, k - 1);
}3.4 求二叉树深度
int TreeDepth(BTNode* root)
{
if(root == NULL)
return 0;
int leftDepth = TreeDepth(root->left);
int rightDepth = TreeDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
3.5 二叉树查找值为X的节点
BTNode* TreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BTNode* ret1 = TreeFind(root->left, x);
if (ret1)
return ret1;
BTNode* ret2 = TreeFind(root->right, x);
if (ret2)
return ret2;
return NULL;
}