目录
- 1. 前言
- 2. 二叉树的实现
- 2.1 创建一棵树
- 2.2 前序遍历
- 2.2.1 分析
- 2.2.2 代码实现
- 2.2.3 递归展开图
- 2.3 中序遍历
- 2.3.1 分析
- 2.3.2 代码实现
- 2.3.3 递归展开图
- 2.4 后序遍历
- 2.4.1 分析
- 2.4.2 代码实现
- 2.4.3 递归展开图
- 2.5 求节点个数
- 2.5.1 分析
- 2.5.2 代码实现
- 2.6 求叶子节点个数
- 2.6.1 分析
- 2.6.2 代码实现
- 2.7 求树高度
- 2.7.1 分析
- 2.7.2 代码实现
- 2.8 求第K层节点的个数
- 2.8.1 分析
- 2.8.2 代码实现
1. 前言
在前面的博客中写了有关二叉树的介绍，那这次来写关于用C语言来实现与二叉树有关的一些操作。
与之前链表和顺序表不同的是，这里不实现增删查改。
2. 二叉树的实现
2.1 创建一棵树
直接手动创建一棵树，也就是直接malloc所有的节点。
直接创建6个节点，然后让node1的数据直接是1，让node2的数据直接是2，依次下去。
然后直接让node1的left = node2，它的right = node4;就按照上面的图来构建。
代码如下：
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}TreeNode;
TreeNode* CreateTree()
{
TreeNode* node1 = (TreeNode*)malloc(sizeof(TreeNode));
assert(node1);
TreeNode* node2 = (TreeNode*)malloc(sizeof(TreeNode));
assert(node2);
TreeNode* node3 = (TreeNode*)malloc(sizeof(TreeNode));
assert(node3);
TreeNode* node4 = (TreeNode*)malloc(sizeof(TreeNode));
assert(node4);
TreeNode* node5 = (TreeNode*)malloc(sizeof(TreeNode));
assert(node5);
TreeNode* node6 = (TreeNode*)malloc(sizeof(TreeNode));
assert(node6);
node1->data = 1;
node2->data = 2;
node3->data = 3;
node4->data = 4;
node5->data = 5;
node6->data = 6;
node1->left = node2;
node1->right = node4;
node2->left = node3;
node2->right = NULL;
node3->left = NULL;
node3->right = NULL;
node4->left = node5;
node4->right = node6;
node5->left = NULL;
node5->right = NULL;
node6->left = NULL;
node6->right = NULL;
}
但是这个代码局限性太大，已经是写固定了的代码，不好再修改，下面这种会好一些。
不用管空。
想要其它形状的可以修改代码，做一定的增加或者就行。
代码如下：
TreeNode* BuyTreeNode(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 = BuyTreeNode(1);
TreeNode* node2 = BuyTreeNode(2);
TreeNode* node3 = BuyTreeNode(3);
TreeNode* node4 = BuyTreeNode(4);
TreeNode* node5 = BuyTreeNode(5);
TreeNode* node6 = BuyTreeNode(6);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
return node1;
}
2.2 前序遍历
2.2.1 分析
前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
就实现这颗树的前序遍历。
先根，然后左子树，再右子树，初学时把NULL也带上，方便理解。
也就是下面这样。
先访问根，然后找左子树，左子树又得拆成根和左子树，一直到空。使用递归来实现。
2.2.2 代码实现
void PrevOrder(TreeNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
结果和分析的一样：
2.2.3 递归展开图
2.3 中序遍历
2.3.1 分析
中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
同样以上面那棵树为例子。
先左子树，再根，再右子树。
这里遇到根先不是NULL，先走它的左子树，是空就打印返回。
2.3.2 代码实现
void InOrder(TreeNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
结果与分析的是一样的：
2.3.3 递归展开图
2.4 后序遍历
2.4.1 分析
.后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
同样是以上面那棵树为例子，它的后序遍历就是：
先访问它的左子树，然后右子树，最后才是根。
要当左右都为空时才访问第一个节点。
2.4.2 代码实现
void PostOrder(TreeNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
递归展开方式也是一样的
2.4.3 递归展开图
2.5 求节点个数
2.5.1 分析
只要节点不为空，就加加，然后再调用左子树，右子树。
用全局的size，每次调用前先置空一些。
局部的使用不了，因为不能置空，再调用一次就会再上次的基础上累计。
同样是这课树节点数为6。
2.5.2 代码实现
int size = 0;
void TreeSize(TreeNode* root)
{
if (root == NULL)
return;
++size;
TreeSize(root->left);
TreeSize(root->right);
}
int main()
{
TreeNode* root = CreateTree();
size = 0;
TreeSize(root);
printf("TreeSize:%d\n", size);
return 0;
}
还有另一种实现：把树拆成左子树加右子树加1.
代码如下：
int TreeSize(TreeNode* root)
{
return root == NULL ? 0 :
TreeSize(root->left) +
TreeSize(root->right) + 1;
}
结果还是一样的。
采用的就是分治法
2.6 求叶子节点个数
2.6.1 分析
先得判断一下树是不是空树，不是才能就行进行。
不是空树，而且左右节点都为空，就是叶子节点，就返回1；
不是空，也不是叶子节点就采用分治，树的节点就等于左右叶子节点的和。
同样是这棵树，叶子节点就是3.
2.6.2 代码实现
int TreeLeafSize(TreeNode* root)
{
// 空 返回0
if (root == NULL)
return 0;
// 不是空，是叶子 返回1
if (root->left == NULL
&& root->right == NULL)
return 1;
// 不是空 也不是叶子 分治=左右子树叶子之和
return TreeLeafSize(root->left) +
TreeLeafSize(root->right);
}
int main()
{
TreeNode* root = CreateTree();
printf("TreeLeafSize:%d\n", TreeLeafSize(root))；
return 0;
}
和分析的一样叶子节点个数就是3.
2.7 求树高度
2.7.1 分析
先要判断一下树是不是空树，是就为0。
不是空树，就要判断一下左子树和右子树那个更高，然后高的那个就加1。
同样以这棵树计算，这棵树的高度就是3
2.7.2 代码实现
int TreeHeight(TreeNode* root)
{
if (root == NULL)
return 0;
int leftHeight = TreeHeight(root->left);
int rightHeight = TreeHeight(root->right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
int main()
{
TreeNode* root = CreateTree();
printf("TreeHeight:%d\n", TreeHeight(root));
return 0;
}
int TreeHeight(TreeNode* root)
{
if (root == NULL)
return 0;
return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1;
}
这里使用fmax返回大的数，需要包一个头文件<math.h>
结果也是一样的。
2.8 求第K层节点的个数
2.8.1 分析
同样采用分治。
如果是空树就返回0；
如果不为空，k=1，第一层就返回1；
如果不为空，且k>1,就返回左子树的k-1层加上右子树的k-1层。
同样以这棵树计算，k>1就说明再第一层的下面。这棵树的第三层的节点数就是，第二层的左加第二层的右；第二层的左又转化成第一层的左加第一层的右，为空就返回0。
2.8.2 代码实现
int TreeLevelK(TreeNode* root, int k)
{
assert(k > 0);
if (root == NULL)
return 0;
if (k == 1)
return 1;
return TreeLevelK(root->left, k - 1)
+ TreeLevelK(root->right, k - 1);
}
int main()
{
TreeNode* root = CreateTree();
printf("TreeLevelK:%d\n", TreeLevelK(root, 3));
return 0;
}
结果如下：
有问题请指出，大家一起进步！
