数据结构完全二叉树 二叉树？

来源：蜘蛛抓取(WebSpider) 时间：2022-11-27 12:46 标签： 数据结构完全二叉树

数据结构分线性存储结构和非线性存储结构，前面说的顺序表，单链表，双链表，栈，队列都属于线性结构，线性结构的特别是集合中必存在唯一的一个"第一个元素，集合中必存在唯一的一个"最后的元素"；除最后元素之外，其它数据元素均有唯一的"后继"；除第一元素之外，其它数据元素均有唯一的"前驱"。大家注意的是唯一2个字，也就是说线性结构不可能存在2个或多个前驱结点，同样不可能出现2个或多个后继结点，现在我们说下2叉树，很明显是非线性的因为它有2个后继结点。

父母结点：结点的前驱节点称为父母结点

孩子结点：结点的后继节点称为孩子结点

兄弟结点：拥有同一父母的结点称为兄弟结点

度：结点拥有子树的的个数（后继节点的个数）没有后继结点的称为叶子结点（树的度指的是所有结点中度最大的）

结点层次：指的是按照这个结点算起来的高度。

树的高度：就是树的层次。

 三：树的抽象接口

* 判断二叉树是否为null * 返回二叉树节点个数 * 查找并返回首次出现关键字为key的元素节点 * 返回弄得节点的父节点 * 插入p的孩子节点（leftchild验证为左子树还是右子树） * 删除p节点的左或者右子树

现在我先画一个很简单的树来帮助理解

首先我们应该定义一个根，如果这个根空，则表示是空树。比如上面这颗树我们怎么计算他结点的个数呢，我们采取的方式是计算左子树的个数+右子树的个数+根不就是么，我们采用递归的思想来解决。

现在有几种情况，第一这个父结点左子树为null右子树不为null；第二右子树为null左子树不为null，第三都不为null。第一种情况我们只需要把要删除的p结点替换它的右子树即可，第二种情况我们同样把删除的p结点替换成它的左子树。第三种情况，既然删除父结点p我们只要需要把p结点的右子树中最小的结点赋值给这个删除的p结点即可，然后置空p结点右子树中的最小结点

}//找到要删除节点的节点

然后我们考虑一下特别情况，比如这颗树 本身是叶子结点，或者度为1，那么直接进行转换就可以

树是一种数据结构，由n（n>=1）个有限结点组成的一个具有层次关系的集合。每颗树都有一个根结点，根结点下有若干个子结点，每一个非根结点有且只有一个父结点。除了根结点外，每个子结点又可以分为多个不相交的子树。

①结点：包含一个数据元素及若干指向子树分支的信息。
②结点的度：一个结点拥有子树的数目称为结点的度。
③叶子结点：也称为终端结点，没有子树的结点或者度为零的结点。
④分支结点：也称为非终端结点，度不为零的结点称为非终端结点。
⑤树的度：树中所有结点的度的最大值。
⑥结点的层次：从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子节点位于第L+1层。
⑦树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度。
⑧有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树。
⑨无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树。
⑩森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根结点删除，则该树就变成了一片森林，森林中的树由原来根结点的各棵子树构成

为什么需要树这种数据结构

1 数组存储方式的分析
优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。
缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低

2 链式存储方式的分析
优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可， 删除效率也很好)。
缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)

能提高数据存储，读取的效率, 比如利用二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。

树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树

  • (01) 每个节点有零个或多个子节点；
  • (02) 没有父节点的节点称为根节点；
  • (03) 每一个非根节点有且只有一个父节点；
  • (04) 除了根节点外，每个子节点可以分为多个不相交的子树。

性质1：二叉树第i层上的结点数目最多为 2^(i-1) (i≥1)。
性质2：深度为k的二叉树至多有2^k-1个结点(k≥1)。
性质3：包含n个结点的二叉树的高度至少为log2 (n+1)。
性质4：在任意一棵二叉树中，若叶子结点的个数为n0，度为2的结点数为n2，则n0=n2+1。即度为0的节点个数总比度为2的节点个数多一个
性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：
当i=1时，该节点为根，它无双亲节点。
当i>1时，该节点的双亲节点的编号为i/2。
若2i≤n，则有编号为2i的左节点，否则没有左节点。
若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点。

如果该二叉树的所有叶子节点都在最后一层，每个节点的孩子节点要么没有，要么就是两个，不允许出现单个孩子的情况，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树。
特点：满二叉树的叶子节点出现在最下层且连续不中断，非叶子节点的度一定是2

如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，每层节点添加，必须是从左到右，不允许跳着添加 。我们称为完全二叉树。

1 叶子结点只能出现在最下层和次下层。
2 最下层的叶子结点集中在树的左部。
3 倒数第二层若存在叶子结点，一定在右部连续位置。
4 如果结点度为1，则该结点只有左孩子，即没有右子树。
5 同样结点数目的二叉树，完全二叉树深度最小。
6 满二叉树一定是完全二叉树，但反过来不一定成立

前序遍历：先遍历父节点，在输出左子树然后输出右子树
中序遍历：先遍历左子树，然后输出父节点和右子树
后续遍历：先遍历左子树和右子树，然后输出父节点
层次遍历： 按照树的层次自上而下的遍历二叉树

若已知前序遍历序列和中序遍历序列，则可以确定一棵二叉树。
若已知后序遍历序列和中序遍历序列，则可以确定一棵二叉树。
若已知前序遍历序列和后序遍历序列，不可以唯一确定一棵二叉树。

使用数组的存储方式和树的存储方式可以互相转换
在遍历数组的时候，仍然可以前序遍历，中序遍历和后序遍历的方式来完成二叉树节点的遍历
当二叉树为完全二叉树时，结点数刚好填满数组。不是完全二叉树则顺序存储结构中可能会出现了空间浪费的情况。故顺序存储一般适用于完全二叉树。

1 顺序二叉树通常只考虑完全二叉树

n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）

这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种

目的：让二叉树的各个节点的左右指针充分利用

1 顺序存储化二叉树方式创建二叉树
2 二叉树的遍历–递归、非递归、层次遍历

我要回帖

更多关于 数据结构完全二叉树 的文章

 

随机推荐