【数据结构】二叉树的实现

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)
{// 空 返回0if (root == NULL)return 0;// 不是空，是叶子 返回1if (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;
}

结果如下：

有问题请指出，大家一起进步！