请问用二叉树的顺序存储结构存储数据，是什么意思？

来源：蜘蛛抓取(WebSpider) 时间：2022-07-04 19:39 标签： 二叉树的顺序存储结构图

设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为1，中序遍历序列为2，后序遍历序列为3。

网友您好，请在下方输入框内输入要搜索的题目：

网友您好，请在下方输入框内输入要搜索的题目：

已知一棵二叉树的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，写出该二叉树的先序遍历序列。

设一棵二叉树的前序序列为abdecf，后序序列为debfca，则该二叉树中序遍历的顺序是（)。

已知一棵二叉树的后序遍历序列为EICBGAHDF，同时知道该二叉树的中序遍历序列为CEIFGBADH，试画出该二叉树。【重庆大学2000二、2】

请帮忙给出正确答案和分析，谢谢！

设一棵二叉树的中序序列为badce，后序遍历为bdeca，则该二叉树前序適历的顺顺序是（)。

假设一棵二叉树的中序序列为DCBGEAHFIK，后序序列为DCEGBFHKIA。请写出该二叉树的先序遍历序列。

二叉树结点数值采用顺序存储结构，如图所示。
②写出前序遍历，中序遍历和后序遍历的结果。
③写出值为c的结点的父结点及其左、右孩子。
④画出把此二叉树还原成森林的图。

一棵非空二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足()。

A、所有的结点均无左孩子

B、所有的结点均无右孩子

一棵二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为()

本文章向大家介绍树与二叉树知识点总结(一)，主要包括树与二叉树知识点总结(一)使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

　　树是\(N(N>0)\)个结点的有限集合，\(N=0\)时，称为空树，这是一种特殊情况，在任意一颗非空树中应满足:

  1. 有且仅有一个特定的称为根的结点
  2. 当\(N>1\)时，其余结点可分为\(m(m>0)\)个互不相交的有限集合\(T_1,T_2,……,T_m\),其中每个集合本身又是一棵树，并且称为根结点的子树
  • 根节点没有前驱结点，其他节点有且只有一个前驱结点
  • 所有节点可以有零个或者多个后继结点
  • 树是一种递归的数据结构，适合于表示所有层次结构的数据

    • 祖先结点:根结点到该结点的唯一路径的任意节点
  • 双亲结点:根结点到该结点的唯一路径上最接近该结点的结点
  • 兄弟节点:具有相同双亲结点的结点

  • 树的度:树中所有结点的度数的最大值

  • 结点的层次、深度、高度

    • 层次:根为第一层、它的孩子为第二层，以此类推
    • 深度:根结点开始自顶向下累加
    • 高度:叶子结点开始自底向上累加

  • 树的高度(深度)、路径、路径长度

    • 树的高度(深度):树中结点的最大层数

    • 路径:又两个结点之间所经过的结点序列构成的

    • 路径长度:路径上所经过的边的个数

      由于树种的分支是有向的，即从双亲指向孩子，所以数中的路径是自上而下的，同一双亲的两个孩子之间不存在路径

  1. 树中的结点数等于所有结点的度数加1。

　　不难想象，除根结点以外，每个结点有且仅有一个指向它的前驱结点。也就是说每个结点和指向它的分支一一对应。
　　假设树中一共有\(b\)个分支，那么除了根结点，整个树就包含有\(b\)个结点，所以整个树的结点数就是这\(b\)个结点加上根结点，设为\(n\)，则\(n=b+1\)。而分支数\(b\)也就是所有结点的度数，证毕。

  1. 度为\(m\)的树中第\(i\)层上至多结点树如下

　　首先考虑\(i=1\)的情况：第一层只有根结点，即一个结点，\(i=1\)带入式子满足。
　　假设第\(i-1\)层满足这个性质，第\(i-1\)层最多有\(m^{i-2}\)个结点，又因为树的度为\(m\),所以对于第\(i-1\)层的每个结点，最多有\(m\)个孩子结点。所以第\(i\)层的结点数最多是\(i-1\)层的\(m\)倍，所以第\(i\)层上最多有\(m

  1. 高度为\(h\)的\(m\)叉树至多的节点数如下
  1. 具有\(n\)个结点的\(m\)叉树的最小高度如下
  1. 树结点与度之间的关系有

　　双亲表示法:用一组连续的存储空间存储树的结点，同时在每个结点中，用一个变量存储该结点的双亲结点在数组中的位置。

优点:可以很快得到每个结点的双亲结点

缺点:求结点的孩子需要遍历整个结构

把每个结点的孩子结点排列起来存储成一个单链表。所以\(n\)个结点就有\(n\)个链表；
如果是叶子结点，那这个结点的孩子单链表就是空的；
然后\(n\)个单链表的的头指针又存储在一个顺序表（数组）中。

优点:寻找子女非常直接

缺点:寻找双亲需要便利\(N\)个结点的孩子链表指针域所只想的\(N\)个孩子链表

　　孩子兄弟表示法：顾名思义就是要存储孩子和孩子结点的兄弟，具体来说，就是设置两个指针，分别指向该结点的第一个孩子结点和这个孩子结点的右兄弟结点。

优点:方便实现转换为二叉树，易于查找结点的孩子

缺点:从当前结点查找其双亲结点比较麻烦

二叉树是\(n(n≥0)\)个结点的有限集合:

  1. 或者为空二叉树，即 \(n=0\)
  2. 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

　　每个结点至多有两颗子树，左右子树的顺序不能颠倒，二叉树与度为2的有序树不同,不同的原因是度为2的树要求每个节点最多只能有两棵子树，并且至少有一个节点有两棵子树。二叉树的要求是度不超过2，节点最多有两个叉，可以是1或者0。

  • 根结点既有左子树又有右子树

  • 斜树:每个结点只有左结点或者每个结点只有右结点
  • 满二叉树:树种每一层都含有最多的结点，对于编号\(i\)的结点，期双亲结点为\(\lfloor i/2\rfloor\)
  • 完全二叉树：每一个结点都与高度为h的满二叉树编号\(1-n\)相同；如果\(i≤n/2\)下，则结点\(i\)为分支结点，否则为叶子结点
  • 二叉排序树：左子树均小于根结点，右子树均大于根结点
  • 平衡二叉树：左右子树的深度之差不超过1

  1. 非空二叉树上的叶子结点数等于度为2的节点数加一，即 \(n_0=n_2+1\)

　　二叉树的顺序存储结构就是用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。

　　优点：适合完全二叉树和满二叉树，序号可以反映出结点之间的逻辑关系，可以节省空间
　　缺点：适合一般二叉树，只能添加一些空结点，空间利用率低

　　二叉树每个结点最多两个孩子，所以设计二叉树的结点结构时考虑两个指针指向该结点的两个孩子。

//先序遍历非递归算法

//中序遍历非递归算法

非递归代码如下(重难点！！！):

r=NULL;//指向最近访问过的节点，辅助指针 //1、从根结点到最左下角的左子树都入栈 else{ //返回栈顶的两种情况 //1、右子树存在且未访问过， //2、右子树已经访问或空，接下来出栈访问结点 r=p; //指针访问过的右子树根结点 p=NULL;//访问完之后就重置P，每次从栈中弹出一个，防止进入第一个if

难点:要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点

我要回帖

更多关于 二叉树的顺序存储结构图 的文章

 

随机推荐