Catalog
数据结构实验六之二叉树的孩子链表发和双亲链表法
#include <iostream>
using namespace std;
#define MAX_TREE_SIZE 100

下面是二叉树的双亲表示法

typedef struct PTNode {
char data;
int parent;
}PTNode;

typedef struct {
PTNode nodes[MAX_TREE_SIZE];
int r, n;
}PTree;

void Create_Parentree(PTree &p) {
char data;
int parent;
for (int i = 0; i < p.n; i++) {
cout << "请输入节点"<<i <<"的值及其父节点" << endl;
cin >> data >> parent;
p.nodes[i].data = data;
p.nodes[i].parent = parent;
}
cout << "输入结束" << endl;
}

void Traversal_Parentree(PTree &p) {
for (int i = 0; i < p.n; i++) {
//if(p.nodes[i+1].parent == i)
//cout << p.nodes[i].data << " ";
cout << "节点" << p.nodes[i].data << "的子节点为:" << endl;
int flag = 0;
int flag2 = 0;
for(int j = i; ;j++){
if (j == p.n - 1) break;
if (p.nodes[j + 1].parent == i) {
cout << p.nodes[j + 1].data << " ";
flag = 1;
flag2 = 1;
}
else if(p.nodes[j + 1].parent != i && flag == 1)
break;
}
if (!flag2) cout << "无";
cout << endl;

}
cout << endl;
}

下面是二叉树的孩子表示法:

typedef struct CTNode {//孩子节点
int child;
struct CTNode *next;
}*ChildPtr;
typedef struct {
char data;
ChildPtr firstchild;//孩子链表头指针
}CTBox;
typedef struct {
CTBox nodes[MAX_TREE_SIZE];
int n, r;//节点数和根的位置
}CTree;


void Create_Childtree(CTree &p) {

char data;

//ChildPtr c =(ChildPtr)malloc (sizeof(CTNode));

for (int i = 0; i < p.n; i++) {
p.nodes[i].firstchild = (ChildPtr)malloc(sizeof(CTNode));
cout << "输入节点" << i << "的值" << endl;
cin >> data;
p.nodes[i].data = data;
cout << "输入值来判定头节点"<<i<<"的next是否为空" << endl;
int temp;
cin >> temp;
if (temp == -1) {
p.nodes[i].firstchild = NULL;
continue;
}

else
{
cout << "输入第一个孩子节点的值" << endl;
cin >> p.nodes[i].firstchild->child;
cout << "输入第一个孩子节点next的值以判断是否为空" << endl;
cin >> temp;

ChildPtr c2 = (ChildPtr)malloc(sizeof(CTNode));
if (temp == -1) {
c2 = NULL;
p.nodes[i].firstchild->next = c2;
continue;
}

else {
//ChildPtr c3 = (ChildPtr)malloc(sizeof(CTNode));
p.nodes[i].firstchild->next = c2;
cout << "输入第二个孩子节点的值" << endl;
cin >> c2->child;
}
cout << "输入第二个孩子节点next的值" << endl;
cin >> temp;
if (temp == -1) {
c2->next = NULL;
continue;
}
ChildPtr cctemp;
while (temp != -1) {
ChildPtr cc;
cc = (ChildPtr)malloc(sizeof(CTNode));
c2->next = cc;
cctemp = cc;
c2 = cc;

cout << "输入节点值" << endl;
cin >> cc->child;
cout << "输入节点的next的值" << endl;
cin >> temp;
}
cctemp->next = NULL;
}

}

}

void Tranversal_Childrentree(CTree &p) {
for (int i = 0; i < p.n; i++) {
ChildPtr t = (ChildPtr)malloc(sizeof(CTNode));
cout << "节点" << p.nodes[i].data << "的子树位置为:";
if (p.nodes[i].firstchild == NULL)
cout << "无子树" << endl;
else {
cout << p.nodes[i].firstchild->child <<" ";
t = p.nodes[i].firstchild->next;
while (t != NULL) {
cout << t->child <<" ";
t = t->next;
}
cout << endl;
continue;
}

}
}

main函数:

(我将双亲表示法做了注释)

int main() {
//树的双亲表存储表示
#if 0
PTree P;
cout << "请输入根节点的位置:" << endl;
cin >> P.r;
cout << "请输入节点数" << endl;
cin >> P.n;
Create_Parentree(P);
Traversal_Parentree(P);
#endif
//树的孩子节点表示
CTree P2;
cout << "请输入根节点的位置:" << endl;
cin >> P2.r;
cout << "请输入节点数" << endl;
cin >> P2.n;
Create_Childtree(P2);
Tranversal_Childrentree(P2);

}

双亲表示法运行结果如下:

孩子表示法的输入过程如下:

运行结果如下:

Author: superzhaoyang
Link: http://yoursite.com/2019/11/18/数据结构实验六之二叉树的孩子链表发和双亲链表法/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付宝

Comment