数据结构OJ实验7-树结构及应用

A. 树的先序遍历（双亲转先序）

题目描述

亲表示法结果，用一个二维数组表示，位置下标从0开始，如果双亲位置为-1则表示该结点为根结点

编写程序，输出该树的先根遍历结果。

输入

第一个输入t，表示有t棵树

接着每棵树输入3行：

第1行输入n，表示树有n个结点

第2行输入n个英文字母，表示每个树结点的数值

第3行输入n个整数，表示每个结点的双亲在数组的下标

以此类推输入下一棵树

输出

共输出t行，每行输出一棵树的先根遍历结果

样例查看模式?

正常显示查看格式

输入样例1?

2
7
A?B?C?D?E?F?G
-1?0?0?0?1?1?3
10
A?B?C?D?R?E?F?G?H?K
4?4?4?0?-1?0?2?6?6?6

输出样例1

ABEFCDG
RADEBCFGHK

AC代码

#include<iostream>
#include<vector>
using namespace std;
struct node
{
	char data;
	int fa;
	node()
	{
		data = '0';
		fa = -1;//全部默认自己为根
	}
};
class tree
{
	vector<node>t;
	int n;
public:
	tree()
	{
		cin >> n;
		t.resize(n);
		for (int i = 0; i < n; i++)
		{
			char ch;
			cin >> ch;
			t[i].data = ch;
		}
		for (int i = 0; i < n; i++)
		{
			int x;
			cin >> x;
			if (x != -1)
			{
				t[i].fa = x;
			}
		}
	}
	void pre(int x = -1)
	{
		for (int i = 0; i < n; i++)
		{
			if (t[i].fa == x)
			{
				cout << t[i].data;
				pre(i);
			}
		}
	}
};
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		tree tt;
		tt.pre();
		cout << endl;
	}
	return 0;
}

B. 树的后根遍历（孩子链表法）

题目描述

根据树的孩子链表表示法构建一棵树，并输出树的后根遍历

下标位置从0开始

输入

第一行输入两个参数，第一个参数n表示树有n个结点，第二个参数r表示根结点的数组下标

接着n行，每行先输入一个结点的数值（用单个字母表示），再输入结点的孩子的下标，最后以-1结尾

如果该结点没有孩子，则一行只输入结点的数值和-1

输出

只有一行输出，树的后根遍历结果

样例查看模式?

正常显示查看格式

输入样例1?

10?4
A?3?5?-1
B?-1
C?6?-1
D?-1
R?0?1?2?-1
E?-1
F?7?8?9?-1
G?-1
H?-1
K?-1

输出样例1

DEABGHKFCR

AC代码

#include<iostream>
#include<vector>
using namespace std;
struct node
{
	char data;
	vector<int>child;//孩子用数组形式表示
};
class tree
{
	vector<node>t;
	int n;
	int root;
	void pos(int x)
	{
		for (int i = 0; i < t[x].child.size(); i++)
		{
			pos(t[x].child[i]);
		}
		cout << t[x].data;//遍历孩子后才输出根
	}
public:
	tree()
	{
		cin >> n >> root;
		t.resize(n);
		for (int i = 0; i < n; i++)
		{
			cin >> t[i].data;
			vector<int>temp;
			int x;
			cin >> x;
			while (x != -1)
			{
				temp.push_back(x);
				cin >> x;
			}
			t[i].child = temp;
		}
	}
	void posorder()
	{
		pos(root);
		cout << endl;
	}
};
int main()
{
	tree tt;
	tt.posorder();
	return 0;
}

C. 树结构转换（先序转双亲）

题目描述

给出一棵二叉树的特定字符先序遍历结果（空子树用字符'#'表示），构建该二叉树，并输出该二叉树的双亲表示法结果

双亲表示法的数组下标从0开始，根结点必定是在下标0元素，且根结点的双亲下标为-1，左右孩子按下标递增顺序排列,

结点下标是层次遍历顺序。

输入

第一个输入t，表示有t棵二叉树

接着t行，每行输入含特定字符的二叉树先序遍历序列

输出

共输出2t行

每棵二叉树输出两行，第一行输出各个结点的数值，第二行输出各结点的双亲下标

