广安发展建设集团门户网站,建设英文网站要求,微信客户管理系统,网站建设神州互动目录
一、树的概念 二、树结点之间的关系
三、二叉树 1、满二叉树
2、完全二叉树
四、二叉树的存储 1、顺序存储
2、链式存储 一、树的概念 如果数据和数据之间满足一对多的关系#xff0c;将其逻辑结构称之为树 如下图#xff1a;树的根与树的分支存在一对多的关系 将上…目录
一、树的概念 二、树结点之间的关系
三、二叉树 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、链式存储 先序中序后序创建。由于是单向链表前者结点可以找到后者结点但是后者结点不好找前者结点。所以使用先序创建。 结点的表示 包含了数据域、指向左子树的指针和指向右子树的指针 数据域存放的数据 指向左子树的指针存放左子树的地址 指向右子树的指针存放右子树的地址 使用链式存储方式实现二叉树的创建和遍历,创建如下图的二叉树 //二叉树的应用
#includestdio.h
#includestdlib.h
#includestdbool.h
//创建根节点
struct tree_node
{char date;struct tree_node *left;//左树指针struct tree_node *right;//右树指针
};
//先序创建
//利用递归创建二叉树,返回类型为下一个结点的地址,实现递归创建
struct tree_node * tree_create()
{struct tree_node *nodeNULL;//创建一个指针存放节点地址初始化为空char str;//用来存储创建的数据scanf( %c,str);//从终端获取要创建的二叉树if(str#)//如果接受到字符#即这个结点没有return NULL;node(struct tree_node*)malloc(sizeof(struct tree_node));//新创建的结点if(nodeNULL){printf(结点创建失败\n);return NULL;}node-datestr;//递归创建左子树node-lefttree_create();//递归创建右子树node-righttree_create();return node;
}
//先序遍历
bool tree_erg_fir(struct tree_node *root)
{if(rootNULL){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(rootNULL){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(rootNULL){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 *roottree_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
