数据结构--树和二叉树
目录
一.树概念及结构(了解)
1.1树的概念 树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它 叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
有一个特殊的结点，称为根结点，根节点没有前驱结点。
除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集 合Ti(1又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以 有0个或多个后继。
因此，树是递归定义的。（常用递归思想建立树）
二.树的实现
三.实现树的函数
1. NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右 子树之前。
2. LNR：中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中 （间）
3. LRN：后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
4. 求二叉树所有节点的个数.
5. 求叶子节点的个数.
6.销毁函数.
一.树概念及结构(了解)
1.1树的概念 树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它 叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
有一个特殊的结点，称为根结点，根节点没有前驱结点。
除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集 合Ti(1又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以 有0个或多个后继。
因此，树是递归定义的。（常用递归思想建立树）
二.树的实现
这段代码是用 C 语言定义了一个二叉树的数据结构。
一、结构定义
1. typedef char BTDataType; ：这里定义了一个别名 BTDataType ，代表二叉树节点存储的数据类型为字符型。
2. typedef struct BinaryTreeNode ：定义了一个结构体类型 BinaryTreeNode ，这个结构体代表二叉树的节点。
- struct BinaryTreeNode* left; ：指向左子树的指针。
- struct BinaryTreeNode* right; ：指向右子树的指针。
- BTDataType data; ：存储节点的数据，这里是字符型数据。
通过这个定义，可以方便地创建二叉树的节点，并构建二叉树的数据结构，用于存储和操作二叉树中的数据。
//定义二叉树
typedef char BTDataType;
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType data;
}BTNode;三.实现树的函数
前序/中序/后序的递归结构遍历：是根据访问结点操作发生位置命名
1. NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右 子树之前。
这段 C 语言代码实现了二叉树的前序遍历。
一、函数功能
PrevOrder 函数用于对给定的二叉树进行前序遍历。前序遍历的顺序是先访问根节点，再遍历左子树，最后遍历右子树。
二、实现步骤
1. 首先判断根节点是否为 NULL 。如果是，则输出 "NULL " 表示该节点为空，并直接返回。这是为了处理空树的情况。
2. 如果根节点不为空，则先输出根节点的数据 root->data 。
3. 接着递归调用 PrevOrder 函数遍历左子树 root->left 。
4. 最后递归调用 PrevOrder 函数遍历右子树 root->right 。
通过这样的递归调用，就可以按照前序遍历的顺序输出二叉树中所有节点的数据。如果二叉树为空树，则输出 "NULL " 来表示。
//前序
void PrevOrder(BTNode* root)
{if (root == NULL) {printf("NULL ");return;}printf("%c ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}2. LNR：中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中 （间）
这段 C 语言代码实现了二叉树的中序遍历。
一、函数功能
InOrder 函数用于对给定的二叉树进行中序遍历。中序遍历的顺序是先遍历左子树，再访问根节点，最后遍历右子树。
二、实现步骤
1. 首先判断根节点是否为 NULL 。如果是，则输出 "NULL " 表示该节点为空，并直接返回。这是为了处理空树的情况。
2. 如果根节点不为空，则先递归调用 InOrder 函数遍历左子树 root->left 。
3. 接着输出根节点的数据 root->data 。
4. 最后递归调用 InOrder 函数遍历右子树 root->right 。
通过这样的递归调用，就可以按照中序遍历的顺序输出二叉树中所有节点的数据。如果二叉树为空树，则输出 "NULL " 来表示。
//中序
void InOrder(BTNode* root)
{if (root == NULL) {printf("NULL ");return;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}3. LRN：后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
这段 C 语言代码实现了二叉树的后序遍历。
一、函数功能
PostOrder 函数用于对给定的二叉树进行后序遍历。后序遍历的顺序是先遍历左子树，再遍历右子树，最后访问根节点。
二、实现步骤
1. 首先判断根节点是否为 NULL 。如果是，则输出 "NULL " 表示该节点为空，并直接返回。这是为了处理空树的情况。
2. 如果根节点不为空，则先递归调用 PostOrder 函数遍历左子树 root->left 。
3. 接着递归调用 PostOrder 函数遍历右子树 root->right 。
4. 最后输出根节点的数据 root->data 。
通过这样的递归调用，就可以按照后序遍历的顺序输出二叉树中所有节点的数据。如果二叉树为空树，则输出 "NULL " 来表示。
//后序
void PostOrder(BTNode* root)
{if (root == NULL) {printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}4. 求二叉树所有节点的个数.
这段 C 语言代码实现了求二叉树所有节点个数的功能。
一、函数功能
TreeSize 函数用于计算给定二叉树的节点总数。
二、实现思路
利用后序遍历的思想，先分别计算左子树和右子树的节点个数，再加上根节点（值为 1），得到整个二叉树的节点个数。
1. 首先判断根节点是否为 NULL 。如果是，则表示这是一棵空树，节点个数为 0，直接返回 0。
2. 如果根节点不为空，则递归计算左子树的节点个数 TreeSize(root->left) 。
3. 接着递归计算右子树的节点个数 TreeSize(root->right) 。
4. 最后将左子树节点个数、右子树节点个数与根节点（值为 1）相加，即 TreeSize(root->left) + TreeSize(root->right) + 1 ，并返回这个值作为整个二叉树的节点个数。
//求二叉树所有节点的个数
//可以遍历，这里利用后序的思想求解
int TreeSize(BTNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}5. 求叶子节点的个数.
这段 C 语言代码实现了计算二叉树中叶子节点个数的功能。
一、函数功能
TreeLeafSize 函数用于确定给定二叉树中的叶子节点数量。
二、实现思路
1. 首先判断根节点是否为 NULL 。如果是，则表示这是一棵空树，没有叶子节点，直接返回 0。
2. 如果根节点不为空，接着判断该节点是否为叶子节点，即判断其左子树和右子树是否都为 NULL 。如果是叶子节点，则返回 1。
3. 如果不是叶子节点，则分别递归计算左子树中的叶子节点个数 TreeLeafSize(root->left) 和右子树中的叶子节点个数 TreeLeafSize(root->right) ，然后将这两个值相加并返回，从而得到整个二叉树的叶子节点个数。
// 叶子节点的个数
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);
}6.销毁函数.
这段 C 语言代码实现了销毁二叉树的功能。
一、函数功能
DestoryTree 函数用于释放给定二叉树所占用的内存空间，实现二叉树的销毁。
二、实现思路
采用后序遍历的方式，先递归销毁左子树和右子树，最后释放根节点的内存并将根节点指针置为 NULL ，以防止悬空指针。
1. 首先判断根节点是否为 NULL 。如果是，则直接返回，因为空树无需销毁。
2. 如果根节点不为空，则先递归调用 DestoryTree 函数销毁左子树 root->left 。
3. 接着递归调用 DestoryTree 函数销毁右子树 root->right 。
4. 当左子树和右子树都被销毁后，使用 free(root) 释放根节点所占用的内存空间。
5. 最后将根节点指针置为 NULL ，防止出现悬空指针。这样就完成了整个二叉树的销毁。
//如果要摧毁的话，参数需要结构体指针的地址
void DestoryTree(BTNode* root)
{if (root = NULL)return;DestoryTree(root->left);DestoryTree(root->right);free(root);root = NULL;
}