n个节点的完全二叉树顺序存储在一维数组a中,设计一个算法由此数组得到该完全二叉树的二叉链表结构.用c++写
再删一个最小的（也就是原来第二小的）每次都是这么：(我理解为h就是数组i
BiTree * BuildByFirst(int A[], int cur, int n)
{
if (cur >= n)
return NULL;
BiTree *tmp = new BiTree()
tmp->data = A[cur];
tmp->left = BuildByFirst(A, 2 * cur + 1, n);
tmp->right = BuildByFirst(A, 2 * cur + 2, n);
return tmp;
}
void Conversion(int A[]，int n, BiTree &T)
{
BiTree *tmp = BuildByFirst(A, 0, n);
T = *tmp;
delete tmp;
}
程序代码如下：
#include<iostream>
#include<math.h>
#define MAX 100
using namespace std;
typedef char ElemType;
typedef struct node
{
ElemType data; //数据域
struct node *left; //左孩子指针
struct node *right; //右孩子指针
} BTNode;
//初始化二叉链表结点数组
void InitNodes(BTNode *nodes[], ElemType values[], int size)
{
int i;
for(i=0; i<size; i++)
{
nodes[i] = new BTNode();
nodes[i]->data = values[i];
}
}
//中序遍历二叉树
void MidOrderTravel(BTNode *root)
{
if(root != NULL)
{
MidOrderTravel(root->left);
cout<<root->data<<" ";
MidOrderTravel(root->right);
}
}
//根据二叉树的顺序存储结构，生成二叉树的二叉链表结构
BTNode *CreateBinaryTree(BTNode *nodes[], int size)
{
BTNode *root;
int i;
if(size < 1)
return NULL;
for(i=0; i<size; i++)
{
if(2*i+1 >= size)
nodes[i]->left = NULL;
else if(nodes[2*i+1]->data == ' ')
nodes[i]->left = NULL;
else
nodes[i]->left = nodes[2*i+1];
if(2*i+2 >= size)
nodes[i]->right = NULL;
else if(nodes[2*i+2]->data == ' ')
nodes[i]->right = NULL;
else
nodes[i]->right = nodes[2*i+2];
}
root = nodes[0];
return root;
}
void main()
{
ElemType values[] = {'A','B','C','D','E','F','G'};
//ElemType values[] = {'A','B','C',' ','D','E'};
BTNode *root;
BTNode *nodes[MAX];
int size = 7; //二叉树的顺序结构的大小
InitNodes(nodes, values, size);
root = CreateBinaryTree(nodes, size);
cout<<"中序遍历序列：";
MidOrderTravel(root);
cout<<end;
}
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树，并且最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树成为完全二叉树。
扩展资料
判断一棵树是否是完全二叉树的思路：
1、如果树为空，则直接返回错
2、如果树不为空：层序遍历二叉树；
3、如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；
4、如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；
5、如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树。
参考资料来源：百度百科-完全二叉树
参考资料来源：百度百科-链表
思路很简单，根放在0位置，以后假定当前位置是i，那么左子结点在2i+1，右子结点在2i+2。比如根的左子结点在1，右子结点在2。结点1的左子结点在3，右子结点在4。定义一种空值表示没有子结点，比如empty。
假定一个结点由3个成员组成：value, left, right
数组假定是全局的，如果不是可以作为参数传送。
递归实现比较简单：
void btree2array(node, index)
{
if(node == NULL)
array[index] = empty;
array[index] = node->value;
btree2array(node->left, index * 2 + 1);
btree2array(node->right, index * 2 + 2);
}
开始调用的时候就一句话：
btree2array(root, 0);
另外,虚机团上产品团购,超级便宜
算法： 设数组 a[N]; a[1] 为根结点，则结点i的left_node为a[i*2],right_node为a[i*2+1];
然后转成链表的话就简单了。
链表的结构
struct Node{
int value;
Node *left, *right;
};
定义一个根Node *root = new Node; root->value=a[1];
剩下的自己写吧。
一般顺序结构存储的二叉树节点都会记录有下一个节点的位置啊，转化过来呗。。。。呵呵
参考源代码：
该程序的特点是不仅适合完全二叉树，还适合所有二叉树的顺序结构转换成二叉链表结构，但需要按完全二叉树的编号顺序进行二叉树的顺序存储。
#include<iostream>
#include<math.h>
#define MAX 100
using namespace std;
typedef char ElemType;
//二叉链表结点结构
typedef struct node
{
ElemType data; //数据域
struct node *left; //左孩子指针
struct node *right; //右孩子指针
} BTNode;
//初始化二叉链表结点数组
void InitNodes(BTNode *nodes[], ElemType values[], int size)
{
int i;
for(i=0; i<size; i++)
{
nodes[i] = new BTNode();
nodes[i]->data = values[i];
}
}
//中序遍历二叉树
void MidOrderTravel(BTNode *root)
{
if(root != NULL)
{
MidOrderTravel(root->left);
cout<<root->data<<" ";
MidOrderTravel(root->right);
}
}
//根据二叉树的顺序存储结构，生成二叉树的二叉链表结构
BTNode *CreateBinaryTree(BTNode *nodes[], int size)
{
BTNode *root;
int i;
if(size < 1)
return NULL;
for(i=0; i<size; i++)
{
if(2*i+1 >= size)
nodes[i]->left = NULL;
else if(nodes[2*i+1]->data == ' ')
nodes[i]->left = NULL;
else
nodes[i]->left = nodes[2*i+1];
if(2*i+2 >= size)
nodes[i]->right = NULL;
else if(nodes[2*i+2]->data == ' ')
nodes[i]->right = NULL;
else
nodes[i]->right = nodes[2*i+2];
}
root = nodes[0];
return root;
}
void main()
{
ElemType values[] = {'A','B','C','D','E','F','G'};
//ElemType values[] = {'A','B','C',' ','D','E'};
BTNode *root;
BTNode *nodes[MAX];
int size = 7; //二叉树的顺序结构的大小
InitNodes(nodes, values, size);
root = CreateBinaryTree(nodes, size);
cout<<"中序遍历序列：";
MidOrderTravel(root);
cout<<endl;
}
n个节点的完全二叉树顺序存储在一维数组a中,设计一个算法由此数组得到该...
答：一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树，并且最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树成为完全二叉树。
求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点...
答：根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是en/2?，这是最后一个分支结点，在它之后是第一个终端（叶子）结点，故序号最小的，叶子结点的下标是en/2u+1。最坏的情况就是这个二叉树是单支数。 比如有k 层，节点数字也是 k 。需要 2^K - 1 长度dao的数组来存放，而实际...
完全二叉树的存储结构通常采用顺序存储结构()
答：正确。一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。如果对满二叉树的结点进行编号, 约定编号从根结点起, 自上而下, 自左而右。则深度为k...
n个结点的完全二叉树顺序存储,叶结点和非叶结点的个数、范围?
答：n个节点的完全二叉树，则根据公式2^N-1=n 算出N， 即层数。叶节点数：2^(N-1),非叶子节点数：2^(N-1)-1 范围就不用说了吧，非叶子：1---2^(N-1)-1 叶子：2^(N-1)---2^N-1 存储，可以用链表，也可以用数组。链表，每个节点一个左子节点，一个右子节点。数组，就按照...
完全二叉树为什么最适合顺序存储结构?
答：对于普通的不是满二叉树的，那些空出来的节点对应的数组元素留空即可，因此顺序存储会造成一定的空间浪费。如果是完全二叉树，就不会有空间浪费的情况；若是只有右子树，那么会造成相当大的浪费。二叉树算法思路：1、如果树为空，则直接返回错。2、如果树不为空：层序遍历二叉树。3、如果一个结点左右...
完全二叉树的顺序存储的方法步骤
答：完全二叉树的顺序存储，仅需从根节点开始，按照层次依次将树中节点存储到数组即可，在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。一棵深度为k，且有2^k-1个结点的二叉树...
为什么说二叉树只能顺序存储?
答：所以，这样即使是将一棵树顺序存储到了一个一维数组中，结点 i 的左孩子就是2i，右孩子就是2i+1这套公式照样能够使用。假设现在一棵非完全二叉树，拿一棵普通的二叉树举例，一棵普通二叉树有5种形态（空树、只有根结点、只有左子树、只有右子树、左右子树都有），从形态上来看是一棵“残缺不全...
什么是二叉树的顺序存储?
答：二叉树的顺序存储是将二叉树的所有结点，按照一定的次序，存储到一片连续的存储单元中 二叉树的顺序存储必须将结点排成一个适当的线性序列，使得结点在这个序列中的相应位置能反映出结点之间的逻辑关系。这种结构特别适用于近似满二叉树。在一棵具有n个结点的近似满二叉树中，当从树根起，自上层到下层，...
二叉树 两种存储结构的优缺点
答：一、顺序存储 优点：读取某个指定的节点的时候效率比较高O(0)缺点：会浪费空间(在非完全二叉树的时候)二、链式存储 优点：读取某个指定节点的时候效率偏低O(nlogn)缺点：相对二叉树比较大的时候浪费空间较少 二叉树的顺序存储，寻找后代节点和祖先节点都非常方便，但对于普通的二叉树，顺序存储浪费大量...
n个结点的线索二叉树中线索的数目为多少?为什么?
答：在一个具有n个结点的线索二叉树中有n+1个指针是用来作为线索处理的。因为n个结点的二叉树中有2n个指针，而这些个结点（除根结点）都有一个指针指向它，这有就n-1个结点被实用，空的指针有n+1个，可用作线索。一棵深度为k，且有2^（k-1）个节点的二叉树，称为满二叉树。这种树的特点是每一...
