叶子节点路径

给定一棵有N个节点（编号为1-N）的树，试输出树从根结点到所有叶结点的路径。

[输入格式]

第一行包含一个整数N，代表节点数

第二行包含N个整数p1，p2，…，pn，代表每个节点的父节点编号。若pi=0，则该节点为树的根节点

[输出数据]

输出树中从根结点到所有叶结点的路径

[输入规范]

0≤pi≤N有且仅有一个pi=0

[样例1]

输入：

7

0 5 5 1 4 1 4

输出：

1-4-5-2、1-4-5-3、1-4-7、1-6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
using namespace std;

int tree[100];
int ans[100];
bool notleaf[100];//notleaf[i]==true表示第i个节点不是叶子节点
int n;
void find(int i, int ansLen) {//i表示当前在第几个节点，ansLen表示ans的长度
	if (tree[i] == 0) {//从叶子节点找根节点
		cout << i << "-";
		for (int i = ansLen-1; i >0; i--)
			cout << ans[i] << "-";
		cout << ans[0] << "、";
	}
	else {
		ans[ansLen] = i;
		ansLen++;
		find(tree[i], ansLen);
		ansLen--;
	}
}

void find1(int k, int ansLen) {//i表示当前在第几个节点，ansLen表示ans的长度
	ans[ansLen] = k;
	ansLen++;
	int i;
	for (i = 1; i <= n; i++) {//从根节点找叶子节点
		if (tree[i] == k) {
			find1(i, ansLen);
		}
	}
	if (!notleaf[k]) {//k如果为叶子节点
		for (int j = 0; j < ansLen-1; j++)
			cout << ans[j] << "-";
		cout << ans[ansLen-1] << "、";
	}
	ansLen--;
}
int main()
{
	freopen("./data1.txt", "r", stdin);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> tree[i];
		notleaf[tree[i]] = true;
	}

	//find时间复杂度较低，但输出顺序与原题不同：1-6在1-4-7之前
	//for(int i=1;i<=n;i++)
	//	if(!notleaf[i])	find(i, 0);//是叶子节点则去寻找
	
	//find1时间复杂度较高，但输出顺序与原题一样
	find1(1, 0);
	printf("\b");//删掉最后多出来的"、"
}

树的高度和宽度

2、对于输入父结点信息，实现采用孩子-兄弟链表（二叉链表）表示树，编程计算树的高度、宽度（树的宽度为树中具有最多结点数量的那一层的结点数）。

[输入格式]

第一行包含一个整数N，代表节点数

第二行包含N个整数p1，p2，…，pn，代表每个节点的父节点编号。若pi=0，则该节点为树的根节点

[输出数据]

输出两个正整数，分别表示树的高度、宽度

[输入规范]

0≤pi≤N

+有且仅有一个pi=0

[样例1]

输入：

10

0 1 5 1 4 1 4 6 6 3

输出：

5、4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
using namespace std;

typedef  struct  Node
{
    int data;//记录当前节点
    int high;//记录所处高度
    int  parent;//记录父节点
    struct  Node* lchild = NULL;
    struct  Node* rbrother = NULL;
}Node, * Tree;

Tree tree;
int maxhigh = 0;//最大高度
int wide[100];//wide[i]表示第i层宽度
int maxWide = 0;//最大宽度

void find(Tree T,int nowhigh) {//nowhigh记录当前高度
    maxhigh = maxhigh > nowhigh ? maxhigh : nowhigh;//更新最大高度
    wide[nowhigh]++;
    maxWide = maxWide > wide[nowhigh] ? maxWide : wide[nowhigh];//更新最大宽度
    if (T->lchild)find(T->lchild, nowhigh + 1);
    if (T->rbrother)find(T->rbrother, nowhigh);
}

