索引存储二叉树

❶ oracle的B树索引到底是不是基于二叉树

B-Tree索引是最常见的索引结构，默认创建的索引就是B-Tree索引。
一、B树索引的结构
B-树索引是基于二叉树结构的。B-树索引结构有3个基本组成部分：根节点、分支节点和叶子节点。其中根节点位于索引结构的最顶端，而叶子节点位于索引结构的最底端，中间为分子节点。
叶子节点（Leaf node）：包含条目直接指向表里的数据行。
分支节点（Branch node）：包含的条目指向索引里其他的分支节点或者是叶子节点。
根节点（Branch node）：一个B树索引只有一个根节点，它实际就是位于树的最顶端的分支节点。
可以用下图一来描述B树索引的结构。其中，B表示分支节点，而L表示叶子节点。
clip_image001
1.1关于分支节点块（包括根节点块）
1、 其所包含的索引条目都是按照顺序排列的（缺省是升序排列，也可以在创建索引时指定为降序排列）。
2、 每个索引条目（也可以叫做每条记录）都具有两个字段。第一个字段表示当前该分支节点块下面所链接的索引块中所包含的最小键值；第二个字段为四个字节，表示所链接的索引块的地址，该地址指向下面一个索引块。
3、 在一个分支节点块中所能容纳的记录行数由数据块大小以及索引键值的长度决定。比如从上图一可以看到，对于根节点块来说，包含三条记录，分别为（0 B1）、（500 B2）、（1000 B3），它们指向三个分支节点块。其中的0、500和1000分别表示这三个分支节点块所链接的键值的最小值。而B1、B2和B3则表示所指向的三个分支节点块的地址。
1.2关于叶子节点
1、 B树索引的所有叶子块一定位于同一层上，这是由B树的数据结构定义的。Oracle 设计的B树索引结构保证了B 树索引从根到叶子都有相等的分支节点，保证了B树索引的平衡，这样就不会因为基表的数据插入后删除操作造成B树索引变得不平衡，从而影响索引的性能。因此，从根块到达任何一个叶子块的遍历代价都是相同的； 索引高度是指从根块到达叶子块时所遍历的数据块的个数，通常，大多数的B树索引的高度都是2到3，也就意味着，即使表中有上百万条记录，从索引中定位一个键字只需要2或3次I/O,索引越高，性能越差；
2、 叶子节点所包含的索引条目与分支节点一样，都是按照顺序排列的（缺省是升序排列，也可以在创建索引时指定为降序排列）
3、 每个索引条目（也可以 叫做每条记录）也具有两个字段。第一个字段表示索引的键值，对于单列索引来说是一个值；而对于多列索引来说则是多个值组合在一起的。第二个字段表示键值所对应的记录行的ROWID，该ROWID是记录行在表里的物理地址。ROWID 是唯一的Oracle 指针，指向该行的物理位置，使用ROWID 是Oracle 数据库中访问行最快的方法。参照Oracle中的rowid
4、 叶子节点其实是一个双向链表，每个叶子节点包含一个指向下一个和上一个叶子点的指针，这样在一定范围内便利索引以搜索需要的记录。
clip_image002
clip_image004
二、B树索引的访问
当oracle进程需要访问数据文件里的数据块时，oracle会有两种类型的I/O操作方式：
1） 随机访问，每次读取一个数据块（通过等待事件“db file sequential read”体现出来）。
2） 顺序访问，每次读取多个数据块（通过等待事件“db file scattered read”体现出来）。
第一种方式则是访问索引里的数据块，而第二种方式的I/O操作属于全表扫描。这里顺带有一个问题，为何随机访问会对应到db file sequential read等待事件，而顺序访问则会对应到db file scattered read等待事件呢？这似乎反过来了，随机访问才应该是分散（scattered）的，而顺序访问才应该是顺序（sequential）的。其实，等待事件主要根据实际获取物理I/O块的方式来命名的，而不是根据其在I/O子系统的逻辑方式来命名的。下面对于如何获取索引数据块的方式中会对此进行说明。
事实上在B树索引虽然为一个树状的立体结构，但其对应到数据文件里的排列当然还是一个平面的形式，也就是像下面这样。
/根/分支/分支/叶子/…/叶子/分支/叶子/叶子/…/叶子/分支/叶子/叶子/…/叶子/分支/.....
因此，当oracle需要访问某个索引块的时候，势必会在这个结构上跳跃的移动。
当oracle需要获得一个索引块时，首先从根节点开始，根据所要查找的键值，从而知道其所在的下一层的分支节点，然后访问下一层的分支节点，再次同样根据键值访问再下一层的分支节点，如此这般，最终访问到最底层的叶子节点。可以看出，其获得物理I/O块时，是一个接着一个，按照顺序，串行进行的。在获得最终物理块的过程中，我们不能同时读取多个块，因为我们在没有获得当前块的时候是不知道接下来应该访问哪个块的。因此，在索引上访问数据块时，会对应到 db file sequential read等待事件，其根源在于我们是按照顺序从一个索引块跳到另一个索引块，从而找到最终的索引块的。
那么对于全表扫描来说，则不存在访问下一个块之前需要先访问上一个块的情况。全表扫描时，oracle知道要访问所有的数据块，因此唯一的问题就是尽可能高效的访问这些数据块。因此，这时oracle可以采用同步的方式，分几批，同时获取多个数据块。这几批的数据块在物理上可能是分散在表里的，因此其对应到db file scattered read等待事件。
三、DML对B树索引的影响
3.1 INSERT
在每个INSERT操作过程中，关键字必须被插入在正确叶节点的位置。如果叶节点已满，不能容纳更多的关键字，就必须将叶节点拆分。拆分的方法有两种：
1)如果新关键字值在所有旧叶节点块的所有关键字中是最大的，那么所有的关键字将按照99:1的比例进行拆分，使得在新的叶节点块中只存放有新关键字，而其他的所有关键字（包括所有删除的关键字）仍然保存在旧叶节点块中。
2)如果新关键字值不是最大的，那么所有的关键字将按照50:50的比例进行拆分，这时每个叶节点块（旧与新）中将各包含原始叶节点中的一半关键字。
这个拆分必须通过一个指向新叶节点的新入口向上传送到父节点。如果父节点已满，那么这个父节点也必须进行拆分，并且需要将这种拆分向上传送到父节点的父节点。这时，如果这个父节点也已满，将继续进行这个过程。这样，某个拆分可能最终被一直传送到根节点。如果根节点满了，根结点也将进行分裂。根结点在进行分裂的时候，就是树的高度增加的时候。根节点进行分裂的方式跟其他的的节点分裂的方式相比较，在物理位置上的处理也是不同的。根节点分裂时，将原来的根结点分裂为分支节点或叶节点，保存到新的块中，而将新的根节点信息保存到原来的根结点块中，这样做的是为因为避免修改数据字典所带来的相对较大的开销。
注意：现在Oracle都是采用了平衡算法，正常情况下即使索引关键字不断增大，也不会产生不平衡树。当索引关键字不断增大，导致树级别单方向增长时，Oracle会自动进行索引翻转以维持索引的平衡，当然这种操作非常消耗资源
在索引的每一个层次之间，每一个层最左边的节点的block头部都有一个指向下层最左边的块的指针，这样有利于fast full scan 的快速定位最左边的叶子节点。
每个拆分过程都是要花费一定的开销的，特别是要进行物理硬盘I/O动作。此外，在进行拆分之前，Oracle必须查找到一个空块，用来保存这个拆分。可以用以下步骤来进行查找空块的动作：
1) 在索引的自由列表(free-list, 又称为空闲列表) 中查到一个空闲块，可以通过CREATE/ALTER INDEX命令为一个索引定义多个空闲列表。索引空闲列表并不能帮助Oracle查找一个可用来存放将要被插入的新关键字的块。这是因为关键字值不能随机地存放在索引中可用的第一个“空闲”叶节点块中，这个值必须经过适当的排序之后，放置在某个特定的叶节点块中。只有在块拆分过程中才需要使用索引的空闲列表，每个空闲列表都包含有一个关于“空”块的链接列表。当为某个索引定义了多个空闲列表时，首先将从分配给进程的空间列表中扫描一个空闲块。如果没有找到所需要的空闲块，将从主空闲列表中进行扫描空闲块的动作。
2) 如果没有找到任何空闲块，Oracle将试图分配另一个扩展段。如果在表空间中没有更多的自由空间，Oracle将产生错误ORA-01654。
3) 如果通过上述步骤，找到了所需的空闲块，那么这个索引的高水位标(HWM)将加大。
4) 所找到的空闲块将用来执行拆分动作。
在创建B*树索引时，一个需要注意的问题就是要避免在运行时进行拆分，或者，要在索引创建过程中进行拆分（“预拆分”），从而使得在进行拆分时能够快速命中，以便避免运行时插入动作。当然，这些拆分也不仅仅局限于插入动作，在进行更新的过程中也有可能会发生拆分动作。
3.2 UPDATE
索引更新完全不同于表更新，在表更新中，数据是在数据块内部改变的（假设数据块中有足够的空间来允许进行这种改变）；但在索引更新中，如果有关键字发生改变，那么它在树中的位置也需要发生改变。请记住，一个关键字在B*树中有且只有一个位置。因此，当某个关键字发生改变时，关键字的旧表项必须被删除，并且需要在一个新的叶节点上创建一个新的关键字。旧的表项有可能永远不会被重新使用，这是因为只有在非常特殊的情况下， Oracle才会重用关键字表项槽，例如，新插入的关键字正好是被删除的那个关键字（包括数据类型、长度等等）。（这里重用的是块，但完全插入相同的值的时候，也不一定插入在原来的被删除的位置，只是插入在原来的块中，可能是该块中的一个新位置。也正因为如此，在索引块中保存的的记录可能并不是根据关键字顺序排列的，随着update等的操作，会发生变化。）那么，这种情况发生的可能性有多大呢？许多应用程序使用一个数列来产生NUMBER关键字（特别是主关键字）。除非它们使用了RECYCLE选项，否则这个数列将不会两次产生完全相同的数。这样，索引中被删除的空间一直没有被使用。这就是在大规模删除与更新过程中，表大小不断减小或至少保持不变但索引不断加大的原因。
3.3 DELETE
当删除表里的一条记录时，其对应于索引里的索引条目并不会被物理的删除，只是做了一个删除标记。当一个新的索引条目进入一个索引叶子节点的时候，oracle会检查该叶子节点里是否存在被标记为删除的索引条目，如果存在，则会将所有具有删除标记的索引条目从该叶子节点里物理的删除。
当一个新的索引条目进入索引时，oracle会将当前所有被清空的叶子节点（该叶子节点中所有的索引条目都被设置为删除标记）收回，从而再次成为可用索引块。
尽管被删除的索引条目所占用的空间大部分情况下都能够被重用，但仍然存在一些情况可能导致索引空间被浪费，并造成索引数据块很多但是索引条目很少的后果，这时该索引可以认为出现碎片。而导致索引出现碎片的情况主要包括：
1、不合理的、较高的PCTFREE。很明显，这将导致索引块的可用空间减少。
2、索引键值持续增加（比如采用sequence生成序列号的键值），同时对索引键值按照顺序连续删除，这时可能导致索引碎片的发生。因为前面我们知道，某个索引块中删除了部分的索引条目，只有当有键值进入该索引块时才能将空间收回。而持续增加的索引键值永远只会向插入排在前面的索引块中，因此这种索引里的空间几乎不能收回，而只有其所含的索引条目全部删除时，该索引块才能被重新利用。
3、经常被删除或更新的键值，以后几乎不再会被插入时，这种情况与上面的情况类似。
四、总结
通过上面对B树的分析，可以得出以下的应用准则：
1、避免对那些可能会产生很高的更新动作的列进行索引。
2、避免对那些经常会被删除的表中的多个列进行索引。若有可能，只对那些在这样的表上会进行删除的主关键字与/或列进行索引。如果对多个列进行索引是不可避免的，那么就应该考虑根据这些列对表进行划分，然后在每个这样的划分上执行TRUNCATE动作（而不是DELETE动作）。TRUNCATE在与 DROP STORAGE短语一同使用时，通过重新设置高水位标来模拟删除表与索引以及重新创建表与索引的过程。
3、避免为那些唯一度不高的列创建B*树索引。这样的低选择性将会导致树节点块的稠密性，从而导致由于索引“平铺( flat)”而出现的大规模索引扫描。唯一性的程度越高，性能就越好，因为这样能够减少范围扫描，甚至可能用唯一扫描来取代范围扫描。
4）空值不存储在单列索引中。对于复合索引的方式，只有当某个列不空时，才需要进行值的存储。在为DML语句创建IS NULL或IS NOT NULL短语时，应该切记这个问题。
5）IS NULL不会导致索引扫描，而一个没有带任何限制的IS NOT NULL则可能会导致完全索引扫描。

