一張二叉樹的圖

?1，二叉樹的特點

1. 每個點p的左兒子是p*2,右兒子是p*2+1，可以分別表示為p<<1與p<<1|1
2. 節(jié)點的序號是從左到右，從上到下增加的
3. 每個點至多2個兒子（屁話（bushi））

2，先序遍歷(根左右）

就是每次到子樹的根節(jié)點，先存入這個節(jié)點，然后優(yōu)先訪問左兒子，左兒子訪問到回來，再訪問右兒子（不是親生的（que ren））

?順序1->2->4->5(正在回家的路上）->3->6

int t[N];//t表示樹上節(jié)點
int cnt;
void build(int p)
{cout<<t[p];//每次存儲根節(jié)點后進(jìn)入左兒子build(p<<1);build(p<<1|1);//左兒子出來后再進(jìn)入右兒子
}

3，中序遍歷（左根右）

每次到子樹的根節(jié)點，先進(jìn)入左兒子，回來后在訪問根，最后再訪問右兒子

?順序4->2->5->1->6->3

int t[N];//t表示樹上節(jié)點
int cnt;
void build(int p)
{build(p<<1);//每次x先進(jìn)入左兒子，出來后再存儲根節(jié)點cout<<t[p];build(p<<1|1);//根節(jié)點存儲后后再進(jìn)入右兒子
}

4，后序遍歷（左右根）

依次訪問左右兒子，再回來訪問根節(jié)點

順序是4->5->2->3->6->1

int t[N];//t表示樹上節(jié)點
int cnt;
void build(int p)
{build(p<<1);//每次x先進(jìn)入左兒子build(p<<1|1);//再進(jìn)入右兒子cout<<t[p];//最后存儲根節(jié)點
}

5，層序遍歷

就是一層一層訪問，這次不再是遍歷了，我們觀察序號，其實

t[1]~t[n]就是點1~n的層序遍歷

int t[N];//t表示樹上節(jié)點
int cnt;
for (int i=1; i<=n; ++i)cout<<t[i]<<endl;

?