二叉树适合存什么数据

❶ 什么样的二叉树适合用数组存储

完全二叉树适合用数组存储，它在使用时可以没有存储单元的浪费。

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

楼上回答的是树的存储，不是二叉树的存储，主要如下：
1、顺序存储：适用于完全二叉树，如果根从1开始编号，则第i结点的左孩子编号为2i，右孩子为2i+1，双亲编号为(i/2）下取整，空间紧密
2、二叉链表：适用于普通二叉树，每个结点除了数据外，还有分别指向左右孩子结点的指针，存储n个结点有n+1个空指针域，存储密度小于顺序存储，但是适用范围广，缺陷是正常遍历只能从双亲向孩子，退回来一般需要借助栈（或者用递归，其实也是栈）
3、三叉链表：同样适用于普通二叉树，结点除了数据外，还有左右孩子与双亲的指针，存储密度低于二叉链表，但是可以非常方便地在二叉树中遍历，不需要其他辅助工具

❸ 二叉树是什么

二叉树 (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

❹ 二叉树 两种存储结构的优缺点

一、顺序存储

优点：读取某个指定的节点的时候效率比较高O(0)

缺点：会浪费空间(在非完全二叉树的时候)

二、链式存储

优点：读取某个指定节点的时候效率偏低O(nlogn)

缺点：相对二叉树比较大的时候浪费空间较少

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

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

(4)二叉树适合存什么数据扩展阅读：

性质1：二叉树的第i层上至多有2i-1（i≥1）个节点

性质2：深度为h的二叉树中至多含有2h-1个节点

性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1

性质4：具有n个节点的完全二叉树深为log2x+1（其中x表示不大于n的最大整数）

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

二叉树的存储结构
二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可采用顺序存储结构和链式存储结构。
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;

❻ 二叉树是用来干什么的在软件工程方面有什么用途，请帮小弟举几个实例。

二叉树常被用于实现二叉查找树和二叉堆。

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。

根据不同的用途可分为：

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

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

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

(6)二叉树适合存什么数据扩展阅读

深度为h的二叉树最多有个结点(h>=1)，最少有h个结点。对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1。

有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系为若I为结点编号则 如果I>1，则其父结点的编号为I/2。如果2*I<=N，则其左孩子（即左子树的根结点）的编号为2*I。若2*I>N，则无左孩子。如果2*I+1<=N，则其右孩子的结点编号为2*I+1。

❼ 二叉树的存储方式有哪些

二叉树的存储方式通常有动态存储。用结构体表示二叉树的一个节点。用数据域保持保存节点的值，用链接语保存两个孩子的指针。还有就是采用满二叉树的顺序存储方式。

❽ 完全二叉树用什么数据结构实现最合适,为什么

一般的二叉树用带有两个指向自身结构类型变量的指针的多个结构体组成最合适。
如果该二叉树不会变化，可以用数组实现，每个数组元素表示一个节点，因为是完全的，所以长度一定是2的n次方-1，n为树的深度，也可以很方便地算出某个元素与树根节点、父节点等的关系，因此不用指针反而可以减少存储开销及查询效率。

❾ 有关数据结构二叉树存储结构类型的，求助大神解答

图中的第一行是定义了一个叫做DataType的类型就是char类型。 接下来定义了一个叫做BinTNode的二叉树结点类型，它包含一个字符型的数据，还有两个指向左右子树的指针。 第三个定义数据类型是定义了一个指向二叉树节点的指针叫做BinTree。 接下来的一个无返回值的函数f31( ),是一个先正向打印从根结点到最左下角结点的路径，再反向打印一遍此路径。 若二叉树如图中所示，则调用f31(T)的输出结果为： ABDDBA

❿ 数据结构树和二叉树有哪些实际应用

一个单位有10个部门，每个部门都有一部电话，但是整个单位只有一根外线，当有电话打过来的时候，由转接员转到内线电话，已知各部门使用外线电话的频率为（次/天）

5 20 10 12 8 4 3 5 6 9

问应该如何设计个内线电话号码，使得接线员拨号次数尽可能少？

这是哈夫曼树的应用。

一种数据结构，用于保存和处理树状的数据，如家谱。

应用极为广泛，因为根据数据结构的理论，任何复杂的树够可以转换为二叉中并进行处理。

二叉树再排序、查找、大规模数据索引方面有很多很多应用。

二叉树排序是简单算法排序中速度最快的。

树的一个大类是自平衡二叉搜索树 (self-balanced BST), 变种特别多:RB 树是每个节点是红色或者黑色, 颜色隔代遗传AVL 树是每个节点包含平衡因子, 等于左高-右高Splay 树是每个节点带个父节点的指针Treap 是每个节点都带个随机的 priority number, parent priority >= child priority。

自平衡二叉搜索树在面试中经常出现, 但做网页的互联网码农却很少用得上，如果是当 Map 用, 往往还不如直接上哈希表. 如果是当排序用, 不如直接用排序算法... 不过也有有用的时候, 例如查找一个数字的上下界。

树的另一个大类是 Trie, 特点是能保证字典序, 存储词典的空间压缩率高, 能做前缀搜索. 在正则匹配, 数据压缩, 构建索引都可能用到. Trie 也有不少变种:Double Array - trie 的一个经典实现。

每个节点可以存一段字符串而不限于一个字符Judy Array - 基于 256-ary radix tree, 用了 20 种压缩方式, 极其复杂...Burst Trie - 如果一个子树足够小, 就用 binary 堆的方式存储,。

不过压缩效果一般HAT Trie - 压缩率高而且不容易出现 CPU cache miss, 查速接近哈希表而耗内存少得多. 节点可以是以下三种之一: Array Hash, 序列化的 Bucket, 传统 Trie nodeMARISA Trie - 压缩率最高, 支持 mmap 载入, 也是用了很多压缩技巧的复杂实现, 就是构建比较花时间, 也不能动态更新。