树和二叉树->存储结构

文字描述

1 二叉树的顺序存储

用一组地址连续的存储单元自上而下，自左至右存储完全二叉树上的结点元素。

这种顺序存储只适用于完全二叉树。因为，在最坏情况下，一个深度为k且只有k个结点的单支树却需要长度为2^k-1的一维数组。

2 二叉树的链式存储(二叉链表)：

链表中的结点至少包含3个域：数据域，左指针域，右指针域；

3 二叉树的链式存储(三叉链表)：

链表中的结点至少包含4个域：数据域，左指针域，右指针域，和指向其双亲结点的指针域。

4 树的双亲表示法

以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。

5 树的孩子表示法

把每个结点的孩子结点排列起来，看成一个线性表，且以单链表存储结构，则n个结点有n个孩子链表(叶子的孩子链表为空表)。而n个头指针又组成一个线性表，为了便于查找，也采用顺序存储结构。

6 树的孩子兄弟表示法，又称二叉树表示法，或二叉链表表示法。

即以二叉链表做树的存储结构。连报表中的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild和nextsibling。

示意图

代码实现

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 #define DEBUG
  5 /*树中结点的最大个数*/
  6 #define MAX_TREE_SIZE 100
  7 
  8 typedef char KeyType;
  9 typedef int InfoType;
 10 
 11 /*树中的结点类型*/
 12 typedef struct{
 13     KeyType key;
 14     InfoType otherinfo;
 15 }TElemType;
 16 
 17 ///////////////////////////////////////////
 18 //            二叉树的存储结构            //
 19 //////////////////////////////////////////
 20 
 21 /*
 22  * 二叉树的顺序存储
 23  *
 24  *用一组地址连续的存储单元自上而下，自左至右存储完全二叉树上的结点元素。
 25  *0 号单元存储根结点
 26  */
 27 typedef TElemType SqBiTree[MAX_TREE_SIZE];
 28 
 29 
 30 /*
 31  * 二叉树的链式存储(二叉链表)
 32  *
 33  * 链表中的结点包含三个数据：数据域data，左指针域lchild，右指针域rchild
 34  */
 35 typedef struct BiTNode2{
 36     TElemType data;
 37     struct BiTNode2 *lchild, *rchild;
 38 }BiTNode2, *BiTree2;
 39 
 40 /*
 41  * 二叉树的链式存储(三叉链表)
 42  *
 43  * 链表中的结点包含四个数据：数据域data，左指针域lchild，右指针域rchild，指向其双亲结点的指针域parent
 44  */
 45 typedef struct BiTNode3{
 46     TElemType data;
 47     struct BiTNode3 *lchild, *rchild, *parent;
 48 }BiTNode3, *BiTree3;
 49 
 50 
 51 ////////////////////////////////////////
 52 //          树的存储结构             //
 53 ///////////////////////////////////////
 54 
 55 /*
 56  * 树的双亲表示法
 57  *
 58  * 以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。
 59  */
 60 //结点结构
 61 typedef struct PTNode{
 62     //结点的数据域
 63     TElemType data;
 64     //结点的双亲位置域
 65     int parent;
 66 }PTNode;
 67 //树的结构
 68 typedef struct{
 69     //树的结点
 70     PTNode node[MAX_TREE_SIZE];
 71     //树的根的位置
 72     int r;
 73     //树的结点数
 74     int n;
 75 }PTree;
 76 
 77 /*
 78  * 树的孩子表示法
 79  *
 80  * 把每个结点的孩子结点排列起来，看成一个线性表，且以单链表作存储结构，
 81  * 则n个结点有n个孩子链表(叶子的孩子链表为空表)。而n个头指针又组成一个线性表，
 82  * 为了便于查找，便采用顺序存储结构。
 83  */
 84 //孩子结点
 85 typedef struct CTNode{
 86     int child;
 87     struct CTNode *next;
 88 } *ChildPtr;
 89 typedef struct{
 90     TElemType data;
 91     //孩子链表头指针
 92     ChildPtr firstchild;
 93 }CTBox;
 94 typedef struct{
 95     CTBox nodes[MAX_TREE_SIZE];
 96     //结点数
 97     int n;
 98     //根的位置
 99     int r;
100 }CTree;
101 
102 /*
103  * 树的孩子兄弟表示法，别名二叉树表示法，二叉链表表示法
104  *
105  * 以二叉链表作树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点
106  */
107 typedef struct{
108     //data为数据域
109     TElemType data;
110     //firstchild指向该结点的第一个孩子结点
111     struct CSNode *firstchild;
112     //nextsibling指向该结点的下一个兄弟结点
113     struct CSNode *nextsibling;
114 }CSNode, *CSTree;
115 
116 int main(int argc, char *argv[])
117 {
118     printf("本代码只是用C表示树和二叉树的如下几种存储结构: 

");
119     printf("二叉树的顺序存储、二叉树的链式存储(二叉链表)、二叉树的链式存储(三叉链表)

");
120     printf("树的双亲表示法、树的孩子表示法、树的孩子兄弟表示法

");
121     return 0;
122 }

树和二叉树的存储结构(C语言)

运行