㈠ 顺序存储是二叉树常用的存储结构吗
二叉树的存储结构
二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可采用顺序存储结构和链式存储结构。
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;
㈡ 树的存储结构转换
//声明树中的类以及结点结构，文件名为tree.h
#ifndef TREE_H
#define TREE_H
template <class T>//树中结点采用孩子兄弟表示法
struct TNode
{
T data;
TNode<T> *firstchild, *rightsib;
};
template <class T>
class Tree
{
public:
Tree( ); //构造函数，初始化一棵树，其前序序列由键盘输入
~Tree(void); //析构函数，释放树中各结点的存储空间
TNode<T>* Getroot( ); //获得指向根结点的指针
void PreOrder(TNode<T> *root); //前序遍历树
void PostOrder(TNode<T> *root); //后序遍历树
void LeverOrder(TNode<T> *root); //层序遍历树
private:
TNode<T> *root; //指向根结点的头指针
void Release(TNode<T> *root); //析构函数调用
};
#endif
//定义类中的成员函数，文件名为tree.cpp
#include<iostream>
#include<string>
#include"tree.h"
using namespace std;
/*
*前置条件：树不存在
*输 入：无
*功 能：构造一棵树
*输 出：无
*后置条件：产生一棵树
*/
template<class T>
Tree<T>::Tree( )
{
const int MaxSize = 100;
int end = 0;
int front = 0;
int rear = 0; //采用顺序队列，并假定不会发生上溢
int j = 0;
TNode<T>* queue[MaxSize]; //声明一个队列
TNode<T>* tempNode; //声明指向结点类型的指针
TNode<T>* brotherNode; //工作指针
TNode<T>* q;
T ch;
cout<<"请输入创建一棵树的根结点数据"<<endl;
cin>>ch;
root = new TNode<T>;
root->data = ch;
root->firstchild = NULL;
root->rightsib = NULL;
queue[rear++] = root;
while (!end) //若继续创建树
{
T ch1,ch2;
cout<<"请输入创建一棵树的父结点数据和孩子结点数据"<<endl;
cin>>ch1>>ch2;
TNode<T>* p = new TNode<T>; //生成一个结点
p->data = ch2;
p->firstchild = NULL;
p->rightsib = NULL;
queue[rear++] = p;
tempNode = queue[front];//头结点出队，同时对头元素的标识符后移
while(ch1 != tempNode->data)
tempNode = queue[front++];
if(tempNode->firstchild == NULL) tempNode->firstchild = p;
else{
brotherNode = tempNode->firstchild; //工作指针指向结点的第一个孩子
while (brotherNode != NULL) //若第一个孩子有兄弟结点
{
q = brotherNode;
brotherNode = brotherNode->rightsib;//工作指针指向第一个孩子的右兄弟
}
q->rightsib = p;
}
cout<<"创建结束? 如果结束请按1否则请按0 "<<endl;
cin>>end;
}
}
/*
*前置条件：树已存在
*输 入：无
*功 能：释放树中各结点的存储空间
*输 出：无
*后置条件：树不存在
*/
template<class T>
Tree<T>::~Tree(void)
{
Release(root);
}
/*
*前置条件：树已存在
*输 入：无
*功 能：获取指向树根结点的指针
*输 出：指向树根结点的指针
*后置条件：树不变
*/
template<class T>
TNode<T>* Tree<T>::Getroot( )
{
return root;
}
/*
*前置条件：树已存在
*输 入：无
*功 能：前序遍历树
*输 出：树中结点的一个线性排列
*后置条件：树不变
*/
template<class T>
void Tree<T>::PreOrder(TNode<T> *root) //前序遍历树
{
if (root == NULL) return; //递归调用的结束条件
else{
cout<<root->data; //打印根节点
PreOrder(root->firstchild); //前序递归遍历root的第一个孩子
PreOrder(root->rightsib); //前序递归遍历root的右兄弟
}
}
/*
*前置条件：树已存在
*输 入：无
*功 能：后序遍历树
*输 出：树中结点的一个线性排列
*后置条件：树不变
*/
template<class T>
void Tree<T>::PostOrder(TNode<T> *root)
{
if (root == NULL) return; //递归调用的结束条件
else{
PostOrder(root->firstchild); //后序递归遍历root的第一个孩子
cout<<root->data; //打印出root结点
PostOrder(root->rightsib); //后序递归遍历root的右兄弟
}
}
/*
*前置条件：树已存在
*输 入：无
*功 能：层序遍历树
*输 出：树中结点的一个线性排列
*后置条件：树不变
*/
template<class T>
void Tree<T>::LeverOrder(TNode<T> *root)
{
const int MAX_QUEUE_SIZE = 100;
int front = 0;
int rear = 0; //采用顺序队列，并假定不会发生上溢
TNode<T>* queue[MAX_QUEUE_SIZE]; //声明一个队列
TNode<T>* tempNode; //声明指向结点类型的指针
TNode<T>* brotherNode; //工作指针
if (root == NULL) return;//循环结束条件
queue[rear++] = root; //否则结点入队
while (front != rear) //若队列中有结点
{
tempNode = queue[front++];//头结点出队，同时对头元素的标识符后移
cout<<tempNode->data; //打印出头结点
brotherNode = tempNode->firstchild; //工作指针指向结点的第一个孩子
while (brotherNode != NULL) //若第一个孩子有兄弟结点
{
queue[rear++] = brotherNode; //第一个孩子结点入队
brotherNode = brotherNode->rightsib;//工作指针指向第一个孩子的右兄弟
}
}
}
/*
*前置条件：树已经存在
*输 入：无
*功 能：释放树的存储空间，析构函数调用
*输 出：无
*后置条件：树不存在
*/
template <class T>
void Tree<T>::Release(TNode<T>* root)
{
if (root != NULL){
Release (root->firstchild); //释放第一个孩子
Release (root->rightsib); //释放右兄弟
delete root;
}
}
//有关树的实现的主函数，文件名为treemain.cpp
#include <iostream>
#include <string>
#include"tree.cpp"
using namespace std;
void main()
{
Tree<string> t; //创建一棵树
TNode<string>* p = t.Getroot( ); //获取指向根结点的指针
cout<<"------前序遍历------ "<<endl;
t.PreOrder(p);
cout<<endl;
cout<<"------后序遍历------ "<<endl;
t.PostOrder(p);
cout<<endl;
cout<<"------层序遍历------ "<<endl;
t.LeverOrder(p);
cout<<endl;
}
㈢ 树的存储结构
常用的有：1、双亲表示，2、孩子链表表示，3、双亲孩子链表表示，4、孩子兄弟链表表示
㈣ 关于树的孩子兄弟存储结构
就是孩子兄弟链表中该结点的孩子构成的森林，自然是从firstchild开始
自己的高度肯定是孩子的最大高度加1
然后和兄弟的高度比较，留下最大值
㈤ 二叉树的存储结构是怎样的有哪些类型的存储结构对应的c语言描述是
楼上回答的是树的存储，不是二叉树的存储，主要如下：
1、顺序存储：适用于完全二叉树，如果根从1开始编号，则第i结点的左孩子编号为2i，右孩子为2i+1，双亲编号为(i/2）下取整，空间紧密
2、二叉链表：适用于普通二叉树，每个结点除了数据外，还有分别指向左右孩子结点的指针，存储n个结点有n+1个空指针域，存储密度小于顺序存储，但是适用范围广，缺陷是正常遍历只能从双亲向孩子，退回来一般需要借助栈（或者用递归，其实也是栈）
3、三叉链表：同样适用于普通二叉树，结点除了数据外，还有左右孩子与双亲的指针，存储密度低于二叉链表，但是可以非常方便地在二叉树中遍历，不需要其他辅助工具
㈥ 树的存储表示是什么
树的存储结构根据应用的不同而不同，有的从双亲的角度考虑，引出了双亲表示法，有的从孩子的角度考虑，给出孩子表示法，还有的从孩子和兄弟的角度来讨论。这些都是人们在大量的应用中所使用的不同形式的存储结构，这里介绍常用的双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法。
1.双亲表示法由树的定义可知，树中每个结点都有且仅有一个双亲结点，根据这一特性，可以用一组连续的一维数组来存储树中的各个结点（一般按层次存储），数组中的一个元素对应树中的一个结点，其中包括结点的数据信息以及该结点的双亲在数组中的下标。树的这种存储方法称为双亲表示法，双亲表示法的结点结构如图1所示，其中，data表示数据域，存储树中结点的数据信息，parent表示指针域，存储该结点的双亲在数组中的下标。
1.双亲表示法的存储结构2）双亲表示法示例图1所示的树的双亲表示如图1所示，这是一棵树及其双亲表示法的存储结构。根结点A无双亲，所以parent的值为－1，G、H和I的parent值为4，表示它们的双亲是下标为4的结点E。这种存储结构利用任一结点的双亲是唯一的性质，可以方便地直接找到任一结点的双亲结点，但求结点的孩子结点时需要扫描整个数组。
图1树的双亲表示法示例
㈦ 树的存储方法主要有哪些
三叉链表不就是存储结构，其具体实现既可以用指针实现，也可以用数组实现 至于遍历方法可以任意地在二叉树中上下
㈧ 完全二叉树的存储结构通常采用顺序存储结构()
正确。
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
如果对满二叉树的结点进行编号, 约定编号从根结点起, 自上而下, 自左而右。则深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。
(8)树的存储结构扩展阅读：
判断一棵树是否是完全二叉树的思路
1、如果树为空，则直接返回错。
2、如果树不为空：层序遍历二叉树。
如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列。
如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树。
如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树。
㈨ 数据结构，树的常用存储方式
存入文本文件，每行：孩子节点-父节点。
这样也方便用Hadoop进行处理。
㈩ 树的存储结构，孩子链存储表示法没看懂求解释
对于一般的家谱树(一般的多叉树)来说，我们可以很清楚的看出层次关系，树的层数表示代数（一共多少代人），树的最后一层表示最后一代人，由于多叉链表法表示的不方便，因此被迫无奈采用孩子兄弟表示法(二叉链表法).