C 二叉树顺序结构存储？二叉树的顺序存储结构数据A

一、顺序存储是二叉树常用的存储结构吗

二叉树的存储结构

二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可采用顺序存储结构和链式存储结构。

1．顺序存储结构

二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法从树根起，自上层至下层，每层自左至右地给所有结点编号,缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点存储空间。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。图5-5(a)是一棵完全二叉树，图5-5（b）给出的图5-5(a)所示的完全二叉树的顺序存储结构。

(a)一棵完全二叉树(b)顺序存储结构

图5-5完全二叉树的顺序存储示意图

对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。如图5-6给出了一棵一般二叉树改造后的完全二叉树形态和其顺序存储状态示意图。显然，这种存储对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时，会造成空间的大量浪费，不宜用顺序存储结构。最坏的情况是右单支树，如图5-7所示，一棵深度为k的右单支树，只有k个结点，却需分配2k－1个存储单元。

(a)一棵二叉树(b)改造后的完全二叉树

(c)改造后完全二叉树顺序存储状态

图5-6一般二叉树及其顺序存储示意图

(a)一棵右单支二叉树(b)改造后的右单支树对应的完全二叉树

(c)单支树改造后完全二叉树的顺序存储状态

图5-7右单支二叉树及其顺序存储示意图

结构5-1二叉树的顺序存储

#define Maxsize 100//假设一维数组最多存放100个元素

typedef char Datatype;//假设二叉树元素的数据类型为字符

typedef struct

{ Datatype bt[Maxsize];

int btnum;

}Btseq;

2．链式存储结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。

通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。其结点结构为：

其中，data域存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。利用这样的结点结构表示的二叉树的链式存储结构被称为二叉链表，如图5-8所示。

(a)一棵二叉树(b)二叉链表存储结构

图5-8二叉树的二叉链表表示示意图

为了方便访问某结点的双亲，还可以给链表结点增加一个双亲字段parent,用来指向其双亲结点。每个结点由四个域组成，其结点结构为：

这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。利用这样的结点结构表示的二叉树的链式存储结构被称为三叉链表。

图5-9给出了图5-8(a)所示的一棵二叉树的三叉链表表示。

图5-9二叉树的三叉链表表示示意图

尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序存储结构还节省空间。因此，二叉链表是最常用的二叉树存储方式。

结构5-2二叉树的链式存储

#define datatype char//定义二叉树元素的数据类型为字符

typedef struct node//定义结点由数据域，左右指针组成

{ Datatype data;

struct node*lchild,*rchild;

}Bitree;

二、任何二叉树都可以采用顺序存储结构

下面是使用Java编写的BTree类中的postOrder方法，实现二叉树的后序遍历：

public class BTree{

private Node root;

public BTree(){

root= null;

}

//后序遍历

public void postOrder(){

postOrder(root);

}

private void postOrder(Node node){

if(node== null){

return;

}

//后序遍历左子树

postOrder(node.lchild);

//后序遍历右子树

postOrder(node.rchild);

//访问当前节点的数据

visit(node.data);

}

//访问操作

private void visit(Object data){

System.out.print(data+"");

}

public static void main(String[] args){

//创建一个二叉树对象

BTree tree= new BTree();

//构建二叉树

Node root= new Node();

root.data="A";

root.lchild= new Node();

root.lchild.data="B";

root.rchild= new Node();

root.rchild.data="C";

root.lchild.lchild= new Node();

root.lchild.lchild.data="D";

root.lchild.rchild= new Node();

root.lchild.rchild.data="E";

root.rchild.lchild= new Node();

root.rchild.lchild.data="F";

root.rchild.rchild= new Node();

root.rchild.rchild.data="G";

tree.root= root;

//后序遍历二叉树

tree.postOrder();

}

}

在这个例子中，我们创建了一个二叉树对象，并使用节点类Node构建了一个具有7个节点的二叉树。然后通过调用postOrder方法进行后序遍历，访问操作在visit方法中进行。最终输出结果为后序遍历的节点数据：D E B F G C A。

你可以根据需要修改节点类和访问操作来适应你的实际情况。

三、二叉树的顺序存储结构数据A***B***C***D***E

二叉树结构链式图：

A

/

\

B

C

/

\

D

E

前序遍历：（根，左，右）：

A

->

B-> D-> E-> C中序遍历：（左，根，右）：

D-> B-> E-> A-> C后序遍历：（左，右，根）：

D-> E-> B-> C-> A

前序

中序

后序

遍历，主要是以根节点做为参考点，进行遍历。（根，左，右）

遍历顺序中

‘根’

在第一个，所以叫前序遍历。（左，根，右）遍历顺序中

‘根’

在第二个，所以叫中序遍历。（左，右，根）遍历顺序中

‘根’

在第三个，所以叫后序遍历。

四、二叉树是非线性数据结构,所以

二叉树是非线性数据结构，所以（C、它能采用顺序存储结构和链式存储结构存储）。

一般而言，完全二叉树（包括满二叉树）使用顺序存储，普通二叉树一般用二叉链表或者三叉链表存储。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

扩展资料：

若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：

当i=1时，该节点为根，它无双亲节点。

当i>1时，该节点的双亲节点的编号为i/2。

若2i≤n，则有编号为2i的左节点，否则没有左节点。

若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点。