Arect和他的……
数据结构第二次上机实验

二叉树的基本操作

感谢dyf同学的代码,不然我还做不出来,得用某种手段才能实现

  • 创建二叉树
  • 输出路径和路径长度
#include<iostream>
#include<conio.h>
#include<vector>
using namespace std;
class tree {
public:
	char data = '0';
	tree* left = NULL;
	tree* right = NULL;
	tree(char a) {
		data = a;
	}
	tree() {}
};
char temp = '0';
tree* readTree(tree* t) {
	temp = _getch();
	cout << temp;
	if (temp != '#') {
		t = new(tree)(temp);
		t->left = readTree(t->left);
		t->right = readTree(t->left);
		return t;
	}
	else return NULL;
}
bool preo(tree* t) {
	if (t != NULL) {
		cout << t->data << " ";
		preo(t->left);
		preo(t->right);
	}
	return true;
}
bool treeLenth(tree* t, int num, string str) {
	if (t == NULL) {
		return false;
	}
	if (num == 0) {
		cout << "[" << t->data << "] 第" << num << "层\n";
		str.push_back(t->data);
		num++;
		treeLenth(t->left, num, str);
		treeLenth(t->right, num, str);
	}
	else if (num > 0) {
		for (unsigned int i = 0; i < str.size(); i++) {
			cout << "[" << str[i] << "]" << "->";
		}
		cout << "[" << t->data << "] 第" << num << "层\n";
		str.push_back(t->data);
		num++;
		treeLenth(t->left, num, str);
		treeLenth(t->right, num, str);
	}
	return true;
}
int main() {
	tree* root = NULL;
	cout << "请输入二叉树(先根):";
	root = readTree(root);
	cout << "\n先根遍历顺序为:";
	preo(root);
	cout << "\n";
	string str;
	treeLenth(root, 0, str);
}

验证图的遍历算法

又是抄的……

  • 深度优先遍历
  • 广度优先遍历
#include<iostream>
#include<conio.h>
#include<vector>
using namespace std;
class graphNode {
public:
	unsigned int VerAdj = 0;//序号
	int cost = 0;//权值
	graphNode* link = NULL;//下一个
	graphNode() {}
	graphNode(const unsigned int a) {
		VerAdj = a;
	}
};
class graph {
public:
	unsigned int VerName = 0;//序号
	graphNode* adjacent = NULL;//下一个
	graph() {}
	graph(const unsigned int a) {
		VerName = a;
	}
};
vector<bool> DFS(vector<graph> gr, unsigned int g, vector<bool> visited) {
	cout << "[" << gr[g].VerName << "] ";
	visited[g] = true;
	graphNode* p = gr[g].adjacent;
	while (p != NULL) {
		if (!visited[p->VerAdj]) {
			visited = DFS(gr, p->VerAdj, visited);
		}
		p = p->link;
	}
	return visited;
}
bool DFS_Main(vector<graph> gr, int x) {
	vector<bool> visited(gr.size(), false);
	for (unsigned int i = x; i < gr.size(); i++) {
		if (!visited[i]) {
			visited = DFS(gr, i, visited);
		}
	}
	for (unsigned int i = 0; i < x; i++) {
		if (!visited[i]) {
			visited = DFS(gr, i, visited);
		}
	}
	return true;
}
vector<graph> creatGraph() {
	cout << "结点数:";
	int num = 0;
	cin >> num;
	vector<graph> gr;
	for (int i = 0; i < num; i++) {
		gr.push_back(*new(graph)(i));
	}
	cout << "边数:";
	cin >> num;
	char ch_1 = '0', ch_2 = '0';
	for (int i = 0; i < num; i++) {
		cout << "连接";
		ch_1 = _getch();
		cout << ch_1 << "->";
		cin >> ch_2;
		graphNode* p = gr[ch_1 - '0'].adjacent;
		do {
			if (gr[ch_1 - '0'].adjacent == NULL) {
				gr[ch_1 - '0'].adjacent = new(graphNode)(ch_2 - '0');
				p = NULL;
				continue;
			}
			else {
				if (p->link == NULL) {
					p->link = new(graphNode)(ch_2 - '0');
					p = NULL;
					continue;
				}
				p = p->link;
			}
		} while (p != NULL);
	}
	return gr;
}
bool BFS(vector<graph> gr, unsigned int g) {
	vector<int> Q;
	vector<bool>visited(gr.size(), false);
	cout << "[" << gr[g].VerName << "] ";
	visited[g] = true;
	Q.push_back(g);
	graphNode* p = NULL;
	while (Q.size() > 0) {
		p = gr[Q[0]].adjacent;
		Q.erase(Q.begin(), Q.begin() + 1);
		while (p != NULL) {
			if (!visited[p->VerAdj]) {
				cout << "[" << p->VerAdj << "] ";
				visited[p->VerAdj] = true;
				Q.push_back(p->VerAdj);
			}
			p = p->link;
		}
	}
	return true;
}
int main() {
	vector<graph>gr = creatGraph();
	cout << "深度优先遍历,从此结点开始\n";
	int xx = 0;
	cin >> xx;
	DFS_Main(gr, xx);
	cout << "\n广度优先遍历,从此结点开始\n";
	cin >> xx;
	BFS(gr, xx);
}
首页      本地磁盘(C:)      数据结构第二次上机实验

INSPI

文章作者

保持学者的沉默与谦恭

发表评论

textsms
account_circle
email

Arect和他的……

数据结构第二次上机实验
二叉树的基本操作 感谢dyf同学的代码,不然我还做不出来,得用某种手段才能实现 创建二叉树输出路径和路径长度 #include<iostream> #include<conio.h> #include<vector…
扫描二维码继续阅读
2019-12-01