一、什么是树
树是一种非线性的数据结构，由若干个节点组成。每个节点都包含数据，并且可以有多个子节点。树的最顶端是一个特殊的节点，叫根节点，它没有父节点。从根节点开始，树不断向下分叉，形成不同的层次。最底层的节点叫叶子节点，它们没有子节点。
二、树的种类
树有很多种类，每种都有自己的特点。
（一）二叉树
二叉树是最常见的树。它的每个节点最多有两个子节点，分别是左子节点和右子节点。二叉树的遍历方式有前序、中序和后序遍历，常用于表达式求值和数据排序。
（二）平衡二叉树
平衡二叉树是一种特殊的二叉树，它的左右子树高度差不超过1。这种树在插入、删除和查找数据时效率很高，常用于数据库索引。
（三）B树和B+树
B树和B+树是多路平衡查找树，主要用于数据库和文件系统的索引。它们可以高效地存储和检索大量数据。
树以其独特的结构和强大的功能，在数据存储和处理中发挥着重要作用，是计算机科学中不可或缺的一部分。
三、遍历
树的遍历是按照某种顺序访问树中的每个节点的过程，确保每个节点都被访问一次且仅一次。以下是常见的树的遍历形式，以二叉树为例：
前序遍历：适合构建树的结构、打印树的先序序列等。
中序遍历：适用于二叉搜索树的排序和查找。
后序遍历：适合删除树的节点、计算表达式的后缀形式等。
层次遍历：适合按层打印树的结构、计算树的深度等。
本次代码会实现前中后三种遍历：
前序遍历
过程：先访问根节点，然后递归地对左子树进行前序遍历，最后递归地对右子树进行前序遍历。简记为“根左右”。
中序遍历
过程：先递归地对左子树进行中序遍历，然后访问根节点，最后递归地对右子树进行中序遍历。简记为“左根右”。
后序遍历
过程：先递归地对左子树进行后序遍历，然后递归地对右子树进行后序遍历，最后访问根节点。简记为“左右根”。
//二叉搜索树
#include<stdio.h>
#include<stdlib.h>typedef struct Node
{int data;//数据域struct Node *left;//左子树struct Node *right;//右子树
}TreeNode;TreeNode * insert(TreeNode * root,int val);
void pre_order(TreeNode *root);
void in_order(TreeNode *root);//中序遍历
void post_order(TreeNode *root);
int main(int argc, char const *argv[])
{//根节点指针TreeNode *root=NULL;//插入数据root = insert(root,1);root = insert(root,2);root = insert(root,3);root = insert(root,4);root = insert(root,5);in_order(root);pre_order(root);post_order(root);return 0;
}
TreeNode * insert(TreeNode * root,int val)
{if (root==NULL)//传入的结点为空时，创建新的结点{root=malloc(sizeof(TreeNode));root->data=val;root->left=NULL;root->right=NULL;return root;}if (val<root->data){// 小于当前结点值，插入左子树root->left= insert(root->left,val);}else{//大于当前结点值，插入右子树root->right= insert(root->right,val);}return root;
}
void in_order(TreeNode *root)
{if (root==NULL){return;}in_order(root->left);//先打印左子树printf("%d",root->data);//打印根节点in_order(root->right);//打印右子树
}
void pre_order(TreeNode *root)
{if (root==NULL){return;}printf("%d",root->data);//打印根节点pre_order(root->left);//打印左子树pre_order(root->right);//打印右子树
}
void post_order(TreeNode *root)
{if (root==NULL){return;}post_order(root->left);//打印左子树post_order(root->right);//打印右子树printf("%d",root->data);//打印根节点
}