n个节点的完全二叉树顺序存储在一维数组a中,设计一个算法由此数组得到该完全二叉树的二叉链表结构.用c++写
程序代码如下：
#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、如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树。
参考资料来源：百度百科-完全二叉树
参考资料来源：百度百科-链表
假定一个结点由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);
另外,虚机团上产品团购,超级便宜
然后转成链表的话就简单了。
链表的结构
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;
}
已赞过
已踩过<