❷ 关于数据结构的问题

应该是A，双向链表就不说了。
首先应该了解存储表示方法有四种：
◆ 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。
◆ 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。
◆ 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。
◆ 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。

闭散列表是应该属于散列存储，是哈希算法的一种处理存储冲突方式，
当由关键码得到的哈希地址一旦产生了冲突,也就是说,该地址已经存放了数据元素,就去寻找下一个空的哈希地址,只要哈希表足够大,空的哈希地址总能找到,并将数据元素存入. 所以符合散列存储方法的要求。

而线索二叉树是索引存储，它是对二叉树以某种方式遍历后，得到二叉树中所有结点的一个线性序列。这样，二叉树中的结点就有了唯一直接前驱结点和唯一直接后继结点。
在线索二叉树时，二叉树采用二叉链表作为存储结构，每个结点有五个域leftChild,leftTag,data,rightTag,rightChild
规定：如果某结点的左指针域为空，令其指向依某种方式遍历时所得到的该结点的前驱结点，否则指向左孩子。
如果某结点的右指针域为空，令其指向依某种方式遍历时所得到的该结点的后继结点，否则指向右孩子（？？）
为了区分一个结点的指针是指向左右孩子还是指向前驱，后继结点，可用标志为来区分：
如果 leftTag/rightTag=0,那么指向左/右孩子。
如果 leftTag/rightTag=1,那么指向前驱/后继线索。
对一颗二叉树的遍历方法不同，得到的线索二叉树也不同。通常有前序线索二叉树，中序线索二叉树，后序线索二叉树。

