二叉树的遍历总结
二叉樹的遍歷總結(jié)
文章目錄
- 二叉樹的遍歷總結(jié)
- 二叉樹結(jié)構(gòu)
- 建立二叉樹
- 層次遍歷
- 遞歸的三種遍歷
- 非遞歸的三種遍歷
- 完整代碼
二叉樹結(jié)構(gòu)
用二叉鏈表來存儲(chǔ)二叉樹
typedef struct BiTNode //二叉樹 {int data; //結(jié)點(diǎn)數(shù)值struct BiTNode *lchild;struct BiTNode *rchild; }BiTNode, *BiTree;建立二叉樹
輸入一個(gè)數(shù)組，以層次遍歷的順序進(jìn)行建樹，規(guī)定數(shù)組元素都大于0。當(dāng)數(shù)組元素為-1時(shí)，表示該結(jié)點(diǎn)為空。
舉個(gè)例子，比如數(shù)組大小為 12，數(shù)組元素為
3 5 6 8 -1 2 7 8 1 34 -1 65則建立的二叉樹為
建立二叉樹的代碼：
queue<BiTree> q;//輔助隊(duì)列void createBiTree() {int n;int a[1010];//讀取輸入scanf("%d", &n);for (int i = 1; i <= n; i++){scanf("%d", &a[i]);}//建立二叉樹int counts = 1;for (int i = 1; i <= n; i++){BiTree tmp = (BiTree)malloc(sizeof(BiTNode));tmp = q.front();q.pop();tmp->data = a[i];//賦值tmp->lchild = (BiTree)malloc(sizeof(BiTNode));tmp->rchild = (BiTree)malloc(sizeof(BiTNode));if(a[i] != -1){tmp->num = counts;//給非空結(jié)點(diǎn)編號(hào)counts++;q.push(tmp->lchild);//后面的元素必須掛在非空結(jié)點(diǎn)下面q.push(tmp->rchild);}else //空結(jié)點(diǎn)標(biāo)記{tmp->lchild->data = -1;tmp->rchild->data = -1;}}while(!q.empty())//清除隊(duì)列中的空結(jié)點(diǎn){q.front()->data = -1;q.pop();} }層次遍歷
訪問結(jié)點(diǎn)
- 如果該結(jié)點(diǎn)不為空，輸出該結(jié)點(diǎn)的值
層次遍歷
- 先把二叉樹的根結(jié)點(diǎn)入隊(duì)。然后隊(duì)首元素出隊(duì)，訪問出隊(duì)結(jié)點(diǎn)。若它有左子樹，則將左子樹根結(jié)點(diǎn)入隊(duì)；若它有右子樹，右子樹根結(jié)點(diǎn)入隊(duì)。然后繼續(xù)出隊(duì)，訪問出隊(duì)結(jié)點(diǎn)······重復(fù)這個(gè)過程，直到隊(duì)列為空
遞歸的三種遍歷
先序遍歷，也叫前序遍歷
- 訪問根結(jié)點(diǎn)
- 先序遍歷左子樹
- 先序遍歷右子樹
中序遍歷
- 中序遍歷左子樹
- 訪問根結(jié)點(diǎn)
- 中序遍歷右子樹
后序遍歷
- 后序遍歷左子樹
- 后序遍歷右子樹
- 訪問根結(jié)點(diǎn)
非遞歸的三種遍歷
中序遍歷
先序遍歷和中序遍歷很相似，區(qū)別在于掃描結(jié)點(diǎn)時(shí)先訪問結(jié)點(diǎn)，再將其入棧
void PreOrder2(BiTree T) {stack<BiTree> s;BiTree p = T;while((p->data != -1) || (!s.empty()))//p不空或者棧不空{if(p->data != -1) //結(jié)點(diǎn)非空{visit(p); //先訪問結(jié)點(diǎn)，再入棧s.push(p);p = p->lchild;}else{p = s.top(); //出棧，轉(zhuǎn)向出棧結(jié)點(diǎn)的右子樹s.pop();p = p->rchild;}} }后序遍歷
初始時(shí)依次掃描根結(jié)點(diǎn)的所有左側(cè)結(jié)點(diǎn)并將它們?nèi)恳来芜M(jìn)棧
讀棧頂元素，若其右孩子不為空且未被訪問過，將右子樹轉(zhuǎn)向 1
否則，棧頂元素出棧并訪問
注意：
在第二步中，需要分清返回時(shí)是從左子樹返回的還是右子樹返回的，設(shè)置一個(gè)輔助指針 r，指向最近訪問過的結(jié)點(diǎn)。
每次出棧訪問完一個(gè)結(jié)點(diǎn)就相當(dāng)于遍歷完以該結(jié)點(diǎn)為根的子樹，需要將 p 置空。
void PostOrder2(BiTree T) {stack<BiTree> s;BiTree p = T;BiTree r = NULL; //r指針記錄最后一個(gè)訪問的結(jié)點(diǎn)BiTree kong = (BiTree)malloc(sizeof(BiTNode));//空指針，方便p置空kong->data = -1;while((p->data != -1) || (!s.empty()))//p不空或棧不空{if(p->data != -1) //非空結(jié)點(diǎn){s.push(p); //入棧，一路向左p = p->lchild;}else{p = s.top(); //訪問棧頂元素（不出棧）if((p->rchild->data != -1) && (p->rchild != r))//右子樹存在且未被訪問過{p = p->rchild; //轉(zhuǎn)向右子樹s.push(p);p = p->lchild; //仍然一路向左}else //否則，彈出棧頂元素并訪問{s.pop(); visit(p);r = p; //記錄最近訪問過的結(jié)點(diǎn)p = kong; //結(jié)點(diǎn)訪問完后，p置空}}} }完整代碼
#include <cstdio> #include <cstdlib> #include <queue> #include <stack> using namespace std;typedef struct BiTNode //二叉樹 {int data; //結(jié)點(diǎn)數(shù)值struct BiTNode *lchild;struct BiTNode *rchild; }BiTNode, *BiTree; queue<BiTree> q;//輔助隊(duì)列void createBiTree(); //層次序列建立二叉樹 void visit(BiTree R); //訪問結(jié)點(diǎn)void LevelOrder(BiTree R); //層次遍歷/* 遞歸的先序、中序、后序遍歷 */ void PreOrder(BiTree R); void InOrder(BiTree R); void PostOrder(BiTree R); /* 非遞歸的先序、中序、后序遍歷 */ void PreOrder2(BiTree R); void InOrder2(BiTree R); void PostOrder2(BiTree R); int main() {BiTree bit;bit = (BiTree)malloc(sizeof(BiTNode));q.push(bit);createBiTree();//層次遍歷printf("\n層次遍歷： ");LevelOrder(bit);printf("\n\n");/* 遞歸 */printf("遞歸\n");printf("先序遍歷： ");PreOrder(bit);printf("\n");printf("中序遍歷： ");InOrder(bit);printf("\n");printf("后序遍歷： ");PostOrder(bit);printf("\n\n");/* 非遞歸 */printf("非遞歸\n");printf("先序遍歷： ");PreOrder2(bit);printf("\n");printf("中序遍歷： ");InOrder2(bit);printf("\n");printf("后序遍歷： ");PostOrder2(bit);printf("\n");return 0; }void createBiTree() {int n;int a[1010];//讀取輸入scanf("%d", &n);for (int i = 1; i <= n; i++){scanf("%d", &a[i]);}//建立二叉樹for (int i = 1; i <= n; i++){BiTree tmp = (BiTree)malloc(sizeof(BiTNode));tmp = q.front();q.pop();tmp->data = a[i];//賦值tmp->lchild = (BiTree)malloc(sizeof(BiTNode));tmp->rchild = (BiTree)malloc(sizeof(BiTNode));if(a[i] != -1){q.push(tmp->lchild);//后面的元素必須掛在非空結(jié)點(diǎn)下面q.push(tmp->rchild);}else //空結(jié)點(diǎn)標(biāo)記{tmp->lchild->data = -1;tmp->rchild->data = -1;}}while(!q.empty())//清除隊(duì)列中的空結(jié)點(diǎn){q.front()->data = -1;q.pop();} } void visit(BiTree T) {if(T->data != -1)printf("%d ", T->data); } void LevelOrder(BiTree T) {while(!q.empty())//初始化隊(duì)列{q.pop();}q.push(T);//根結(jié)點(diǎn)入隊(duì)while(!q.empty()){BiTree tmp = q.front();q.pop();//隊(duì)頭結(jié)點(diǎn)出隊(duì)visit(tmp);//訪問出隊(duì)結(jié)點(diǎn)if(tmp->lchild->data != -1)q.push(tmp->lchild);if(tmp->rchild->data != -1)q.push(tmp->rchild);} } void PreOrder(BiTree T) {if(T->data != -1)//結(jié)點(diǎn)非空{visit(T);PreOrder(T->lchild);PreOrder(T->rchild);} } void InOrder(BiTree T) {if(T->data != -1)//結(jié)點(diǎn)非空{InOrder(T->lchild);visit(T);InOrder(T->rchild);} } void PostOrder(BiTree T) {if(T->data != -1)//結(jié)點(diǎn)非空{PostOrder(T->lchild);PostOrder(T->rchild);visit(T);} } void PreOrder2(BiTree T) {stack<BiTree> s;BiTree p = T;while((p->data != -1) || (!s.empty()))//p不空或者棧不空{if(p->data != -1) //結(jié)點(diǎn)非空{visit(p); //先訪問結(jié)點(diǎn)，再入棧s.push(p);p = p->lchild;}else{p = s.top(); //出棧，轉(zhuǎn)向出棧結(jié)點(diǎn)的右子樹s.pop();p = p->rchild;}} } void InOrder2(BiTree T) {stack<BiTree> s;BiTree p = T;while((p->data != -1) || (!s.empty()))//p不空或棧不空{if(p->data != -1) //非空結(jié)點(diǎn){s.push(p); //入棧，一路向左p = p->lchild; }else //出棧，轉(zhuǎn)向出棧結(jié)點(diǎn)的右子樹{p = s.top();s.pop();visit(p);p = p->rchild;}} } void PostOrder2(BiTree T) {stack<BiTree> s;BiTree p = T;BiTree r = NULL; //r指針記錄最后一個(gè)訪問的結(jié)點(diǎn)BiTree kong = (BiTree)malloc(sizeof(BiTNode));//空指針，方便p置空kong->data = -1;while((p->data != -1) || (!s.empty()))//p不空或棧不空{if(p->data != -1) //非空結(jié)點(diǎn){s.push(p); //入棧，一路向左p = p->lchild;}else{p = s.top(); //訪問棧頂元素（不出棧）if((p->rchild->data != -1) && (p->rchild != r))//右子樹存在且未被訪問過{p = p->rchild; //轉(zhuǎn)向右子樹s.push(p);p = p->lchild; //仍然一路向左}else //否則，彈出棧頂元素并訪問{s.pop(); visit(p);r = p; //記錄最近訪問過的結(jié)點(diǎn)p = kong; //結(jié)點(diǎn)訪問完后，p置空}}} }程序運(yùn)行結(jié)果如下：
總結(jié)
