二叉树的层次遍历以及用层次遍历算法显示所有叶子节点

发布网友发布时间：2022-04-25 14:08

共3个回答

热心网友时间：2022-04-13 14:22

#include <iostream>
using namespace std;
struct segtree{int a,b;} tree[10001];
void buildtree(int l,int r,int root = 0) //建树 {tree[root].a=l;tree[root].b=r;if (l==r)return;int mid=(l+r)>>1;root<<=1;buildtree(l,mid,root+1);buildtree(l,mid,root+2);}
void dfs(int level,int root = 0){for (int i=1;i<level;i++)cout<<' ';cout<<"Lv"<<level<<" : ["<<tree[root].a<<","<<tree[root].b<<"]\n";if (tree[root].a!=tree[root].b){root<<=1;dfs(level+1,root+1);dfs(level+1,root+2);}}
struct {int root,level;} st[100001];
void bfs(){int top=1,first=0;st[first].root=0;st[first].level=1;while (first<top){for (int i=st[first].level;i>1;i--)cout<<' ';cout<<"Lv"<<st[first].level<<" : ["<<tree[st[first].root].a<<","<<tree[st[first].root].b<<"]\n";if (tree[st[first].root].a!=tree[st[first].root].b){st[top].root=st[first].root*2+1;st[top++].level=st[first].level+1;st[top].root=st[first].root*2+2;st[top++].level=st[first].level+1;}first++;}}
int main(){int t,i;cout<<"以[1,9]线段树为例，生成一个二叉树。\n\n";buildtree(1,9);cout<<"以深度遍历该树（深搜）：\n";dfs(1);cout<<"以深度遍历该树（宽搜）：\n";bfs();system("pause");return 0;}

热心网友时间：2022-04-13 15:40

算法非常奇特

热心网友时间：2022-04-13 17:15

数据结构