欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树之 树的遍历

程序员文章站 2022-05-19 20:56:42
...

树的遍历

我萌讨论的是一般的树,就是子结点个数不限同时也没有先后次序的树

let’s start

结点结构体定义:`

struct node {
	int data; //数据域
	vector<int> child; //指针域,存放所有子结点的下标
} Node[maxn];//结点数组

树的先根遍历:

void PreOrder(int root) {
	printf("%d ",Node(root).data); //访问当前结点
	for(int i =0; i<Node[root].child.size(); i++) {
		PreOrder(Node[root].child[i]); //递归访问结点root的所有子结点
	}
}

树的层序遍历:

void LayerOrder(int root) {
	queue<int> Q;
	Q.push(root); //将根结点入队
	while(Q.empty()) {
		int front = Q.front();//取出队首元素
		printf("%d ",Node[front].data); //访问当前结点的数据域
		Q.pop(); 
		for(int i = 0; i<Node[front].child.size(); i++) {
				q.push(Node[front].child[i]); //将当前结点的所有子结点入队
		}
	}
}

未完待续

相关标签: