作者:一个喜欢猫咪的的程序员
专栏:《数据结构》
喜欢的话:世间因为少年的挺身而出,而更加瑰丽。 ——《人民日报》
目录
2.4.2二叉树第K层的节点个数(TreeLevelSize):
2.7.1判断二叉树是否是完全二叉树(BinaryTreeComplete)
3.1test.c文件(二叉树实现):3.2Queue.h文件:
1.二叉树的概念及结构
1.1二叉树的概念
二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树,且有左右之分。
1.2二叉树的类型分类:
二叉树分为两种:
- 完全二叉树
- 满二叉树
1.3二叉树的结构
由上图可知,二叉树是一个节点root,链接着一个左节点left和一个右节点right。
定义二叉树的结构:
typedef int BTDataType; typedef struct BinaryTreeNode {//二叉树的结构 BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode;
创建二叉树节点:
BTNode* BuyBTNode(BTDataType x) { BTNode*newnode=(BTNode*)malloc(sizeof(BTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->left = newnode->right = NULL; return newnode; }
在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,为了降低大家学习成本,此处手动快速创建一棵简单的二叉树.
这里手动链接各方便大家理解后面的操作,以及对测试用例的修改来测试接口函数是否正确符合要求.
//构造二叉树 BTNode* n1 = BuyBTNode(1); BTNode* n2 = BuyBTNode(2); BTNode* n3 = BuyBTNode(3); BTNode* n4 = BuyBTNode(4); BTNode* n5 = BuyBTNode(5); BTNode* n6 = BuyBTNode(6); BTNode* n7 = BuyBTNode(7); n1->left = n2;//链接二叉树 n1->right = n4; n2->left = n3; n4->left = n5; n4->right = n6; n3->left = n7;
2.接口实现及其具体细节的讲解
2.1知识铺垫:二叉树的遍历方式
遍历顺序分为4种:(root为根节点)
- 前序遍历:root 左子树 右子树
- 中序遍历:左子树 root 右子树
- 后序遍历:左子树 右子树 root
- 层序遍历:一层一层遍历(后面会单独讲)
如:前序遍历是每颗子树都先遍历root节点,再遍历左子树,最后在遍历右子树。
以下图为例:我们来了解一下前序遍历的顺序。
先root节点出1,然后是1的左子树(以2为根节点的子树)出2,再到2的左子树出3,再出3的左子树NULL,然后返回3的位置再走3的右子树然后出NULL,再返回2走2的右子树出NULL再返回到1的位置,1的右子树也是如此,以此类推。
还是以上图为例子,前中后序的顺序如下:
2.2前中后序遍历代码实现:
2.2.1前序遍历(PreOrder):
前序遍历的遍历顺序:root 左子树 右子树
将一个二叉树分为根节点、左子树和右子树,它的子树也是可以这样分。
这样的操作是重复的,因此可以看成一个递归的底层过程。
只看最下面的部分的话
- 当root为NULL时,打印NULL。
- 当root不为NULL时,打印root->data的值。
只看最顶部 1 2 4的时候。
先打印root(1),然后递归找到左子树(2)打印2,再递归找到右子树(4)打印4。
从局部映射到整体后,函数递归写法就是如此。
// 二叉树前序遍历 void PreOrder(BTNode* root) { //assert(root); if (root == NULL) { printf("NULL "); return; } printf("%d ", root->data); PreOrder(root->left); PreOrder(root->right); }
2.2.2中序遍历(InOrder):
中序遍历与前序遍历不相同的地方就是在打印的先后顺序不同
因此递归的前后顺序随着改变。
// 二叉树中序遍历 void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); }
2.2.3后序遍历(PostOrder):
// 二叉树后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); }
2.3二叉树的节点个数和叶节点个数:
2.3.1二叉树节点的个数(TreeSize):
二叉树节点的个数,可以看成左子树的节点个数+右子树的节点个数+1(根节点)。
遇到NULL返回0。
当只有1个节点时,它也有左子树(NULL)和右子树(NULL)。
当树为 1 2 4时,1的左子树为2,右子树为4。那2和4的左子树和右子树又是相当于只有一个节点的情况。
...
扩张到n个节点的情况下,就是递归不断向下找并且返回的过程。
// 二叉树节点个数 int TreeSize(BTNode* root) { if (root == NULL) return 0; return TreeSize(root->left) + TreeSize(root->right) + 1; }
2.3.2二叉树叶子节点的个数(TreeLeafSize)
计算叶子结点的个数,又跟就是二叉树节点个数不太一样
叶节点代表它没有左右节点了,也就是左右节点皆为NULL
- 当左右左右节点皆为NULL时返回1
- 叶节点数等于左子树的叶子个数+右子树的叶子个数
// 二叉树叶子节点个数 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); }