❸ 索引的种类

二、索引类型
Mysql目前主要有以下几种索引类型：FULLTEXT，HASH，BTREE，RTREE。

1. FULLTEXT
即为全文索引，目前只有MyISAM引擎支持。其可以在CREATE TABLE ，ALTER TABLE ，CREATE INDEX 使用，不过目前只有 CHAR、VARCHAR ，TEXT 列上可以创建全文索引。

全文索引并不是和MyISAM一起诞生的，它的出现是为了解决WHERE name LIKE “%word%"这类针对文本的模糊查询效率较低的问题。

2. HASH
由于HASH的唯一（几乎100%的唯一）及类似键值对的形式，很适合作为索引。

HASH索引可以一次定位，不需要像树形索引那样逐层查找,因此具有极高的效率。但是，这种高效是有条件的，即只在“=”和“in”条件下高效，对于范围查询、排序及组合索引仍然效率不高。

3. BTREE
BTREE索引就是一种将索引值按一定的算法，存入一个树形的数据结构中（二叉树），每次查询都是从树的入口root开始，依次遍历node，获取leaf。这是MySQL里默认和最常用的索引类型。

4. RTREE
RTREE在MySQL很少使用，仅支持geometry数据类型，支持该类型的存储引擎只有MyISAM、BDb、InnoDb、NDb、Archive几种。

