有圖有真相
y
最近在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)策肝，前面學(xué)的都還還好結(jié)構(gòu)也比較簡(jiǎn)單，學(xué)到二叉樹時(shí)，思維量明顯提高之众。為了更好的更清晰的研究二叉樹拙毫，自己決定寫個(gè)打印二叉樹圖像的算法。
總體思想是利用層次遍歷棺禾，每遍歷到一個(gè)元素就將它打印出來缀蹄，這樣就能從頭到尾打印出一顆二叉樹。其中難點(diǎn)主要是隨著二叉樹的深度增加帘睦，每個(gè)元素間的間距也是在增大的。為了找這個(gè)規(guī)律坦康，我在excel里做了一個(gè)巨大的二叉樹竣付，一個(gè)格子一個(gè)格子數(shù)每行的間距，然后總結(jié)出來的通式滞欠。
主要代碼如下
//打印每個(gè)元素
void PrintTreeNode(char c,int h,int index){
//基礎(chǔ)空格
int blank = 3;
//用于標(biāo)記是否為每行第一個(gè)元素
bool flag = false;
//確定元素所在行
int line = 1;
for(;line<=h;line++){
if(index<=pow(2,line-1)){
if(index == pow(2, line-1)){
flag = true;
}else{
line--;
}
break;
}
}
//每個(gè)字母的空格倍數(shù)
int itemblank = blank;
for(int i=1;i<h-line+1;i++){
itemblank = itemblank*2+1;
}
//每行開頭字母的空格倍數(shù)
int headblank = (itemblank-1)/2-1;
if(flag){
//新的一行的回車數(shù)
int changelinenum = (itemblank-1)/4;
if(changelinenum < 1){
changelinenum = 1;
}
if(line == 1){
changelinenum = 1;
}
//先回車換行
for(int j=0;j<changelinenum;j++){
printf("\n");
}
//在打印空格到正確的位置
for(int i=0;i<headblank;i++){
printf(" ");
}
//最后打印每行的第一個(gè)元素
printf("%c",c);
}else{
//先打印空格到正確的位置
for(int i=0;i<itemblank;i++){
printf(" ");
}
//打印元素
printf("%c",c);
}
}
//h為二叉樹的高度
void PrintTree(BiTree T,int h){
printf("\n");
//二叉樹元素序號(hào)
int index = 0;
LinkQueue Q;
InitQueue(&Q);
//第一個(gè)元素先入隊(duì)
EnQueue(&Q, T);
//總數(shù)大于滿二叉樹最大值則退出循環(huán)
while(index < pow(2,h)-1){
BiTNode *node = DeQueue(&Q);
index++;
//將空的子樹也入隊(duì)古胆，這樣方便計(jì)算
if(node == NULL){
EnQueue(&Q, NULL);
EnQueue(&Q, NULL);
//打印第index個(gè)元素
PrintTreeNode(' ',h,index);
}else{
EnQueue(&Q, node->lChild);
EnQueue(&Q, node->rChild);
//打印第index個(gè)元素
PrintTreeNode(node->data,h,index);
}
}
printf("\n");
}
希望對(duì)大家有幫助