前言：
在前面我们讲了堆及其应用，帮助我们初步了解了二叉树的一些原理，但那与真正的二叉树仍有不同，今天我们就来正式学习一下二叉树的基本结构及其基本操作
一、什么是二叉树？
在前面的文章中我们已经提到过二叉树的结构及其特点，这里我们不过多赘述，有不理解的可以点文章开头的链接去前面看一下
二、二叉树的节点结构
二叉树有左右子树之分，且二叉树与我们所学的其他数据结构不同的点在于，之前我们所学的都是各类插入或者删除等等，但是二叉树需要做的操作是运用递归遍历，所以二叉树的节点结构与之前几个有很大不同
typedef int TreeDataType; typedef struct Tree { TreeDataType a; struct Tree* left; struct Tree* right; }Tree;
节点结构里面定义有两个递归，是为了方便后面的遍历
三、二叉树的遍历
二叉树的遍历是我们学习二叉树首先要了解的东西，我们都知道二叉树其实就是一串数组，那我们是如何访问他们的呢？这里就牵扯到了遍历顺序的问题。
二叉树的遍历有三种形式：前序、中序和后序
- 特点：按照“根-左-右”的顺序遍历二叉树。
- 特点：首先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。
- 应用：常用于复制一棵树、计算表达式的值等。
中序遍历：
- 特点：按照“左-根-右”的顺序遍历二叉树。
- 特点：先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。
- 应用：常用于二叉搜索树，可以得到一个递增的有序序列。
后序遍历：
- 特点：按照“左-右-根”的顺序遍历二叉树。
- 特点：先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。
- 应用：常用于释放二叉树的内存空间，或者计算表达式的值。
- 例如：
四、二叉树的基本操作
我先把主函数给出，接下来就将按照主函数中的这些功能一步一步来实现
int main() { Tree* root = CreatTree(); //前序 printf("前序："); PrevTree(root); printf("\n"); //中序 printf("中序："); HalfTree(root); printf("\n"); //后序 printf("后序："); PostTree(root); printf("\n"); //节点个数 int count = BTreeSize(root); printf("BTreeSize:%d\n", count); //叶子节点个数 printf("BTreeLeafSize:%d\n", BTreeLeafSize(root)); //树的高度 printf("BTreeHigh:%d\n", BTreeHigh(root)); //二叉树第k层节点个数 printf("BTreeLevelKSize:%d\n", BTreeLevelKSize(root, 3)); //二叉树查找值为x的节点 return 0; }
1、创建二叉树
//二叉树 typedef int TreeDataType; typedef struct Tree { TreeDataType a; struct Tree* left; struct Tree* right; }Tree; //初始化二叉树 Tree* TreeInit(TreeDataType x) { Tree* m = (Tree*)malloc(sizeof(Tree)); if (m == NULL) { perror("TreeInit"); return NULL; } m->a = x; m->left = NULL; m->right = NULL; return m; } //创建一个二叉树 Tree* CreatTree() { Tree* n1 = TreeInit(3); Tree* n2 = TreeInit(5); Tree* n3 = TreeInit(6); Tree* n4 = TreeInit(7); Tree* n5 = TreeInit(9); n1->left = n2; n1->right = n3; n2->left = n4; n2->right = n5; return n1; }
2、前序、中序、后序
前序、中序和后序其实就是数据按照上面图片中的形式进行遍历
//前序 void PrevTree(Tree* root) { if (root == NULL) { printf("N "); return; } printf("%d ", root->a); PrevTree(root->left); PrevTree(root->right); } //中序 void HalfTree(Tree* root) { if (root == NULL) { printf("N "); return; } HalfTree(root->left); printf("%d ", root->a); HalfTree(root->right); } //后序 void PostTree(Tree* root) { if (root == NULL) { printf("N "); return; } PostTree(root->left); PostTree(root->right); printf("%d ", root->a); }
运行结果：
3、求二叉树的节点个数
//二叉树节点个数 int BTreeSize(Tree* root) { //分治的思想 if (root == NULL) { return 0; } return BTreeSize(root->left) + BTreeSize(root->right)+1 ; }
用到了递归的思想，下面的内容都要用递归来解决，如果递归学的不太好建议画图来看这些过程如何进行的
运行结果：
4、求二叉树叶子节点的个数
//二叉树叶子节点个数 int BTreeLeafSize(Tree* root) { if (root == NULL) { return 0; } if (root->left == NULL && root->right == NULL) { return 1; } return BTreeLeafSize(root->left) + BTreeLeafSize(root->right); }
运行结果：
5、树的高度
//求二叉树高度 int BTreeHigh(Tree* root) { if (root == NULL) { return 0; } int leftHigh = BTreeHigh(root->left); int rightHigh = BTreeHigh(root->right); return leftHigh > rightHigh ? leftHigh + 1 : rightHigh + 1; }
运行结果：
6、二叉树第k层的节点个数
//二叉树第k层节点个数 int BTreeLevelKSize(Tree* root, int k) { assert(k > 0); if (root == NULL) { return 0; } if (k == 1) { return 1; } return BTreeLevelKSize(root->left, k - 1) + BTreeLevelKSize(root->right, k - 1); }
运行结果：
7、二叉树查找值为x的节点
//二叉树查找值为x的节点 Tree* BTreeFind(Tree* root,int x) { if (root == NULL) return NULL; if (root->a == x) return root; Tree* ret1 = BTreeFind(root->left, x); if (ret1) { return ret1; } Tree* ret2 = BTreeFind(root->right, x); if (ret2) { return ret2; } }
五、完整代码实例
//二叉树 typedef int TreeDataType; typedef struct Tree { TreeDataType a; struct Tree* left; struct Tree* right; }Tree; //初始化二叉树 Tree* TreeInit(TreeDataType x) { Tree* m = (Tree*)malloc(sizeof(Tree)); if (m == NULL) { perror("TreeInit"); return NULL; } m->a = x; m->left = NULL; m->right = NULL; return m; } //创建一个二叉树 Tree* CreatTree() { Tree* n1 = TreeInit(3); Tree* n2 = TreeInit(5); Tree* n3 = TreeInit(6); Tree* n4 = TreeInit(7); Tree* n5 = TreeInit(9); n1->left = n2; n1->right = n3; n2->left = n4; n2->right = n5; return n1; } //前序 void PrevTree(Tree* root) { if (root == NULL) { printf("N "); return; } printf("%d ", root->a); PrevTree(root->left); PrevTree(root->right); } //中序 void HalfTree(Tree* root) { if (root == NULL) { printf("N "); return; } HalfTree(root->left); printf("%d ", root->a); HalfTree(root->right); } //后序 void PostTree(Tree* root) { if (root == NULL) { printf("N "); return; } PostTree(root->left); PostTree(root->right); printf("%d ", root->a); } //二叉树节点个数 int BTreeSize(Tree* root) { //分治的思想 if (root == NULL) { return 0; } return BTreeSize(root->left) + BTreeSize(root->right)+1 ; } //二叉树叶子节点个数 int BTreeLeafSize(Tree* root) { if (root == NULL) { return 0; } if (root->left == NULL && root->right == NULL) { return 1; } return BTreeLeafSize(root->left) + BTreeLeafSize(root->right); } //求二叉树高度 int BTreeHigh(Tree* root) { if (root == NULL) { return 0; } int leftHigh = BTreeHigh(root->left); int rightHigh = BTreeHigh(root->right); return leftHigh > rightHigh ? leftHigh + 1 : rightHigh + 1; } //二叉树第k层节点个数 int BTreeLevelKSize(Tree* root, int k) { assert(k > 0); if (root == NULL) { return 0; } if (k == 1) { return 1; } return BTreeLevelKSize(root->left, k - 1) + BTreeLevelKSize(root->right, k - 1); } //二叉树查找值为x的节点 Tree* BTreeFind(Tree* root,int x) { if (root == NULL) return NULL; if (root->a == x) return root; Tree* ret1 = BTreeFind(root->left, x); if (ret1) { return ret1; } Tree* ret2 = BTreeFind(root->right, x); if (ret2) { return ret2; } } int main() { Tree* root = CreatTree(); //前序 printf("前序："); PrevTree(root); printf("\n"); //中序 printf("中序："); HalfTree(root); printf("\n"); //后序 printf("后序："); PostTree(root); printf("\n"); //节点个数 int count = BTreeSize(root); printf("BTreeSize:%d\n", count); //叶子节点个数 printf("BTreeLeafSize:%d\n", BTreeLeafSize(root)); //树的高度 printf("BTreeHigh:%d\n", BTreeHigh(root)); //二叉树第k层节点个数 printf("BTreeLevelKSize:%d\n", BTreeLevelKSize(root, 3)); //二叉树查找值为x的节点 return 0; }
运行结果：
总结
总而言之，二叉树其实是对我们运用递归来遍历数据的考察，由于篇幅原因，这里我们只对二叉树的结构进行了大致的讲解，有不理解的地方欢迎与我私信或者在评论区中指出
创作不易，还请各位大佬点个小小的赞！！！
