二叉树是如何存储的

A. 二叉树怎么操作

1.构造二叉树给定一棵二叉树，要对它进行操作必须先把它存储到计算机中，二叉树的存储可以采用顺序存储结构，也可以采用链式存储结构，链式存储结构有二叉链表和三叉链表等。在这里主要讨论二叉链表存储结构。

（1）以先序递归遍历思想建立二叉树。

①建立二叉树的根结点；②先序建立二叉树的左子树；③先序建立二叉树的右子树。

（2）构造二叉树的操作算法。

输入一个二叉树的先序序列，构造这棵二叉树。为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉树的位置上填补一个特殊的字符，比如#。在算法中，需要对每个输入的字符进行判断，如果对应的字符是#，则在相应的位置上构造一棵空二叉树；否则，创建一个新结点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针参数在递归调用返回时完成的。

B. 二叉树是什么

二叉树 (binary tree) 是另一种树型结构，它的特点是每个结点至多只有二棵子 树 (即二叉树中不存在度大于 2的结点 )，并且，二叉树的子树有左右之分，其次序不能任意颠倒 . 二叉树是一种数据结构 :

Binary_tree=(D,R)

其中： D是具有相同特性的数据元素的集合 ;若 D等于空 ,则 R等于空称为空的二叉树 ;若 D等于空则 R是 D上某个二元关系 H的集合，即 R={H}，且
(1) D 中存在唯一的称为根的元素 r，它的关系 H下无前驱 ;
(2) 若 D-{r}不等于空，则 D-{r}={Dl,Dr}，且 Dl交 Dr等于空 ;
(3) 若 Dl不等于空 ,则在 Dl中存在唯一的元素 xl,〈 r,xl〉属于 H，且存在 Dl上的关系 Hl属于 H； 若 Dr不等于空 ,则在 Dr中存在唯一的元素 xr,〈 r,xr〉 >属于 H, 且存 Dr上的关 系 Hr属于 H； H={r,xl,＜ r,xr＞ ,Hl, Hr};
(4) (Dl, Hl) 是一棵合本定义的二叉树，称为根 r的左子树 ,(Dr,Hr)是一棵符合定义的二叉树，称为根的右子树。

其中，图 6.2 是各种形态的二叉树 .

(1) 为空二叉树 (2)只有一个根结点的二叉树 (3)右子树为空的二叉树 (4)左子树为空的二叉树 (5)完全二叉树

二叉树的基本操作：

