数据结构实验六之二叉树的孩子链表发和双亲链表法

#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);

}

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

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

运行结果如下：