样例查看模式?

正常显示查看格式

输入样例1?

3
AB#C##D##
ABD##E##C##
AB##CDW###E#F##
?

输出样例1

A?B?D?C
-1?0?0?1
A?B?C?D?E
-1?0?0?1?1
A?B?C?D?E?W?F
-1?0?0?2?2?3?4

AC代码

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct node
{
	char data;
	node* l;
	node* r;
	node* fa;
	node(char c, node* ll = NULL, node* rr = NULL, node* ff = NULL)
	{
		data = c;
		l = ll;
		r = rr;
		fa = ff;
	}
};
class tree
{
	node* root;
	vector<node*>a;//存树结点
	vector<int>b;//存父亲下标
	int len;
	void Create(node*& n, node* f)
	{
		char ch;
		cin >> ch;
		if (ch == '#')
		{
			n = NULL;
			return;
		}
		n = new node(ch);
		n->fa = f;
		Create(n->l,n);
		Create(n->r,n);
	}
	int find(node* n)//找父亲下标
	{
		if (n == NULL)
		{
			return -1;//为根节点
		}
		for (int i = 0; i < 1000; i++)//从头找到尾
		{
			if (n == a[i])return i;
		}
	}
public:
	tree()
	{
		root = NULL;
		a.resize(1000);
		b.resize(1000);
	}
	void createtree()
	{
		Create(root, NULL);
	}
	void lerorder()//二叉树转换为树，采用层次遍历
	{
		queue<node*>v;
		int idx = 0;
		if (root != NULL)
		{
			v.push(root);
			while (!v.empty())
			{
				a[idx] = v.front();
				b[idx] = find(v.front()->fa);
				idx++;
				if (v.front()->l != NULL)v.push(v.front()->l);
				if (v.front()->r != NULL)v.push(v.front()->r);
				v.pop();
			}
		}
		len = idx;
	}
	void show()
	{
		for (int i = 0; i < len; i++)
		{
			if (i)cout << " ";
			cout << a[i]->data;
		}
		cout << endl;
		for (int i = 0; i < len; i++)
		{
			if (i)cout << " ";
			cout << b[i];
		}
		cout << endl;
	}
};
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		tree b;
		b.createtree();
		b.lerorder();
		b.show();
	}
	return 0;
}

D. 树的双亲结构转孩子链表结构

题目描述

给出一棵树的双亲表示法结果，用一个二维数组表示，位置下标从0开始，如果双亲位置为-1则表示该结点为根结点

编写程序，输出该树的孩子链表表示法结果。

输入

输入一棵树的双亲表示法，共3行：

第1行输入n，表示树有n个结点

第2行输入n个英文字母，表示每个树结点的数值

第3行输入n个整数，表示每个结点的双亲在数组的下标

输出

按输入的结点顺序输出n行，每行输出结点孩子链表结果，先输出结点的数值，再输出结点的孩子的下标，以空格隔开，最后一个数据后面也有空格

如果链表为空则输出结点数值后，输出-1带空格，具体看样式

样例查看模式?

正常显示查看格式

输入样例1?

7
A?B?C?D?E?F?G
-1?0?0?0?1?1?3
?

输出样例1

A?1?2?3?
B?4?5?
C?-1?
D?6?
E?-1?
F?-1?
G?-1?

AC代码

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct node
{
	char data;
	int fa;
	vector<int>child;
	node()
	{
		data = '0';
		fa = -1;
	}
};
class tree
{
	int n;
	vector<node>t;
public:
	tree()
	{
		cin >> n;
		t.resize(n);
		for (int i = 0; i < n; i++)
		{
			char c;
			cin >> c;
			t[i].data = c;
		}
		for (int i = 0; i < n; i++)
		{
			int x;
			cin >> x;
			if (x != -1)
			{
				t[i].fa = x;
				t[x].child.push_back(i);//在这加入下标为x的孩子，因为x表示i的父亲
			}
		}
	}
	void show()
	{
		for (int i = 0; i < n; i++)
		{
			cout << t[i].data << " ";
			if (t[i].child.size() == 0)
			{
				cout << -1 << " " << endl;
			}
			else
			{
				for (int j = 0; j < t[i].child.size(); j++)
				{
					cout << t[i].child[j] << " ";
				}
				cout << endl;
			}
		}
	}
};
int main()
{
	tree b;
	b.show();
	return 0;
}

