Question

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

设计要求：任意选定一棵至少含有8个结点的二叉树，编程实现：（1）按层次遍历算法遍历该二叉树，并给出遍历结果；（2）利用层次遍历算法显示所有叶结点。

Answer 1

#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;}

Answer 2

算法非常奇特

Answer 3

数据结构