数据结构-二叉树
树的相关概念：
1、节点的度：树中一个节点的孩子个数称为该节点的度， 所有节点的度的最大值是树的度
2、分支节点：度大于0的节点称为分支节点
3、叶子结点：度为0的节点称为叶子结点
4、节点的层次（深度）：从上往下数，根节点为1层，依次往下加1
5、树的高度（深度）：树中节点的最大层次
6、树中节点的各子树从左至又是有次序的，不能互换，则该树称为有序树，否则称为无序树
7、双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
8、孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
9、兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
10、森林：森林是m（m >= 0 )棵互不相交的树的集合，
11、树去掉根节点就成为森林，森林加上根节点就是树
1.逻辑结构：树形结构（元素之间存在一对二关系）
2.存储结构：既可以顺序存储，也可以链式存储
注意：如果是顺序存储，必须是完全二叉树，如果是普通二叉树，需要转换成完全二叉树，在进行存储，
会造成内存浪费，推荐使用链式存储3.二叉树链式存储适用于所有的二叉树
二叉树的性质：
1、二叉树的度数为2
2、二叉树严格区分左子树和右子树
3、二叉树的第k层上最多有2^(k-1)个节点
4、深度为k的二叉树，最多有2^k + 1个节点
5、任意一棵二叉树，叶子结点的个数比度数为2的节点个数多1
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
//定义二叉树的结构体
typedef char BT;
typedef struct BTreeBode {
BT val;//存放二叉树节点元素值
struct BTreeBode* left;//指向左子节点
struct BTreeBode* right;//指向右子节点
}BTN;//创建二叉树的三个函数
void init_tree(BTN** bt);
void init_tree1(BTN** bt);
void init_tree2(BTN** bt);void PreOrder(BTN* bt);
void MidOrder(BTN* bt);
void EndOrder(BTN* bt);int main() {
BTN* bt = NULL;//二叉树的根节点指针
//二叉树的初始化
printf("请先序创建一个二叉树\n");
init_tree(&bt);printf("请中序创建一个二叉树\n");
init_tree1(&bt);printf("请后序创建一个二叉树\n");
init_tree2(&bt);//先序遍历
PreOrder(bt);
printf("\n");//中序遍历
MidOrder(bt);
printf("\n");//后序遍历
EndOrder(bt);
return 0;
}
//先序创建：根左右 初始化函数，就是把树的所有节点存进去的过程
void init_tree(BTN** bt) {
BT val = 0;
scanf("%c", &val); //%c,一次只接收一个字符
if (val == '#') {
//空树
*bt = NULL;
}
else {
//创建新节点
*bt = (BTN*)malloc(sizeof(BTN));
(*bt)->val = val;
init_tree(&(*bt)->left);//创建左子树
init_tree(&(*bt)->right);//创建右子树
}
}//中序创建：左根右 初始化函数，就是把树的所以节点存进去的过程
void init_tree1(BTN** bt) {
BT val = 0;
scanf("%c", &val); //%c,一次只接收一个字符
if (val == '#') {
//空树
*bt = NULL;
}
else {
//创建新节点
*bt = (BTN*)malloc(sizeof(BTN));
init_tree1(&(*bt)->left);//创建左子树
(*bt)->val = val;
init_tree1(&(*bt)->right);//创建右子树
}
}//后序创建：左右根 初始化函数，就是把树的所以节点存进去的过程
void init_tree2(BTN** bt) {
BT val = 0;
scanf(" %c", &val); //%c,一次只接收一个字符
if (val == '#') {
//空树
*bt = NULL;
}
else {
//创建新节点
*bt = (BTN*)malloc(sizeof(BTN));
init_tree2(&(*bt)->left);//创建左子树
init_tree2(&(*bt)->right);//创建右子树
(*bt)->val = val;
}
}
//先序遍历函数 根 左 右 A B C D E
void PreOrder(BTN* bt) {
if (bt == NULL) {
return;
}
printf("%c ", bt->val);
PreOrder(bt->left);//左子树
PreOrder(bt->right);//右子树
}//中序遍历函数 左 根 右 C B D A E
void MidOrder(BTN* bt) {
if (bt == NULL) {//递归调用
return;
}
MidOrder(bt->left);//左子树
printf("%c ", bt->val);
MidOrder(bt->right);//右子树
}//后序遍历函数 左 右 根 C D B E A
void EndOrder(BTN* bt) {
if (bt == NULL) {//递归调用
return;
}
EndOrder(bt->left);//左子树
EndOrder(bt->right);//右子树
printf("%c ", bt->val);
}
原文地址：https://blog.csdn.net/m0_68557555/article/details/145290672
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！