数据结构——树和二叉树
目录
一、树的概念
二、树结点之间的关系
三、二叉树
1、满二叉树
2、完全二叉树
四、二叉树的存储
1、顺序存储
2、链式存储
一、树的概念
如果数据和数据之间满足一对多的关系，将其逻辑结构称之为树
如下图：树的根与树的分支存在一对多的关系
将上图具体化，从根节点开始，每个节点都有一个或者多个分支，当然还有没有分支的情况
- 如果数据和数据之间满足一对多的关系，将其逻辑结构称之为树。
- 逻辑关系：树形关系
- 存储关系：顺序存储 链式存储
- 每棵子树的根节点有且仅有一个直接前驱，但是可以有0个或者多个后继。
- 子树：一个结点及其下面的所有结点组成的树。
二、树结点之间的关系
- 根节点：最上层的第一个结点，每棵树有且仅有一个根节点。根节点没有前驱
- 父结点：上一层与自己紧挨着的结点，称之为双亲结点。
- 子结点：下一层与自己紧挨着的结点。
- 兄弟结点：
- 堂兄弟结点：
- 叶子结点：没有子结点的结点
-------------------------------------
- 度：
- 结点的度：该结点的子结点个数。
- 树的度：该树中节点的最大的度
- 层数：
- 根结点的层数是1
- 结点的层数：父结点层数+1
- 深度：
- 从根结点出发，到最底层的层数
举个例子：
上图当中：A称为根，BCD是A的子结点，称A是BCD的父结点，B,C,D之间是兄弟结点，E和G是堂兄弟结点，这个关系可以参考家庭之间的关系
叶子结点（终端结点）：比如E,F没有后继结点的结点称为叶子结点
分支结点（非叶子结点）：有后继结点，比如G结点
A的度：3 B的度：2 D的度：4 上图树的度：4 上图树的层数：4
A所在层数：1 C所在层数：2
4.有序树与无序树
1.如果将树中结点的各个子树看成是从左往右有次序的（即不能交换），则称该树为有序树，否则称为无序树
森林：多个树组成的一个集合，树之间不存在关系，每棵树都独立存在
如下图三个树的集合：
三、二叉树
二叉树是树的一种特殊形式，即每个分支最多只有两个子结点
1、满二叉树
每个结点的度都为2，即每个结点都有两个子节点，（即二叉树中每个结点的子结点都是满的）
2、完全二叉树
在满二叉树的最底层，最右边，删除n个连续结点，形成的二叉树称之为完全二叉树。
完全二叉树的特点：
- 叶子结点只能出现在最下层和次下层
- 最下层的叶子结点集中在树的左边
- 倒数第2层的叶子结点，一定在右边连续位置
- 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
几种常见的完全二叉树：
完全二叉树的编号方式：按照顺序编号
四、二叉树的存储
1、顺序存储
- 二叉树的顺序存储，就是使用一个一维数组存储二叉树结点中的数据，且结点的编号位置就是数组的下标索引。
- 只有在完全二叉树的情况下才能填满数组
- 当为不完全二叉树的时候，会造成大量的空间浪费。所以一般不使用顺序存储。
2、链式存储
- 先序，中序，后序创建。
- 由于是单向链表前者结点可以找到后者结点，但是后者结点不好找前者结点。
- 所以使用先序创建。
结点的表示：
包含了数据域、指向左子树的指针和指向右子树的指针
数据域：存放的数据
指向左子树的指针：存放左子树的地址
指向右子树的指针：存放右子树的地址
使用链式存储方式实现二叉树的创建和遍历,创建如下图的二叉树
//二叉树的应用
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
//创建根节点
struct tree_node
{char date;struct tree_node *left;//左树指针struct tree_node *right;//右树指针
};
//先序创建
//利用递归创建二叉树,返回类型为下一个结点的地址,实现递归创建
struct tree_node * tree_create()
{struct tree_node *node=NULL;//创建一个指针存放节点地址，初始化为空char str;//用来存储创建的数据scanf(" %c",&str);//从终端获取要创建的二叉树if(str=='#')//如果接受到字符#，即这个结点没有return NULL;node=(struct tree_node*)malloc(sizeof(struct tree_node));//新创建的结点if(node==NULL){printf("结点创建失败\n");return NULL;}node->date=str;//递归创建左子树node->left=tree_create();//递归创建右子树node->right=tree_create();return node;
}
//先序遍历
bool tree_erg_fir(struct tree_node *root)
{if(root==NULL){return false;}printf("%c",root->date);tree_erg_fir(root->left);tree_erg_fir(root->right);
}
//中序遍历
bool tree_erg_middle(struct tree_node *root)
{if(root==NULL){return false;}tree_erg_middle(root->left);printf("%c",root->date);tree_erg_middle(root->right);
}
//后序遍历
bool tree_erg_behind(struct tree_node *root)
{if(root==NULL){return false;}tree_erg_behind(root->left);tree_erg_behind(root->right);printf("%c",root->date);
}
int main(int argc, const char *argv[])
{printf("请输入二叉树，创建方式为先序创建:\n");struct tree_node *root=tree_create();//先序遍历tree_erg_fir(root);printf("\n");//中序遍历tree_erg_middle(root);printf("\n");//后序遍历tree_erg_behind(root);printf("\n");return 0;
}
输出如下;
请输入二叉树，创建方式为先序创建:
ABDE###F##CM###
ABDEFCM
EDBFAMC
EDFBMCA