(1)INITIATE(BT ） 初始化操作。置 BT为空树。

(2)ROOT(BT)\ROOT(x) 求根函数。求二叉树 BT的根结点或求结点 x所在二叉树的根结点。
若 BT是空树或 x不在任何二叉树上，则函数值为 “空 ”。

(3)PARENT(BT,x) 求双亲函数。求二叉树 BT中结点 x的双亲结点。若结点 x是二叉树 BT 的根结点
或二叉树 BT中无 x结点，则函数值为 “空 ”。

(4)LCHILD(BT,x) 和 RCHILD(BT,x) 求孩子结点函数。分别求二叉树 BT中结点 x的左孩 子和右孩子结点。
若结点 x为叶子结点或不在二叉树 BT中，则函数值为 “空 ”。

(5)LSIBLING(BT,x) 和 RSIBING(BT,x) 求兄弟函数。分别求二叉树 BT中结点 x的左兄弟和右兄弟结点。
若结点 x是根结点或不在 BT中或是其双亲的左 /右子树根 ,则函树值 为 “空 ”。

(6)CRT_BT(x,LBT,RBT) 建树操作。生成一棵以结点 x为根，二叉树 LBT和 RBT分别为左， 右子树的二叉树。

(7)INS_LCHILD(BT,y,x) 和 INS_RCHILD(BT,x) 插入子树操作。将以结点 x为根且右子树为空的二叉树
分别置为二叉树 BT中结点 y的左子树和右子树。若结点 y有左子树 /右子树，则插入后是结点 x的右子树。

(8)DEL_LCHILD(BT,x) 和 DEL-RCHILD(BT,x) 删除子树操作。分别删除二叉树 BT中以结点 x为根的左子树或右子树。
若 x无左子树或右子树，则空操作。

(9)TRAVERSE(BT) 遍历操作。按某个次序依此访问二叉树中各个结点，并使每个结点只被访问一次。

(10)CLEAR(BT) 清除结构操作。将二叉树 BT置为空树。

5.2.2 二叉树的存储结构

一 、顺序存储结构
连续的存储单元存储二叉树的数据元素。例如图 6.4(b)的完全二叉树 , 可以向量 (一维数组 ) bt(1:6)作它的存储结构，将二叉树中编号为 i的结点的数据元素存放在分量 bt[i]中 ,如图 6.6(a) 所示。但这种顺序存储结构仅适合于完全二叉树 ,而一般二叉树也按这种形式来存储 ,这将造成存 贮浪费。如和图 6.4(c)的二叉树相应的存储结构图 6.6(b)所示，图中以 “0”表示不存在此结点 .

二、 链式存储结构
由二叉树的定义得知二叉树的结点由一个数据元素和分别指向左右子树的两个分支构成 ,则表 示二叉树的链表中的结点至少包含三个域 :数据域和左右指针域 ,如图 (b)所示。有时 ,为了便于找 到结点的双亲 ,则还可在结点结构中增加一个指向其双亲受的指针域，如图 6.7(c)所示。

5.3 遍历二叉树

遍历二叉树 (traversing binary tree)的问题， 即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。 其中常见的有三种情况：分别称之为先 (根 )序遍历，中 (根 )序遍历和后 (根 )序遍历。

5.3.1 前序遍历

前序遍历运算：即先访问根结点，再前序遍历左子树，最后再前序遍历右子树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。例如：

按前序遍历此二叉树的结果为： Hello!How are you?

proc preorder(bt:bitreprtr)
if (bt>null)[
print(bt^);
preorder(bt^.lchild);
preorder(bt^.rchild);]
end;

5.3.2 中序遍历

中序遍历运算：即先中前序遍历左子树，然后再访问根结点，最后再中序遍历右子树。中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。例如：

按中序遍历此二叉树的结果为： a*b-c

proc inorder(bt:bitreprtr)
if (bt>null)[
inorder(bt^.lchild);
print(bt^);
niorder(bt^.rchild);]
end;

5.3.3 后序遍历

后序遍历运算：即先后序遍历左子树，然后再后序遍历右子树，最后访问根结点。后序遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的。例如：

按后序遍历此二叉树的结果为： Welecome to use it!

proc postorder(bt:bitreprtr)
if (bt>null)[
postorder(bt^.lchild);
postorder(bt^.rchild);]
print(bt^);
end;

五、例：
1.用顺序存储方式建立一棵有31个结点的满二叉树，并对其进行先序遍历。
2.用链表存储方式建立一棵如图三、4所示的二叉树，并对其进行先序遍历。
3.给出一组数据：R={10.18,3,8,12,2,7,3}，试编程序，先构造一棵二叉树，然后以中序遍历访问所得到的二叉树，并输出遍历结果。
4.给出八枚金币a,b,c,d,e,f,g,h，编程以称最少的次数，判定它们蹭是否有假币，如果有，请找出这枚假币，并判定这枚假币是重了还是轻了。

中山纪念中学三鑫双语学校信息学竞赛组编写 2004.7.15

C. 试分析二叉树的存储时如何实现的,分别介绍二叉树的顺序存储和链式存储 .

4.二叉树的存储结构
(1）顺序存储方式

type node=record
data:datatype
l,r:integer;
end;
var tr:array[1..n] of node;

(2)链表存储方式，如：
type btree=^node；
node=record
data:datatye;
lchild,rchild:btree;
end;

D. 二叉树的存储结构是怎样的有哪些类型的存储结构对应的c语言描述是

线性表的链式存储结构：
typedef
int
elemtype;
typedef
struct
lnode
{
elemtype
data;
struct
lnode
*next;
}lnode,*linklist;
(被封装好的每个节点，都有一个数据域data和一个指针域*next用于指向下一个节点)
二叉树的二叉链表：
typedef
int
telemtype;
typedef
struct
bitnode
{
telemtype
data;
struct
bitnode
*lchild,*rchild;
}bitnode,*bitree;
(被封装好的每个节点，都有一个数据域data和两个指针域
*lchild,*rchild分别指向左右子树)
需要什么类型的数据作为数据域可更改，或者typedef
int
elemtype;和typedef
int
telemtype;中的int，比如改为char、float等或者自定义数据类型。

E. 如何进行二叉树的存储

用二叉链表进行存储，采用先序遍历的思想来创建二叉树就行了

F. 数据结构 二叉树的顺序存储结构

此结构是将二叉树的所有结点，
按照一定的次序，存储到一片连续的存储单元中。
因此，必须将结点排成一个适当的线性序列，
使得结点在这个序列中的相应位置能反映出结点之间的逻辑关系。
这种结构特别适用于近似满二叉树。
在一棵具有n个结点的近似满二叉树中，
我们从树根起，自上层到下层，逐层从左到右给所有结点编号，就能得到一个足以反映整个二叉树结构的线性序列

G. 采用顺序存储方法和链式存储方法分别画出图6.1所示二叉树的存储结构。【在线等】

线性是线性，顺序是顺序，线性是逻辑结构，顺序是储存结构，两者不是一个概念。线性是指一个节点只有一个子节点，而树，或二叉树一个节点后有多个子节点，且子节点不能相互联系。

顺序存储可能会浪费空间(在非完全二叉树的时候)，但是读取某个指定的节点的时候效率比较高。

链式存储相对二叉树比较大的时候浪费空间较少，但是读取某个指定节点的时候效率偏低。

二叉树的顺序存储，寻找后代节点和祖先节点都非常方便，但对于普通的二叉树，顺序存储浪费大量的存储空间，同样也不利于节点的插入和删除。因此顺序存储一般用于存储完全二叉树。

链式存储相对顺序存储节省存储空间，插入删除节点时只需修改指针，但回寻找指定节点时很不方便。不过普通答的二叉树一般是用链式存储结构。

(7)二叉树是如何存储的扩展阅读：

(1)完全二叉树——若设二叉树的高度为h，除第h层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉树是树的一种特殊情形，是一种更简单而且应用更加广泛的树。

H. 什么是二叉树的顺序存储

二叉树的顺序存储是将二叉树的所有结点，按照一定的次序，存储到一片连续的存储单元中

二叉树的顺序存储必须将结点排成一个适当的线性序列，使得结点在这个序列中的相应位置能反映出结点之间的逻辑关系。这种结构特别适用于近似满二叉树。

在一棵具有n个结点的近似满二叉树中，当从树根起，自上层到下层，逐层从左到右给所有结点编号时，就能得到一个足以反映整个二叉树结构的线性序列。其中每个结点的编号就作为结点。

(8)二叉树是如何存储的扩展阅读：

二叉树的性质：

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。

参考资料来源：网络-二叉树

I. 如何存储一颗二叉树

1、顺序存储结构，用一组地址连续的存储单元由上而下由左至右的存储完全二叉树的节点元素，其他二叉树则与完全二叉树上的结点进行对照，存储在一维数组的相应分量中
2、链式存储结构，如二叉链表，三叉链表
3、线索二叉树

J. 二叉树顺序存储

顺序存储的话，就是存储在数组中，数组的下标就是二叉树的结点位置（层次结构），比如结点A，在数组中就是位置0，B就是1，C就是2....，以此类推，所以第i个结点的在数组中的位置就是i（i从0开始），i的两个孩子结点在数组中的位置是2i+1和2i+2