E. DS森林叶子编码

题目描述

给定一组森林，编写程序生成对应的二叉树，输出这颗二叉树叶结点对应的二进制编码.规定二叉树的左边由0表示，二叉树的右边由1表示。

输入：

N B? 表示N个树，每结点最多B个分支

第2行至第N+1行，每个树的先序遍历

输出

每行表示一个叶结点对应的二进制编码.

样例查看模式?

正常显示查看格式

输入样例1?

3?3
A?B?0?0?0?C?0?0?0?D?0?0?0
E?F?0?0?0?0?0
G?H?0?0?0?I?J?0?0?0?0?0?0

输出样例1

0?1?1
1?0
1?1?0?1?0

AC代码

#include<bits/stdc++.h>
using namespace std;
struct node
{
    char data;
    node* l;
    node* r;
    node()
    {
        l = NULL;
        r = NULL;
    }
};
node* createtree(string s, int& idx, int b)
{
    node* n = NULL;
    if (idx < s.size() && s[idx] != '0')
    {
        n = new node;
        n->data = s[idx];
        idx += 2;
        int i = 0;
        while (!n->l && i < b)//左孩子为空则继续找 
        {
            n->l = createtree(s, idx, b);
            i++;
        }
        //其他孩子为左孩子的右孩子
        node* temp = n->l;
        for (; i < b; i++)
        {
            if (s[idx] != '0')
            {
                temp->r = createtree(s, idx, b);
                temp = temp->r;
            }
            else idx += 2;
        }
    }
    else idx += 2;
    return n;
}
void buildcode(node* n, string ans)
{
    if (n->l)
        buildcode(n->l, ans + "0");
    if (n->r)
        buildcode(n->r, ans + "1");
    if (!n->l && !n->r)
    {
        cout << ans[0];
        for (int i = 1; i < ans.length(); i++)
            cout << ' ' << ans[i];
        cout << endl;
    }
}
int main()
{
    int n, b;
    cin >> n >> b;
    getchar();
    vector<string>forest(n);
    vector<node*>root(n);//每一串都为一个二叉树
    for (int i = 0; i < n; i++)
    {
        getline(cin, forest[i]);
        int idx = 0;
        root[i] = createtree(forest[i], idx, b);
    }
    for (int i = 0; i < n - 1; i++)
    {
        root[i]->r = root[i + 1];
    }
    buildcode(root[0], "");
    return 0;
}

F. 先序+中序还原二叉树

题目描述

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

输入

输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。

输出

输出为一个整数，即该二叉树的高度。

样例查看模式?

正常显示查看格式

输入样例1?

9
ABDFGHIEC
FDHGIBEAC

输出样例1

5

AC代码

#include<bits/stdc++.h>
using namespace std;
struct node
{
    char data;
    node* l;
    node* r;
    node(char c, node* ll = NULL, node* rr = NULL)
    {
        data = c;
        l = ll;
        r = rr;
    }
};
//已知n个结点,先序序列为p,中序序列m
node* createtree(int n,char p[],char m[])
{
    node* root = NULL;
    if (n == 0)return NULL;
    root = new node(' ');
    root->data = p[0];//由先序找根
    //找到中序序列中的相对应数据
    for (int i = 0; i < n; i++)
    {
        if (p[0] == m[i])//找到中间根
        {
            root->l = createtree(i, p + 1, m);
            root->r = createtree(n - i - 1, p + 1 + i, m + 1 + i);
        }
    }
    return root;
}
int high(node* root)
{
    if (root == NULL)return 0;
    int lefth = high(root->l);
    int righth = high(root->r);
    return max(lefth, righth) + 1;
}
int main()
{
    int n;
    node* root;
    char pre[100], mid[100];
    cin >> n >> pre >> mid;
    root = createtree(n, pre, mid);
    cout << high(root) << endl;
    return 0;
}