數據結構（六）二叉樹的遍歷（遞歸非遞歸方法）

一、遞歸方法

1.先序遍歷

void PreOrder(BiTree T)
{visit(T);PreOrder(T->LChild)PreOrder(T->RChild)
}

2.先序遍歷

void PreOrder(BiTree T)
{PreOrder(T->LChild)visit(T);PreOrder(T->RChild)
}

3.先序遍歷

void PreOrder(BiTree T)
{PreOrder(T->LChild)PreOrder(T->RChild)visit(T);
}

二、非遞歸方法

非遞歸的方法我們主要采用棧的方法，先進后出

1.中序遍歷

void MidSearch01(BiTree T)
{stack<BitTNode*> p;while (T || !p.empty()){if (T){p.push(T);T = T->lchild;}else{T = p.top();cout << T->data << "\t";p.pop();T = T->rchild;}}}

2.先序遍歷

//前序遍歷（非遞歸）void PreSearch01(BiTree T)
{stack<BitTNode*> p;while (T || !p.empty()){if (T){cout << T->data << "\t";p.push(T);T = T->lchild;}else{T= p.top();p.pop();T = T->rchild;}}
}

3.后序遍歷

后序遍歷相對于前中序遍歷要麻煩一些

BitTNode* r = NULL;//標記位置
//后序遍歷（非遞歸）
void PostSearch01(BiTree T)
{stack<BitTNode*> p;while (T || !p.empty()){if (T){p.push(T);T = T->lchild;}else{T = p.top();if (T->rchild && T->rchild != r){T = T->rchild;p.push(T);T = T->lchild;}else{p.pop();cout << T->data << "\t";r = T;T = NULL;}}}}

4.層次遍歷

//層次遍歷
void LevelOrder(BiTree T)
{queue<BitTNode*> q;q.push(T);while (!q.empty()){T = q.front();q.pop();cout << T->data << "\t";if (T->lchild != NULL){q.push(T->lchild);}if (T->rchild != NULL){q.push(T->rchild);}}}