目录
一、提前说明
二、二叉树的遍历
2.1前序遍历
2.2中序遍历
2.3后序遍历
2.4代码
三、二叉树结点个数
3.1整体思路
3.2代码
四、二叉树叶子结点个数
4.1整体思路
4.2代码
五、二叉树的高度(深度)
5.1整体思路
5.2代码
六、二叉树第k层节点个数
6.1整体思路：
6.2代码
七、二叉树查找值为x的节点
7.1整体思路
7.2代码
一、提前说明
在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。我们在这里先手动构建一棵“死树”，学完基本操作以后我们再来重新构建。
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}TreeNode;
TreeNode* CreateTreeNode(int x)
{
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
assert(node);
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}
TreeNode* CreateTree()
{
TreeNode* node1 = CreateTreeNode(1);
TreeNode* node2 = CreateTreeNode(2);
TreeNode* node3 = CreateTreeNode(3);
TreeNode* node4 = CreateTreeNode(4);
TreeNode* node5 = CreateTreeNode(5);
TreeNode* node6 = CreateTreeNode(6);
TreeNode* node7 = CreateTreeNode(7);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
node5->right = node7;
return node1;
}
二、二叉树的遍历
遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础
2.1前序遍历
前序遍历(Preorder Traversal)——访问根结点的操作发生在遍历其左右子树之前。
2.2中序遍历
中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
2.3后序遍历
后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
2.4代码
void PreOrder(TreeNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
void InOrder(TreeNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
void PostOrder(TreeNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
紧接着我们用我们的“死树”来验证一下我们的代码：
我们看我们的二叉树其实是非常丑的，但是我们通过验证也证明了我们代码的正确性。
而且在验证的时候还有一个小插曲：当我发现实际和输出不对等时，我没有怀疑代码的正确性，而是发现我的二叉树图画错了。
三、二叉树结点个数
3.1整体思路
求结点个数那么遍历整个二叉树肯定是必要的，这就是为什么说遍历是最重要的操作的原因
我们可以看出，如果root为NULL时，返回0，否则都是向上返回左右结点之和，那么我们就可以直接相加，还要加上它本身。
3.2代码
int BinaryTreeSize(TreeNode* root)
{
if (root == NULL)
{
return 0;
}
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
四、二叉树叶子结点个数
叶结点或终端结点：度为0的节点称为叶节点
4.1整体思路
我们的想法是上一个函数的基础上修改一下返回条件：
4.2代码
int BinaryTreeLeafSize(TreeNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}五、二叉树的高度(深度)
5.1整体思路
首先要判断根是否存在，如果根存在，继续向下遍历，再次遍历的时候，先判断其左右子树是否存在，若存在，再遍历其左右子树，此时就不用再进行根判断了，根判断的代码只在进入函数时有效执行。 以下是我们的大致思路，但是递归的图着实太难画了，实在不理解可以仔细参照文字或者自己画：
在画图的过程中我们也发现了，我们每次都要返回左右子树遍历后的较大值，如何做？
这时我们可以借用C语言库中的较大值函数，而且可以进行代码的简化： 
5.2代码
int BinaryTreeHeight(TreeNode* root)
{
if (root == 0)
{
return 0;
}
return fmax(BinaryTreeHeight(root->left), BinaryTreeHeight(root->right)) + 1;
}六、二叉树第k层节点个数
6.1整体思路：
6.2代码
int BinaryTreeLevelKSize(TreeNode* root, int k)
{
assert(k > 0);
if (root == NULL)
return 0;
if (k == 0)
return 0;
else if (k == 1)
return 1;
else
return BinaryTreeLevelKSize(root->left, k - 1) +
BinaryTreeLevelKSize(root->right, k - 1);
}七、二叉树查找值为x的节点
7.1整体思路
我认为思路的重点是怎么递归左右子树并当返回其中不为空的值。
我们要如何验证代码的正确性呢？在return 0处打断点：
另外我们的printf要用p%打印出地址，观察监视的值与输出是否相同。
7.2代码
TreeNode* BinaryTreeFind(TreeNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
else
{
TreeNode* leftans = BinaryTreeFind(root->left, x);
TreeNode* rightans = BinaryTreeFind(root->right, x);
return leftans == NULL ? rightans : leftans;
}
}