相对于BTREE，RTREE的优势在于范围查找。

ps. 此段详细内容见此片博文：Mysql几种索引类型的区别及适用情况

三、索引种类
普通索引：仅加速查询

唯一索引：加速查询 + 列值唯一（可以有null）

主键索引：加速查询 + 列值唯一（不可以有null）+ 表中只有一个

组合索引：多列值组成一个索引，专门用于组合搜索，其效率大于索引合并

全文索引：对文本的内容进行分词，进行搜索

ps.

索引合并，使用多个单列索引组合搜索
覆盖索引，select的数据列只用从索引中就能够取得，不必读取数据行，换句话说查询列要被所建的索引覆盖

❹ 用数组存储完全二叉树时,结点的索引(数组下标)与其父子结点索引的关系.

如果从下标从1开始存储，则编号为i的结点的主要关系为：
双亲：下取整 （i/2）
左孩子：2i
右孩子：2i+1

如果从下标从0开始存储，则编号为i的结点的主要关系为：
双亲：下取整 （(i-1)/2）
左孩子：2i+1
右孩子：2i+2

❺ 二叉树索引原理是什么

索引是为检索而存在的。如一些书籍的末尾就专门附有索引，指明了某个关键字在正文中的出现的页码位置，方便我们查找，但大多数的书籍只有目录，目录不是索引，只是书中内容的排序，并不提供真正的检索功能。可见建立索引要单独占用空间；索引也并不是必须要建立的，它们只是为更好、更快的检索和定位关键字而存在。
再进一步说，我们要在图书馆中查阅图书，该怎么办呢？图书馆的前台有很多叫做索引卡片柜的小柜子，里面分了若干的类别供我们检索图书，比如你可以用书名的笔画顺序或者拼音顺序作为查找的依据，你还可以从作者名的笔画顺序或拼音顺序去查询想要的图书，反正有许多检索方式，但有一点很明白，书库中的书并没有按照这些卡片柜中的顺序排列——虽然理论上可以这样做，事实上，所有图书的脊背上都人工的粘贴了一个特定的编号①，它们是以这个顺序在排列。索引卡片中并没有指明这本书摆放在书库中的第几个书架的第几本，仅仅指明了这个特定的编号。管理员则根据这一编号将请求的图书返回到读者手中。这是很形象的例子，以下的讲解将会反复用到它。

