顺序存储二叉树 |
您所在的位置：网站首页 › 二维数组示意图 › 顺序存储二叉树 |
顺序存储二叉树
|
顺序存储二叉树的概念说明 二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。 因此，必须把二叉树的所有结点安排成为一个恰当的序列，反映出节点中的逻辑关系 用编号的方法从树根起，自上层至下层，每层自左至右地给所有结点编号,缺点是有可能对存储空间造成极大的费 在最坏的情况下，一个深度为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) 改造后的右单支树对应的完全二叉树
以上是对顺序存储结构的分析：这种二叉树隐含了一个重要的信息 也就是完全二叉树的性质 左孩子的数组下标是父节点的两倍； 右海子的数组下标是父节点的两倍加一； 如果已知父节点编号和左右海子编号，完全可以建立顺序存储的二叉树； OJ实例：这道题完全是针对顺序存储的二叉树进行出题的 赋上我AC的代码： #include using namespace std; #include #define N 100000 int order[N]; //存储二叉树 int map[N]; //一个映射 int times = 1; int n; int postOrder(int head) { if (order[head * 2] != -1) postOrder(head * 2); if (order[head * 2 + 1] != -1) postOrder(head * 2 + 1); if (times == n) printf("%d\n", order[head]); else printf("%d ", order[head]); times++; return 0; } int main() { //freopen("E:/in.txt", "r", stdin); scanf("%d", &n); int num, left, right, temp; for (int i = 0; i < n; i++) { scanf("%d%d%d", &num, &left, &right); if (num == 1) { order[1] = 1; map[1] = 1; } temp = map[num]; if (left != -1) { order[2 * temp] = left; map[left] = 2 * temp; } else order[2 * temp] = -1; if (right != -1) { order[2 * temp + 1] = right; map[right] = 2 * temp + 1; } else order[2 * temp + 1] = -1; } for (int i = 1; i < n; i++) printf("%d ", map[i]); printf("%d\n", map[n]); postOrder(1); // fclose(stdin); return 0; }
|
【本文地址】
今日新闻 |
推荐新闻 |