二叉樹(shù)層次建樹(shù)

對(duì)于二叉樹(shù)，建樹(shù)過(guò)程中需要一個(gè)（尾插法的）鏈表（或隊(duì)列）來(lái)輔助確認(rèn)當(dāng)前父親節(jié)點(diǎn)

由于尾插法需要一個(gè)尾指針。因此可以理解為隊(duì)列，只不過(guò)是不帶頭結(jié)點(diǎn)的鏈表版隊(duì)列。

但其實(shí)就是一個(gè)輔助找到當(dāng)前父親節(jié)點(diǎn)的作用，不必糾結(jié)是啥名字。

代碼如下：

#include<stdio.h>
#include<stdlib.h>
typedef char ElemType;
//樹(shù)結(jié)構(gòu)體
typedef struct tree_node{ElemType val;struct tree_node*lc;struct tree_node*rc;
}Tnode,*BTree;//鏈表
typedef struct link{BTree tree;//存儲(chǔ)的是樹(shù)的節(jié)點(diǎn)struct link*next;
}LinkNode,*LinkList;void build_tree(BTree&tree,LinkList&front,LinkList& rear)
{//還需要一個(gè)指向當(dāng)前父親節(jié)點(diǎn)的指針LinkList cur = NULL;ElemType data;while(scanf("%c",&data) && data != '\n'){//每次來(lái)一個(gè)新建一個(gè)樹(shù)的節(jié)點(diǎn)和鏈表的節(jié)點(diǎn)BTree newTree = (BTree)calloc(1,sizeof(Tnode));LinkList newList = (LinkList)calloc(1,sizeof(LinkNode));newTree->val = data;newList->tree=newTree;//進(jìn)行判讀是不是父親節(jié)點(diǎn)if(tree == NULL){tree = newTree;//入隊(duì)front = rear = newList;cur=rear;}else{if(cur->tree->lc == NULL){//插入左子樹(shù)cur->tree->lc=newTree;//入隊(duì)并更新尾指針rear->next=newList;rear = rear->next;}else{cur->tree->rc = newTree;//入隊(duì)并更新尾指針rear->next=newList;rear = rear->next;//注意這里左右子樹(shù)都滿(mǎn)了，當(dāng)前父親節(jié)點(diǎn)要換cur= cur->next;}}}
}//前序便利
void pre_print(BTree tree)
{if(tree){putchar(tree->val);pre_print(tree->lc);pre_print(tree->rc);}
}
void mid_print(BTree tree)
{if(tree){//左跟右mid_print(tree->lc);putchar(tree->val);mid_print(tree->rc);}
}
void post_print(BTree tree)
{if(tree){//左右跟post_print(tree->lc);post_print(tree->rc);putchar(tree->val);}
}
int main()
{BTree tree = NULL;//樹(shù)根LinkList front=NULL;LinkList rear=NULL;//需要用到尾插法build_tree(tree,front,rear);pre_print(tree);puts("");mid_print(tree);puts("");post_print(tree);return 0;
}

前序便利：根左右--->先打印自身再左子樹(shù)再右子樹(shù)

//前序便利
void pre_print(BTree tree)
{if(tree){putchar(tree->val);pre_print(tree->lc);pre_print(tree->rc);}
}

中序遍歷：左根右--->先打印左子樹(shù)再打印自身再右子樹(shù)

void mid_print(BTree tree)
{if(tree){//左跟右mid_print(tree->lc);putchar(tree->val);mid_print(tree->rc);}
}

后序遍歷：左右根--->先打印左子樹(shù)再右子樹(shù)再自身

void post_print(BTree tree)
{if(tree){//左右跟post_print(tree->lc);post_print(tree->rc);putchar(tree->val);}
}

【注意】以上三中便利采用遞歸思想。?

代碼運(yùn)行結(jié)果如下

封裝思想展示，隊(duì)列封裝

#include<stdio.h>
#include<stdlib.h>
typedef char ElemType;//樹(shù)
typedef struct trees{ElemType data;struct trees*lc;struct trees*rc;
}treeNode,*Tree;//鏈表
typedef struct Links{Tree tree;struct Links*next;
}LNode,*LinkList;//隊(duì)列
typedef struct{LinkList front;LinkList rear;
}LinkQue;void init_que(LinkQue&q)
{q.front=q.rear=(LinkList)calloc(1,sizeof(LNode));q.front=q.rear;
}bool isEmpty(LinkQue&q)
{return q.front == q.rear;
}//入隊(duì)
void push_que(LinkQue&q,Tree tree)
{//新建鏈表節(jié)點(diǎn)LinkList newList = (LinkList)calloc(1,sizeof(LNode));newList->next=NULL;newList->tree=tree;q.rear->next=newList;q.rear=q.rear->next;
}
bool pop_que(LinkQue&q,Tree &tree)
{if(isEmpty(q)){return false;}LinkList del = q.front->next;//頭結(jié)點(diǎn)不存數(shù)據(jù)，第一個(gè)節(jié)點(diǎn)才是真的數(shù)據(jù)起始位置q.front->next=del->next;//斷鏈tree=del->tree;if(q.rear == del)//只剩下尾節(jié)點(diǎn)的數(shù)據(jù){q.rear=q.front;//置空}free(del);return true;
}void build_tree(Tree&tree)
{LinkQue q;init_que(q);LinkList cur = NULL;ElemType data;while(scanf("%c",&data) && data != '\n'){Tree newTree = (Tree)calloc(1,sizeof(treeNode));//申請(qǐng)新的樹(shù)的節(jié)點(diǎn)newTree->data=data;if(tree == NULL){tree = newTree;push_que(q,tree);//入隊(duì)cur = q.rear;}else{if(cur->tree->lc == NULL){cur->tree->lc = newTree;push_que(q,newTree);}else{cur->tree->rc = newTree;push_que(q,newTree);//改變當(dāng)前父親節(jié)點(diǎn)cur = cur->next;}}}
}void pre_print(Tree t)
{if(t){putchar(t->data);pre_print(t->lc);pre_print(t->rc);}
}
void mid_print(Tree t)
{if(t){mid_print(t->lc);putchar(t->data);mid_print(t->rc);}
}
void post_print(Tree t)
{if(t){post_print(t->lc);post_print(t->rc);putchar(t->data);}
}int main()
{Tree tree = NULL;build_tree(tree);// pre_print(tree);return 0;
}

層次遍歷在下節(jié)