❻ 为什么常见索引采用b+树的数据结构而不是平衡二叉树

当记录较多时，采用平衡二叉树就会出现深度较高的情况，这样检索起来O（lgN）的效率较低，而B+树则是多路平衡树，每个节点可以存储多个数据，通过定位以后，如果在叶节点之前没找到，在相应的叶子节点中通过二叉查找，效率较高。

❼ 二叉树类及其实现

二叉树结点类

1 using System;
2 public class Node
3 {
4 //成员变量
5 private object _data; //数据
6 private Node _left; //左孩子
7 private Node _right; //右孩子
8 public object Data
9 {
10 get { return _data; }
11 }
12 public Node Left //左孩子
13 {
14 get { return _left; }
15 set { _left = value; }
16 }
17 public Node Right //右孩子
18 {
19 get { return _right; }
20 set { _right = value; }
21 }
22 //构造方法
23 public Node(object data)
24 {
25 _data = data;
26 }
27 public override string ToString()
28 {
29 return _data.ToString();
30 }
31 }
32

Node类专门用于表示二叉树中的一个结点，它很简单，只有三个属性：Data表示结点中的数据；Left表示这个结点的左孩子，它是Node类型；Right表示这个结点的右孩子，它也是Node类型。

【例6-1 BinaryTree.cs】二叉树集合类

