n个节点的完全二叉树顺序存储在一维数组a中,设计一个算法由此数组得到该完全二叉树的二叉链表结构.用c++写

n个节点的完全二叉树顺序存储在一维数组a中,设计一个算法由此数组得到该完全二叉树的二叉链表结构.用c++写

思路很简单，根放在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];
剩下的自己写吧。

一般顺序结构存储的二叉树节点都会记录有下一个节点的位置啊，转化过来呗。。。。呵呵

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息