int main()
{
	freopen("./data2.txt", "r", stdin);

    int n;
    cin >> n;
    tree = (Tree)malloc(sizeof(Node) * (n + 1));
    memset(tree, 0, sizeof(Node) * (n + 1));
    //创建树
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        tree[i].data = i;
        tree[i].parent = a;
        if (tree[a].lchild == NULL)tree[a].lchild = &tree[i];//父节点为空，则父节点左孩子指向它
        else {//父节点不为空，则找右兄弟
            Tree ptr=tree[a].lchild;
            while (ptr->rbrother != NULL)ptr = ptr->rbrother;
            ptr->rbrother = &tree[i];
        }
    }
    find(tree+1, 1);//0表示根节点的父节点，因此0号节点不算
    cout << maxhigh << "、" << maxWide << endl;
}

霍夫曼编码

3、对于给定的文本内容，要求采用哈夫曼编码输出编码后的内容，并输出编码内容的解码。文本内容由英文字母构成，这里约定不区分字母的大小写。注意，这里约定构造哈夫曼树时，任一结点的左孩子权值不大于右孩子权值，哈夫曼编码时，左分支写’0’右分支写’1’；若两个字母的权值相等，则字典序小的字母优先；对于相等的权值，按出现的先后顺序处理。

例如，对于样例1，因不区分大小写，若按大写字母处理，则字母A、B、C、D的出现次数为4、1、2、1，则B对应的1为左孩子，D对应的1为右孩子，得到的父结点权值为2，比原有的2晚出现，因此原来的2为左孩子，新得到的2作为右孩子，对于两个权值4也类似处理。构造所得的哈夫曼树如下图所示。

clip_image002

输入格式:

测试数据有多组，处理到文件尾。每组测试数据在一行上输入一个字符串（仅由大小写英文字母构成且长度不超过360，至少包含2种字母）表示文本内容。

输出格式:

对于每组测试数据，输出哈夫曼编码后的内容以及编码结果的解码内容。

输入样例:

AcBDaCAA

输出样例:

01011011101000

AcBDaCAA

输入样例:

eAbCDaAAA

输出样例:

01110000010101111

eAbCDaAAA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<iostream>
using namespace std;
#include<fstream>
#include<string>
#include<string.h>
#include<algorithm>

typedef struct letter{
	int num;//出现次数(权值)
	char c;//记录字母
	char code[26];//记录编码
	int lchild, rchild, parent;//记录左右孩子,父节点
}letter;

string str[100];
int line;//行数

char code[26];//记录编码

int cmp(const void* a, const void* b)  //排序函数 
{
	return (*(letter*)a).c - (*(letter*)b).c;
}

//选择两个最小的
void select(letter* L, int* small1, int* small2, int len) {//small1是左节点，small2是右节点
	int min = 100000000;
	for (int i = 0; i < len; i++) {
		if (L[i].num < min && L[i].parent == NULL) {
			min = L[i].num;
			*small1 = i;
		}
	}
	min = 1000000000;
	for (int i = 0; i < len; i++) {
		if (L[i].num < min&&i!=*small1 && L[i].parent == NULL) {
			min = L[i].num;
			*small2 = i;
		}
	}
	if (L[*small1].num > L[*small2].num) {//保障左节点不大于右节点
		int a = *small1;
		*small1 = *small2;
		*small2 = a;
	}
}
//处理编码
void encode(letter* L,int i,int curCode) {//i表示当前节点，curCode第几位数
	if (L[i].c != '\0') {
		strcpy(L[i].code, code);
		return;//叶子节点直接返回
	}
	else {
		code[curCode] = '0';
		code[curCode+1] = '\x00';
		encode(L, L[i].lchild, curCode + 1);
		code[curCode] = '1';
		code[curCode + 1] = '\x00';
		encode(L, L[i].rchild, curCode + 1);
	}
}

void decode(letter* L, int len, char* encode) {//解码
	int i = 0;
	while (encode[i] != '\0') {//encode为编码后的序列
		for (int j = 0; j < len; j++) {
			int l = strlen(L[j].code);
			if (!strncmp(encode + i, L[j].code, l)) {
				i += l;
				cout << L[j].c;
				break;
			}
		}
	}
	cout << endl;
}