1 using System;
2 public class BinaryTree
3 { //成员变量
4 private Node _head; //头指针
5 private string cStr; //用于构造二叉树的字符串
6 public Node Head //头指针
7 {
8 get { return _head; }
9 }
10 //构造方法
11 public BinaryTree(string constructStr)
12 {
13 cStr = constructStr;
14 _head = new Node(cStr[0]); //添加头结点
15 Add(_head, 0); //给头结点添加孩子结点
16 }
17 private void Add(Node parent, int index)
18 {
19 int leftIndex = 2 * index + 1; //计算左孩子索引
20 if (leftIndex < cStr.Length) //如果索引没超过字符串长度
21 {
22 if (cStr[leftIndex] != '#') //'#'表示空结点
23 { //添加左孩子
24 parent.Left = new Node(cStr[leftIndex]);
25 //递归调用Add方法给左孩子添加孩子节点
26 Add(parent.Left, leftIndex);
27 }
28 }
29 int rightIndex = 2 * index + 2;
30 if (rightIndex < cStr.Length)
31 {
32 if (cStr[rightIndex] != '#')
33 { //添加右孩子
34 parent.Right = new Node(cStr[rightIndex]);
35 //递归调用Add方法给右孩子添加孩子节点
36 Add(parent.Right, rightIndex);
37 }
38 }
39 }
40 public void PreOrder(Node node) //先序遍历
41 {
42 if (node != null)
43 {
44 Console.Write(node.ToString()); //打印字符
45 PreOrder(node.Left); //递归
46 PreOrder(node.Right); //递归
47 }
48 }
49 public void MidOrder(Node node) //中序遍历
50 {
51 if (node != null)
52 {
53 MidOrder(node.Left); //递归
54 Console.Write(node.ToString()); //打印字符
55 MidOrder(node.Right); //递归
56 }
57 }
58 public void AfterOrder(Node node) //后继遍历
59 {
60 if (node != null)
61 {
62 AfterOrder(node.Left); //递归
63 AfterOrder(node.Right); //递归
64 Console.Write(node.ToString()); //打印字符
65 }
66 }
67 }
68

BinaryTree是一个二叉树的集合类，它属于二叉链表，实际存储的信息只有一个头结点指针（Head），由于是链式存储结构，可以由Head指针出发遍历整个二叉树。为了便于测试及添加结点，假设BinaryTree类中存放的数据是字符类型，第5行声明了一个字符串类型成员cStr，它用于存放结点中所有的字符。字符串由满二叉树的方式进行构造，空结点用‘#’号表示（参考本章“二叉树存储结构”这一小节中的“顺序存储结构”）。图6.13所示的二叉树可表示为：“ABCDE#F”。

11～16行的构造方法传入一个构造字符串，并在Add()方法中根据这个字符串来构造二叉树中相应的结点。需要注意，这个构造方法只用于测试。

17～39行的Add()方法用于添加结点，它的第一个参数parent表示需要添加孩子结点的双亲结点，第二个参数index表示这个双亲结点的编号（编号表示使用顺序存储结构时它在数组中的索引，请参考本章“二叉树存储结构”这一小节中的“顺序存储结构”）。添加孩子结点的方法是先计算孩子结点的编号，然后通过这个编号在cStr中取出相应的字符，并构造新的孩子结点用于存放这个字符，接下来递归调用Add()方法给孩子结点添加它们的孩子结点。注意，这个方法只用于测试。

40～48行代码的PreOrder()方法用于先序遍历，它的代码跟之前所讲解的先序遍历过程完全一样。

49～57行代码的MidOrder()方法用于中序遍历。

58～66行代码的AfterOrder()方法用于后序遍历。

