二叉樹(shù)的非遞歸遍歷算法
二叉樹(shù)的遍歷是指訪(fǎng)問(wèn)二叉樹(shù)的每個(gè)結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)僅被訪(fǎng)問(wèn)一次。二叉樹(shù)的遍歷可按二叉樹(shù)的構(gòu)成以及訪(fǎng)問(wèn)結(jié)點(diǎn)的順序分為4種方式：先序遍歷、中序遍歷、后序遍歷和層次遍歷。請(qǐng)至少給出其中一種遍歷方式的非遞歸算法的思路和代碼，并舉例演示算法的執(zhí)行過(guò)程。
先序遍歷
算法思路:采用棧來(lái)實(shí)現(xiàn)先序遍歷的非遞歸算法。創(chuàng)建棧，并初始化。遍歷結(jié)點(diǎn)，若結(jié)點(diǎn)存在，則入棧，并輸出結(jié)點(diǎn)的值，指向其左孩子；否則出棧，訪(fǎng)問(wèn)結(jié)點(diǎn)，指向其右孩子。如果結(jié)點(diǎn)不存在或者棧為空，則遍歷結(jié)束。
代碼：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-424021.html
//先序遍歷二叉樹(shù)
void PreOrder(BiTree T)
{
SqStack* S;
S = InitStack();
BiTreeNode* p;
p = T;
while (p|| !StackEmpty(*S))
{
if (p)
{
printf("%c",p->data);
Push(S, p);
p = p->LChild;
}
else
{
Pop(S, &p);
p = p->RChild;
}
}
}
演示過(guò)程（以先序遍歷輸入ABD##E##CF###為例）
- 根節(jié)點(diǎn)A入棧，并打印該結(jié)點(diǎn)的值，P指向其左孩子
此時(shí)輸出:A
- 繼續(xù)遍歷結(jié)點(diǎn)，此時(shí)B結(jié)點(diǎn)存在并打印該結(jié)點(diǎn)的值，則將該結(jié)點(diǎn)入棧，P指向B結(jié)點(diǎn)的左孩子
此時(shí)輸出：AB
- 繼續(xù)遍歷結(jié)點(diǎn)，此時(shí)D結(jié)點(diǎn)存在并打印該結(jié)點(diǎn)的值，則將該結(jié)點(diǎn)入棧，P指向D結(jié)點(diǎn)的左孩子
此時(shí)輸出：ABD
- 繼續(xù)遍歷結(jié)點(diǎn)，此時(shí)D結(jié)點(diǎn)的左孩子不存在，則將棧頂元素出棧，P指向D結(jié)點(diǎn)的右孩子
此時(shí)輸出：ABD（不變）
- 繼續(xù)遍歷結(jié)點(diǎn)，此時(shí)D結(jié)點(diǎn)的右孩子不存在，則將棧頂元素出棧，P指向B結(jié)點(diǎn)的右孩子
此時(shí)輸出：ABD（不變）
- 繼續(xù)遍歷結(jié)點(diǎn)，此時(shí)E結(jié)點(diǎn)存在并打印該結(jié)點(diǎn)的值，則將該結(jié)點(diǎn)入棧，P指向E結(jié)點(diǎn)的左孩子
此時(shí)輸出：ABDE
- 繼續(xù)遍歷結(jié)點(diǎn)，此時(shí)E結(jié)點(diǎn)的左孩子為空，則將棧頂元素出棧，P指向E結(jié)點(diǎn)的右孩子
此時(shí)輸出：ABDE（不變）
- 繼續(xù)遍歷結(jié)點(diǎn)，此時(shí)E結(jié)點(diǎn)的右孩子為空，則將棧頂元素出棧，P指向A結(jié)點(diǎn)的右孩子
此時(shí)輸出：ABDE（不變）
- 繼續(xù)遍歷結(jié)點(diǎn)，此時(shí)C結(jié)點(diǎn)存在并打印該結(jié)點(diǎn)的值，則將該結(jié)點(diǎn)入棧，P指向C結(jié)點(diǎn)的左孩子
此時(shí)輸出：ABDEC
- 繼續(xù)遍歷結(jié)點(diǎn)，此時(shí)F結(jié)點(diǎn)存在并打印該結(jié)點(diǎn)的值，則將該結(jié)點(diǎn)入棧，P指向F結(jié)點(diǎn)的左孩子
此時(shí)輸出：ABDECF
- 繼續(xù)遍歷結(jié)點(diǎn)，此時(shí)F結(jié)點(diǎn)的左孩子為空，則將棧頂元素F出棧，P指向F結(jié)點(diǎn)的右孩子
此時(shí)F結(jié)點(diǎn)的右孩子也為空，繼續(xù)將棧頂元素C出棧，P指向C結(jié)點(diǎn)的右孩子，此時(shí)P指向的結(jié)點(diǎn)為空，棧也為空，遍歷結(jié)束。
中序遍歷
算法思路：同樣也是用棧，與先序遍歷相同，只是輸出在不同位置。創(chuàng)建棧，并初始化。遍歷結(jié)點(diǎn)，若結(jié)點(diǎn)存在，則入棧，指向其左孩子；否則出棧，訪(fǎng)問(wèn)結(jié)點(diǎn)，并輸出結(jié)點(diǎn)的值，指向其右孩子。如果結(jié)點(diǎn)不存在或者棧為空，則遍歷結(jié)束
代碼：
//中序遍歷二叉樹(shù)
void InOrder(BiTree T)
{
SqStack* S;
S = InitStack();
BiTreeNode* p;
p = T;
while (p || !StackEmpty(*S))
{
if (p)
{
Push(S, p);
p = p->LChild;
}
else
{
Pop(S, &p);
printf("%c", p->data);
p = p->RChild;
}
}
}
后序遍歷
算法思路：由于后序遍歷是后序遍歷根節(jié)點(diǎn)的左子樹(shù)，后序遍歷根節(jié)點(diǎn)的右子樹(shù)，最后訪(fǎng)問(wèn)根節(jié)點(diǎn)，那么最大問(wèn)題就是判斷是否該結(jié)點(diǎn)結(jié)束遍歷左子樹(shù)，所以采取以下操作來(lái)解決。同樣也使用一個(gè)棧，初始化棧，遍歷結(jié)點(diǎn)，若結(jié)點(diǎn)存在，結(jié)點(diǎn)入棧，并對(duì)該結(jié)點(diǎn)標(biāo)志位0，表示該結(jié)點(diǎn)尚未被遍歷其左子樹(shù)，然后指向其右結(jié)點(diǎn)；若結(jié)點(diǎn)不存在，滿(mǎn)足該結(jié)點(diǎn)的左子樹(shù)已被遍歷進(jìn)入循環(huán)，遍歷該結(jié)點(diǎn)的右子樹(shù)。不滿(mǎn)足退出循環(huán)，然后繼續(xù)出棧得到子結(jié)點(diǎn)，并將其壓入棧，指向子節(jié)點(diǎn)的右孩子，并對(duì)該結(jié)點(diǎn)標(biāo)志為1。
代碼：
//后序遍歷
void Postorder(BiTree T)
{
SqStack* S;
S = InitStack();
BiTreeNode* p;
p = T;
char tag[Maxsize] = {'0'};
while (p || !StackEmpty(*S))
{
if (p)
{
Push(S, p);
tag[S->top] = '0';//標(biāo)志結(jié)點(diǎn)是否遍歷右子樹(shù)
p = p->LChild;
}
else
{
while (tag[S->top] == '1') {
Pop(S, &p);
printf("%c",p->data);
}
if (S->top == -1) break;
Pop(S, &p);
Push(S, p);
p = p->RChild;
tag[S->top] = '1';
}
}
}
層次遍歷
算法思路：采用順序隊(duì)列來(lái)實(shí)現(xiàn)，將根節(jié)點(diǎn)入隊(duì)，進(jìn)入循環(huán)，將隊(duì)頭指針?biāo)傅脑爻鲫?duì)，并輸出其結(jié)點(diǎn)的值，如果該結(jié)點(diǎn)的左孩子存在，將其左孩子入隊(duì)，如果該結(jié)點(diǎn)的右孩子存在，將右孩子入隊(duì)，直到隊(duì)頭指針和隊(duì)尾指針相等退出循環(huán)。
代碼：
//層次遍歷
void Levelorder(BiTree T)
{
BiTree Q[Maxsize];
int front, rear;
if (T == NULL)return;
front = -1;
rear = 0;
Q[rear] = T;
while (front != rear)
{
front++;
printf("%c",Q[front]->data);
if (Q[front]->LChild != NULL)
{
rear++;
Q[rear] = Q[front]->LChild;
}
if (Q[front]->RChild != NULL)
{
rear++;
Q[rear] = Q[front]->RChild;
}
}
}
代碼匯總
//非遞歸先序遍歷、中序遍歷、后序遍歷可用棧來(lái)實(shí)現(xiàn)
//層次遍歷可用隊(duì)列來(lái)實(shí)現(xiàn)
//作者:Second to none
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<Windows.h>
#include<math.h>
#define Maxsize 30
typedef char ElemType;
void gotoxy(int x, int y)
{
COORD c;
c.X = x - 1;
c.Y = y - 1;
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), c);
}
typedef struct BiTreeNode
{
ElemType data;
struct BiTreeNode* LChild, * RChild;
}*BiTree;
typedef struct SqStack
{
BiTree data[Maxsize];
int top;
}*Stack;
//創(chuàng)建棧
Stack InitStack()
{
Stack S;
S = (Stack)malloc(sizeof(SqStack));
S->top = -1;
return S;
}
//棧空
int StackEmpty(SqStack S)
{
if (S.top == -1)return 1;
else return 0;
}
//入棧
void Push (Stack S,BiTree p)
{
S->top++;
S->data[S->top] = p;
}
//出棧
void Pop(Stack S, BiTree* p)
{
*p = S->data[S->top];
S->top--;
}
BiTree CreateBiTree()
{
char ch;
BiTree T;
scanf_s("%c",&ch,1);
if (ch == '#')T = NULL;
else {
T = (BiTree)malloc(sizeof(BiTreeNode));
T->data = ch;
T->LChild = CreateBiTree();
T->RChild = CreateBiTree();
}
return T;
}
//先序遍歷二叉樹(shù)
void PreOrder(BiTree T)
{
SqStack* S;
S = InitStack();
BiTreeNode* p;
p = T;
while (p|| !StackEmpty(*S))
{
if (p)
{
printf("%c",p->data);
Push(S, p);
p = p->LChild;
}
else
{
Pop(S, &p);
p = p->RChild;
}
}
}
//中序遍歷二叉樹(shù)
void InOrder(BiTree T)
{
SqStack* S;
S = InitStack();
BiTreeNode* p;
p = T;
while (p || !StackEmpty(*S))
{
if (p)
{
Push(S, p);
p = p->LChild;
}
else
{
Pop(S, &p);
printf("%c", p->data);
p = p->RChild;
}
}
}
//后序遍歷
void Postorder(BiTree T)
{
SqStack* S;
S = InitStack();
BiTreeNode* p;
p = T;
char tag[Maxsize] = {'0'};
while (p || !StackEmpty(*S))
{
if (p)
{
Push(S, p);
tag[S->top] = '0';//標(biāo)志結(jié)點(diǎn)是否遍歷右子樹(shù)
p = p->LChild;
}
else
{
while (tag[S->top] == '1') {
Pop(S, &p);
printf("%c",p->data);
}
if (S->top == -1) break;
Pop(S, &p);
Push(S, p);
p = p->RChild;
tag[S->top] = '1';
}
}
}
//層次遍歷
void Levelorder(BiTree T)
{
BiTree Q[Maxsize];
int front, rear;
if (T == NULL)return;
front = -1;
rear = 0;
Q[rear] = T;
while (front != rear)
{
front++;
printf("%c",Q[front]->data);
if (Q[front]->LChild != NULL)
{
rear++;
Q[rear] = Q[front]->LChild;
}
if (Q[front]->RChild != NULL)
{
rear++;
Q[rear] = Q[front]->RChild;
}
}
}
int GetHightOfTree(BiTree T)
{
int rh = 0, lh = 0;
if (!T)return 0;
else
{
lh = GetHightOfTree(T->LChild);
rh = GetHightOfTree(T->RChild);
return(lh > rh ? lh : rh) + 1;
}
}
void DisplayBinTree(BiTree T, int col, int row, int h)
{
if (T)
{
gotoxy(col, row);
printf("%c", T->data);
DisplayBinTree(T->LChild, col - h, row + 1, h / 2);
DisplayBinTree(T->RChild, col + h, row + 1, h / 2);
}
}
void DisplayTree(BiTree T)
{
int k = 0;
k = GetHightOfTree(T);
DisplayBinTree(T, (int)pow(2, k - 1) * 2 + 1, 4, (int)pow(2, k - 1));
printf("\n\n\n");
}
int main()
{
BiTree T;
printf("請(qǐng)采用先序遍歷輸入:\n");
T = CreateBiTree();
printf("輸出二叉樹(shù)的樹(shù)形結(jié)構(gòu)");
DisplayTree(T);
printf("\n先序遍歷輸出\n");
PreOrder(T);
printf("\n中序遍歷輸出\n");
InOrder(T);
printf("\n后序遍歷輸出\n");
Postorder(T);
printf("\n層次遍歷輸出\n");
Levelorder(T);
return 1;
}
運(yùn)行截圖
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-424021.html
到了這里，關(guān)于二叉樹(shù)的非遞歸遍歷算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
