设计一个算法将一棵二叉链表存储的二叉树按顺序存储到数组中
来源:百度知道 编辑:UC知道 时间:2024/05/26 22:24:22
思路很简单,根放在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);
根放在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);