二叉树详解

一、二叉树的实现

1.1 二叉树的前序遍历

1.2 二叉树的中序遍历

1.3 二叉树的后续遍历

1.4 二叉树的节点个数

1.5 二叉树叶子节点个数

1.6 二叉树查找值为x的节点

1.7 二叉树第k层节点个数

1.8 二叉树的高度

1.9 二叉树的销毁

二、代码展示

BTNode.h

BTNode.c

最后

一、二叉树的实现

前面我们已经说过了二叉树的定义与概念，现在我们讨论的是如何实现二叉树。

在二叉树中我们不仅无法确定其具体的孩子数，也无法确定其具体节点数。那该如何实现，那不就是无从下手吗？非也，咱们想不到，自有人会想到，这里，我们实现的思路为：左孩子、右兄弟表示法。即：根左边指向它的左孩子，右边指向它左孩子的兄弟也就是右孩子，这样不就表示出来了。可借助以下代码理解：

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

运用此方法，我们可较为方便的表示出各个节点之间的关系。我们现在能用到这样的方法就是因为：我们是站在巨人的肩膀上。

了解了二叉树的大逻辑后，我们现在要开始研究二叉树的细枝末节了。

1.1 二叉树的前序遍历

我们在用代码实现前，我们要先明白，什么是遍历？什么是前序遍历？

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。

所谓的前序遍历即：二叉树沿着：根，左子树，右子树的顺序进行遍历。

我们已明白其实现逻辑，现在开始用代码实现吧！

void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){return;//此处也可打印N}printf("%d", root->data);//按照前序遍历顺序：根BinaryTreePrevOrder(root->left);//左子数BinaryTreePrevOrder(root->right);//右子数
}

上面帮助大家理解以下此代码。总之：记住顺序：根，左子树，右子树。

1.2 二叉树的中序遍历

在理解了前序遍历后，中序遍历也可以理解。中序遍历和前序遍历并无本质区别，只是顺序变换了一下，即：左子树，根，右子树。代码实现如下：

void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){return;}BinaryTreeInOrder(root->left);printf("%d  ", root->data);BinaryTreeInOrder(root->right);//无不一样之处，只是交换了顺序
}

1.3 二叉树的后续遍历

后续遍历的遍历顺序为：左子树，右子树，根。其余思路还是一致。代码实现如下：

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

1.4 二叉树的节点个数

接下来，我们学习如何求二叉树的节点个数。

假如，你们学校有一个校长，两个院长，四个辅导员，八个班长。校长接到通知，要求统计在校师生人数，你觉得，校长会怎么干？是哪一个小本本，一个一个统计：计算机学院多少人，软件学院多少人，还是把他的左膀右臂——两个院长叫过来。答案显然易见，肯定会摇人，院长见校长这么想，肯定也会叫导员，层层外包，最后，班长成苦命的打工人。

统计节点个数的思路与上文类似，都是层层分封然后加上自己即可。代码实现如下：

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

1.5 二叉树叶子节点个数

此问题我们可不可以运用上题的思路解决，当然可以。实现代码如下：

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);
}

这里的实现思路只不过换成只要是叶节点就放回一。

1.6 二叉树查找值为x的节点

相信有一部分人看到此题，说：“简单”。然后写出以下代码：

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}return BinaryTreeFind(root->left,x);return BinaryTreeFind(root->right,x);
}

这个代码乍一看，大逻辑好像是对的，其实不然，如果，左子树，能够找到，那最好了。但，右子树和部分左子树根本找不到。为啥？一个函数是不是只有一个返回值，结构体可以有多个。既然只有一个，那么注定只能放回一个，其余的哪怕是找到了也会没找到，无法得用。

优化后代码如下：

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode*p1 = BinaryTreeFind(root->left,x);if (p1){return p1;}BTNode* p2 = BinaryTreeFind(root->right,x);//分别用指针记录，找到才返回if (p2){return p2;}return NULL;
}

1.7 二叉树第k层节点个数

求第k层高度，各位读者有没有思路。这里的难点为：如何找到该层。只要能找到，统计节点，那都会，对吧。

这里提供一种想法，仅供参考：每一次使k--，叫k的值和一比。如果等于一，则到了要找的层，不为一就继续，没有就返回0。代码实现思路如下：

int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

1.8 二叉树的高度

我们在这里想，如何求出二叉树的高度呢？是不是可以转换成左子树和右子树谁更高的问题。谁高就加一，对吧。来先看以下代码：

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

这代码，从逻辑和结果上来看，没啥问题。但，复杂度太高。

咱们的想法是运用递归实现，本题中的代码，没有一个记录的，本次用完，别人想用，就忘记了，就要重新调。读者可能认为是2倍的关系。其实不然，我用故事来解释一下：

当班长把统计的人数告诉导员时候，导员说：知道了，你回去吧。走到半路，接到电话，导员说：你在来一下，我给院长汇报时忘记了。班长去汇报，回来。又去为啥：院长统计时又忘记了，又去，又回来，没完没了了，可用下图表示：

从此图可以看出复杂度是很高的，越是底层，干的就越多。所以，我们可做以下优化：

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

1.9 二叉树的销毁

二叉树的销毁其实传不传二级指针都行，不传的化，只需在调用后，手动置空即可。

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

二、代码展示

BTNode.h

#pragma once
#include<stdio.h>typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
//求二叉树高度
int TreeHight(BTNode* root);

BTNode.c

#include"BTNode.h"//二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){return;//此处也可打印N}printf("%d", root->data);//按照前序遍历顺序：根BinaryTreePrevOrder(root->left);//左子数BinaryTreePrevOrder(root->right);//右子数
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){return;}BinaryTreeInOrder(root->left);printf("%d  ", root->data);BinaryTreeInOrder(root->right);//无不一样之处，只是交换了顺序
}
//二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){return;}BinaryTreePostOrder(root->left);BinaryTreePostOrder(root->right);printf("%d  ", root->data);
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
// 二叉树叶子节点个数
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层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode*p1 = BinaryTreeFind(root->left,x);if (p1){return p1;}BTNode* p2 = BinaryTreeFind(root->right,x);//分别用指针记录，找到才返回if (p2){return p2;}return NULL;
}
//求二叉树高度
int TreeHight(BTNode* root)
{if (root == NULL){return 0;}int left = TreeHight(root->left);int right = TreeHight(root->right);return left > right ?left + 1 : right + 1;
}
// 二叉树销毁
void TreeDestory(BTNode* root)
{if (root == NULL)return;TreeDestory(root->left);TreeDestory(root->right);free(root);
}