void output(letter* L, int len, int curLine, char* encode) {//输出
	for (int i = 0; i < str[curLine].size(); i++) {
		char c = toupper(str[curLine][i]);
		for (int j = 0; j < len; j++) {
			if (L[j].c == c) {
				cout << L[j].code;
				strcat(encode, L[j].code);
			}
		}
	}
	//cout << endl << str[curLine] << endl;
	cout << endl;
}

void func(int curLine) {//curLine表示当前是第几个字符串
	letter* L = (letter*)malloc(sizeof(letter) * 26);
	memset(L, 0, sizeof(letter) * 26);
	int len = 0;//记录当前记录了多少种字母
	int i, j;
	//都转成大写存储在结构体中，记录出现的次数
	for (i = 0; i < str[curLine].size(); i++) {
		char c = toupper(str[curLine][i]);
		for (j = 0; j < len; j++) {
			if (L[j].c == c) {
				L[j].num++;
				break;
			}
		}
		if (j == len) {
			L[len].c = c;
			L[len].num++;
			len++;
		}
	}

	qsort(L, len, sizeof(letter), cmp);//按照字典序排序
	realloc(L, sizeof(letter) * (2 * len - 1));

	int len2=0;//霍夫曼树中非叶子节点的数量
	int small1, small2;
	while (len2 != len - 1) {
		select(L, &small1, &small2, len+len2);//选出权值最小两个节点的下标
		L[len + len2].num = L[small1].num + L[small2].num;//保存父节点
		L[len + len2].lchild = small1;
		L[len + len2].rchild = small2;
		L[len + len2].parent = NULL;
		L[small1].parent = len + len2;
		L[small2].parent = len + len2;
		len2++;
	}
	encode(L, len + len2 - 1,0);//编码
	char encode[100] = { 0 };
	output(L, len, curLine,encode);//输出
	decode(L, len, encode);//解码
}



int main() {
	//逐行读取文件，存放在str中
	ifstream file;
	file.open("./data3.txt");
	if (file.fail()) {
		cout << "cant open data3.txt" << endl;
		exit(0);
	}
	while (getline(file, str[line]))line++;
	file.close();

	for (int i = 0; i < line; i++)
		func(i);

}

树的其他操作

给定一个二叉树的先序序列，结点编号为整数，编号之间有空格，孩子为空的位置以#替代。建立二叉树的二叉链表

（1） 设计非递归算法统计叶子结点数量、输出所有叶子结点。

（2） 设计非递归算法判断该二叉树是否为二叉排序树。

（3） 计算该二叉树的高度、宽度。

（4） 输出每一层的元素值。

输入样例:

5 7 10 # # 8 6 # # # 9 12 # 4 # # 1# #

输出样例:

（1）4

10 6 4 1

（2）中序遍历序列为：10 7 6 8 5 12 4 9 1

不是排序二叉树

（3）4

（4）

5

7 9

10 8 12 1

6 4

要求自己给出二叉链表的存储定义！创建一棵空树。创建队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include<iostream>
using namespace std;
#define MAX 1e9;
typedef  struct  BiNode
{
	int  data;
	struct  BiNode* lchild, * rchild;
}BiNode, * BiTree;

struct que {
	int head, rear;
	int count;
	BiTree queue[100];
}q;

void push(BiTree T) {
	q.queue[q.rear] = T;
	q.count++;
	q.rear = (q.rear + 1) % 100;
}
BiTree pop() {
	q.count--;
	BiTree T = q.queue[q.head];
	q.head = (q.head + 1) % 100;
	return T;
}
void push_stack(BiTree T) {
	q.queue[q.count] = T;
	q.count++;

}
BiTree pop_stack() {
	q.count--;
	BiTree T = q.queue[q.count];
	return T;
}

