树的双亲表示法

由于树中的每个结点都有唯一的一个双亲结点，所以可用一组连续的存储空间（一维数组）存储树中的各个结点，数组中的一个元素表示树中的一个结点，每个结点含两个域，数据域存放结点本身信息，双亲域指示本结点的双亲结点在数组中位置。

                                       R

                           A          B        C

                     D         E               F 

                                           G    H     K

 

双亲表示法 结点序号dataparent0R-11A02B03C04D15E16F37G68H69K6 输入数据样例

R -1 A 0 B 0 C 0 D 1 E 1 F 3 G 6 H 6 K 6

#include<cstdio> #include<iostream> using namespace std; typedef struct Node{ char data; int parent; }PTNode; typedef struct{ PTNode nodes[100]; int n; }PTree; void CreateTree(PTree &T){ char ch; int n,j; cout<<"请输入结点个数："<<endl; cin>>n; cout<<"请输入结点数据和其双亲序号："<<endl; for(int i=0;i<n;i++){ fflush(stdin);//清空输入缓冲区 cin>>ch>>j; T.nodes[i].data=ch; T.nodes[i].parent=j; } T.nodes[0].parent=-1; } void FindParent(PTree T){ int i; cout<<"请输入要查找结点的序号"<<endl; cin>>i; cout<<"父亲结点序号为："<<T.nodes[i].parent<<endl; } int main(){ PTree T; CreateTree(T); while(1)//输入测试数据 FindParent(T); }