val); -6ren">
gpt4 book ai didi

【算法】二叉树的各种遍历方式

转载 作者:知者 更新时间:2024-03-13 04:27:19 27 4
gpt4 key购买 nike

1.前序遍历
根-左-右的顺序遍历,可以使用递归

void preOrder(Node *u){
    if(u==NULL)return;
    printf("%d ",u->val);
    preOrder(u->l);preOrder(u->r);
}

2.中序遍历
左-根-右的顺序遍历,可以使用递归

void inOrder(Node *u){
    if(u==NULL)return;
    inOrder(u->l);
    printf("%d ",u->val);
    inOrder(u->r);
}

3.后序遍历
左-右-根的顺序遍历,可以使用递归

void postOrder(Node *u){
    if(u==NULL)return;
    postOrder(u->l);postOrder(u->r);
    printf("%d ",u->val);
}

4.层序遍历
使用队列,类似于BFS宽搜算法
每次将左和右结点放入队列,然后将队头输出

void bfs(Node *t){
	queue<Node*>q;
	Node *ft;
	q.push(t);
	while(q.size()){
		ft=q.front();
		q.pop();
		if(ft==NULL)continue;
		else{
			printf("%d ",ft->val);
			q.push(ft->l);
			q.push(ft->r);
		}
	}
	
}

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com