BiTree tree;
int nodedata[100];

void create(BiTree &tree) {
	static int offset = 0;//记录到字符串第几个位置
	if (nodedata[offset] == -1)return;
	tree = (BiTree)malloc(sizeof(BiNode));
	memset(tree, 0, sizeof(BiNode));
	tree->data = nodedata[offset];
	offset++;
	create(tree->lchild);
	offset++;
	create(tree->rchild);

}

void findLeaf(BiTree tree) {
	memset(&q, 0, sizeof(q));
	static int num = 0;
	static int leaf[100];
	push(tree);
	tree = tree->lchild;
	//其中一个方法如下,用队列实现，这里顺序与标准答案不一样
	/*
	while (q.count) {
		if (q.queue[q.head]->lchild != NULL)push(q.queue[q.head]->lchild);
		if (q.queue[q.head]->rchild != NULL)push(q.queue[q.head]->rchild);
		else if (q.queue[q.head]->lchild == NULL) {
			leaf[num] = q.queue[q.head]->data;
			num++;
		}
		pop();
	}
	*/

	//第二个方法如下，用栈实现
	while (q.count||tree) {
		while (tree != NULL) {
			push_stack(tree);
			tree = tree->lchild;
		}
		if (!tree) {
			tree = pop_stack();
			if (!tree->rchild&&!tree->lchild) {//判断是否为叶子节点
				leaf[num] = tree->data;
				num++;
			}
			tree = tree->rchild;
		}
	}

	//输出
	cout << num<<endl;
	for (int i = 0; i < num; i++)cout << leaf[i]<<" ";
	cout << endl;
}
void isSort(BiTree tree) {//判断是否是二叉排序树
	memset(&q, 0, sizeof(q));
	int pre = MAX;
	bool issort = true;//true为二叉排序树,false则不是
	//这里用栈实现
	cout << "中序遍历序列为:";
	while (q.count || tree) {
		while (tree != NULL) {
			push_stack(tree);
			tree = tree->lchild;
		}
		if (!tree) {
			tree = pop_stack();
			if (pre < tree->data)issort = false;//如果前一个小，则不是二叉排序树
			cout << tree->data << " ";
			pre = tree->data;
			tree = tree->rchild;
		}
	}
	if (issort)cout << endl << "是二叉排序树" << endl;
	else cout << endl << "不是二叉排序树" << endl;
}

int v[10][10];//v[i][j]表示第i层第j个元素
int num[10];//num[i]表示第i层有多少个元素
void findDeep(BiTree tree,int deep) {
	if (!tree)return;
	else {
		v[deep][num[deep]]=tree->data;
		num[deep]++;
		findDeep(tree->lchild, deep + 1);
		findDeep(tree->rchild, deep + 1);
	}
	if (deep == 0) {//deep等于0说明已经遍历结束，下一步准备输出
		for (int i = 0; num[i]; i++) {
			for (int j = 0; j < num[i]; j++) cout << v[i][j] << " ";
			cout << endl;
		}
	}
}



int main()
{
	//输入5 7 10 # # 8 6 # # # 9 12 # 4 # # 1 # #\n
	freopen("./data4.txt", "r", stdin);
	
	//输入并处理数据
	char str[100];
	fgets(str, 0x100, stdin);
	int i = 0;
	int nodenum = 0;
	int num = 0;
	while (str[i] != '\n') {
		if(str[i]=='#')nodedata[nodenum++] = -1;//#用-1代替
		else if (str[i] >= '0' && str[i] <= '9') {
			num *= 10;
			num += str[i] - '0';
		}
		else if(str[i]==' '&&num!=0) {
			nodedata[nodenum++] = num;
			num = 0;
		}
		i++;
	}

	create(tree);//创建二叉树
	findLeaf(tree);//找叶子节点（两种方法）
	isSort(tree);//判断是否是二叉排序树（非递归）
	findDeep(tree,0);//找每一层元素
}