以上三个方法都使用了递归来完成遍历，这符合二叉树的定义。

【例6-1 Demo6-1.cs】二叉树深度优先遍历测试

1 using System;
2 class Demo6_1
3 {
4 static void Main(string[] args)
5 { //使用字符串构造二叉树
6 BinaryTree bTree = new BinaryTree("ABCDE#F");
7 bTree.PreOrder(bTree.Head); //先序遍
8 Console.WriteLine();
9 bTree.MidOrder(bTree.Head); //中序遍
10 Console.WriteLine();
11 bTree.AfterOrder(bTree.Head); //后序遍
12 Console.WriteLine();
13 }
14 }
15

运行结果：

ABDECF

DBEACF

DEBFCA

6.3.2 二叉树的宽度优先遍历

之前所讲述的二叉树的深度优先遍历的搜索路径是首先搜索一个结点的所有子孙结点，再搜索这个结点的兄弟结点。是否可以先搜索所有兄弟和堂兄弟结点再搜索子孙结点呢？

由于二叉树结点分属不同的层次，因此可以从上到下、从左到右依次按层访问每个结点。它的访问顺序正好和之前所述二叉树顺序存储结构中的结点在数组中的存放顺序相吻合。如图6.13中的二叉树使用宽度优先遍历访问的顺序为：ABCDEF。

这个搜索过程不再需要使用递归，但需要借助队列来完成。

（1） 将根结点压入队列之中，开始执行步骤(2)。

（2） 若队列为空，则结束遍历操作，否则取队头结点D。

（3） 若结点D的左孩子结点存在，则将其左孩子结点压入队列。

（4） 若结点D的右孩子结点存在，则将其右孩子结点压入队列，并重复步骤(2)。

【例6-2 BinaryTreeNode.cs.cs】二叉树结点类，使用例6-1同名文件。

【例6-2 LevelOrderBinaryTree.cs】包含宽度优先遍历方法的二叉树集合类

打开例6-1的【BinaryTree.cs】文件，在BinaryTree类中添加如入方法后另存为LevelOrderBinaryTree.cs文件。
1 public void LevelOrder() //宽度优先遍历
2 {
3 Queue queue = new Queue(); //声明一个队例
4 queue.Enqueue(_head); //把根结点压入队列
5 while (queue.Count > 0) //只要队列不为空
6 {
7 Node node = (Node)queue.Dequeue(); //出队
8 Console.Write(node.ToString()); //访问结点
9 if (node.Left != null) //如果结点左孩子不为空
10 { //把左孩子压入队列
11 queue.Enqueue(node.Left);
12 }
13 if (node.Right != null) //如果结点右孩子不为熔
14 { //把右孩子压入队列
15 queue.Enqueue(node.Right);
16 }
17 }
18 }

【例6-2 Demo6-2.cs】二叉树宽度优先遍历测试
1 using System;
2 class Demo6_2
3 {
4 static void Main(string[] args)
5 { //使用字符串构造二叉树
6 BinaryTree bTree = new BinaryTree("ABCDE#F");
7 bTree.LevelOrder();
8 }
9 }

运行结果：ABCDEF

❽ 线索二叉树是一种什么结构

物理结构。包括线性存储和非线性存储其中，线性存储结构有顺序、链接、索引和散列4种结构。非线性存储结构有：树形存储结构、图形存储结构。

n个结点的二叉链表中含有n+1(2n-(n-1)=n+1)个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前驱和后继结点的指针。

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

(8)索引存储二叉树扩展阅读：

二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只有在遍历中得到。

为了容易找到前驱和后继，有两种方法。一是在结点结构中增加向前和向后的指针fwd和bkd，这种方法增加了存储开销，不可取；二是利用二叉树的空链指针。

建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。为实现这一过程，设指针pre始终指向刚刚访问的结点，即若指针p指向当前结点，则pre指向它的前驱，以便设线索。