江苏省网站建设,哪些网站做婚纱摄影,wordpress 一级目录下,网易企业邮箱续费学习树之前#xff0c;我们已经了解了二叉树的顺序存储和链式存储#xff0c;哪么我们如何来存储普通型的树结构的数据#xff1f;如下图1#xff1a; 如图1所示#xff0c;这是一颗普通的树#xff0c;我们要如何来存储呢#xff1f;通常#xff0c;存储这种树结构的数…学习树之前我们已经了解了二叉树的顺序存储和链式存储哪么我们如何来存储普通型的树结构的数据如下图1 如图1所示这是一颗普通的树我们要如何来存储呢通常存储这种树结构的数据的方法有3中
双亲表示法。孩子表示法。孩子兄弟表示法。
双亲表示法 双亲表示法采用顺序表也就是数组存储普通树核心思想顺序存储各个节点的同时给各个节点附加一个记录其父节点位置的变量。 注意根结点没有父节点因此根结点记录父节点位置的变量一般为-1。
例如采用双亲表示法存储图1中的普通树其存储状态如图2所示 图2存储普通树转化为代码为
#define MAX_SIZE 100//定义树中结点最大数量
typedef struct node{char data;//树中结点的数据int parent;//结点的父节点再数组中的位置下标
};typedef struct {node arr[MAX_SIZE];//存放树中所有结点int n;//节点数
}Tree;因此存储图1中普通树的实现代码为
#include iostreamusing namespace std;
#define MAX_SIZE 100//定义树中结点最大数量
typedef struct node{char data;//树中结点的数据int parent;//结点的父节点再数组中的位置下标
};typedef struct {node arr[MAX_SIZE];//存放树中所有结点int n;//节点数
}Tree;Tree Init(Tree tree){cout 请输入结点个数 endl;cin tree.n;cout 请输入结点的值其双亲位于数组中的位置下标 endl;for(int i 0; i tree.n; i){cin tree.arr[i].data tree.arr[i].parent;}return tree;
}void FindParent(Tree tree){char a;bool IsFind false;cout 请输入要查询的节点值 endl;cin a;for(int i 0; i tree.n; i){if(tree.arr[i].data a){IsFind true;cout a 的父节点为 tree.arr[tree.arr[i].parent].data 存储位置下标为 tree.arr[i].parent endl;break;}}
}
int main(){Tree tree;for(int i 0; i MAX_SIZE; i){tree.arr[i].parent -1;tree.arr[i].data ;}tree Init(tree);FindParent(tree);return 0;
}程序运行实例
请输入结点个数
10
请输入结点的值其双亲位于数组中的位置下标
R -1
A 0
B 0
C 0
D 1
E 1
F 3
G 6
H 6
K 6
请输入要查询的节点值
C
C的父节点为R存储位置下标为0孩子表示法
孩子表示法是采用“顺序表链表”的组合结构其存储过程是从树的根结点开始使用顺序表依次存储树中各个节点需要注意的是与双亲表示法不同孩子表示法会给各个节点配备一个链表用于存储各个节点的孩子节点位于顺序表中的位置。
如果孩子没有叶子节点则该节点的链表为空链表。
例如使用孩子表示法存储图3a中的树则最终存储状况如图3b所示 代码实现如下
#include iostreamusing namespace std;
#define MAX_SIZE 100//定义树中结点最大数量
typedef struct node{int child;//链表中每个结点存储的是数据再数组中存储的位置下标struct node *next;
};
typedef struct {char data;//结点的数据node * FirstChild;//孩子链表的头节点
}box;
typedef struct {box arr[MAX_SIZE];//存放树中所有结点int n, r;//节点数和树根的位置
}Tree;Tree Init(Tree tree){cout 请输入结点个数;cin tree.n;for(int i 0; i tree.n; i){cout 输入第 i 1 个节点的值 ;cin tree.arr[i].data;tree.arr[i].FirstChild new node;tree.arr[i].FirstChild-next NULL;cout 输入结点 tree.arr[i].data 的孩子结点的数量;int num 0;cin num;if(num ! 0){node *p tree.arr[i].FirstChild;for(int j 0; j num; j){node *ptr new node;ptr-next NULL;cout 输入第 j 1 个孩子节点在顺序表中的位置: ;cin ptr-child;p-next ptr;p p-next;}}}return tree;
}void FindKids(Tree tree, char ch){bool IsFind false;for(int i 0; i tree.n; i){if(tree.arr[i].data ch){node *p tree.arr[i].FirstChild-next;while(p){IsFind true;cout tree.arr[p-child].data;p p-next;}break;}}
}
int main(){Tree tree;tree.r 0;//默认根结点的下标为0for(int i 0; i MAX_SIZE; i){tree.arr[i].FirstChild NULL;}tree Init(tree);FindKids(tree, F);//找出结点F的所有孩子结点return 0;
}程序运行结果如下
请输入结点个数10
输入第1个节点的值R
输入结点R的孩子结点的数量3
输入第1个孩子节点在顺序表中的位置: 1
输入第2个孩子节点在顺序表中的位置: 2
输入第3个孩子节点在顺序表中的位置: 3
输入第2个节点的值A
输入结点A的孩子结点的数量2
输入第1个孩子节点在顺序表中的位置: 4
输入第2个孩子节点在顺序表中的位置: 5
输入第3个节点的值B
输入结点B的孩子结点的数量0
输入第4个节点的值C
输入结点C的孩子结点的数量1
输入第1个孩子节点在顺序表中的位置: 6
输入第5个节点的值D
输入结点D的孩子结点的数量0
输入第6个节点的值E
输入结点E的孩子结点的数量0
输入第7个节点的值F
输入结点F的孩子结点的数量3
输入第1个孩子节点在顺序表中的位置: 7
输入第2个孩子节点在顺序表中的位置: 8
输入第3个孩子节点在顺序表中的位置: 9
输入第8个节点的值G
输入结点G的孩子结点的数量0
输入第9个节点的值H
输入结点H的孩子结点的数量0
输入第10个节点的值K
输入结点K的孩子结点的数量0
找出节点 F 的所有孩子节点GHK使用孩子表示法存储的树结构正好和双亲表示法相反适用于 查找某个节点的孩子结点不适用于查找父节点。
其实我们也可以将双亲表示法和孩子表示法相互结合就可以得到如图4所示 使用图4结果存储普通树技能快速找到指定节点的父节点也能快速找到指定结点的孩子结点。
孩子兄弟表示法 孩子兄弟表示法采用的是链式存储结构其思想是从树的根结点开始依次用链表存储各个节点的孩子结点和兄弟节点。 所以该链表中的结点包括3个部分如图5所示
结点的值。指向孩子结点的指针。指向兄弟结点的指针。 代码表示如下
typedef struct node{char data;struct node *ForstChild, *NextSibling;
};还是以图1为例使用孩子兄弟表示法进行存储的结果如图所示 由图我们可以发现孩子兄弟表示法是用二叉树的左子树存储树的孩子结点用右子树来存储兄弟结点。
孩子兄弟表示法可以作为将普通树转化为二叉树的最有效的方法同时这个方法也被称之为“二叉树表示法”或者”二叉链表表示法“
