二叉樹的非遞回遍歷
- 前言
- 例子
- 前序遍歷（堆疊實作）
- 中序遍歷（堆疊實作）
- 后序遍歷（堆疊實作）
- 層次遍歷（佇列實作）
| 目錄 | 目錄 |
|---|---|
| 順序表 | 單鏈表（不帶附加頭結點） |
| 雙鏈表（帶附加頭結點） | 堆疊（順序表實作） |
| 佇列（鏈式，不帶附加頭結點） | 二叉樹 |
| 二叉樹的非遞回遍歷 |
前言
通常，對于二叉樹的實作，面試官并不會去問你遞回怎么實作，看了我前面寫的二叉樹，你就知道遞回寫起來比較簡單，
對于二叉樹，面試官一般會問你非遞回演算法是怎么實作的，因為非遞回演算法需要用到堆疊、佇列，所以問起來比較有意義，可以聯系一系列知識，
ps：不知道堆疊、佇列的同學先去看看我寫的文章哦！
例子
為了使大家更加明白，這里樹簡化了許多結點，只有五個結點，ABCDE
前序：ABDCE（根左右）
中序：BDAEC（左根右）
后序：DBECA（左右根）
前序遍歷（堆疊實作）
- 首先訪問根結點，每次訪問一個結點后，在向左子樹繼續遍歷之前，先用堆疊記錄該結點的右孩子，這樣可以在左子樹退回時，取得根結點的地址，在繼續右子樹的遍歷
堆疊的原始碼在我的博客中有寫過，找不到的朋友可以翻上面的目錄
堆疊主要的變化：
void PreOrder(BinTree* T)
{
assert(T);// 斷言檢查是否為空樹
Stack s;
StackInit(&s);
StackPush(&s, T);// 先訪問根結點
while (!StackEmpty(&s)) // 堆疊非空才繼續訪問
{
T = StackTop(&s);//訪問元素
StackPop(&s);// 訪問了就洗掉元素
printf("%c ", T->data);// 列印訪問的元素
if (T->rightChild != NULL) // 先將右孩子保存在堆疊中
StackPush(&s, T->rightChild);
if (T->leftChild != NULL)
StackPush(&s, T->leftChild);// 先訪問左孩子
}
}
中序遍歷（堆疊實作）
- 先訪問中序下的第一個結點，從根結點開始沿leftChild 走到最左下角的結點，該結點的leftChild 為NULL，訪問它之后，在遍歷該結點的右子樹，重復執行上面的程序，直到該子樹遍歷完
前序跟中序都是使用堆疊進行遍歷的，堆疊的變化點是一樣的
void InOrder(BinTree* T)
{
assert(T);
Stack s;
StackInit(&s);
while (T || !StackEmpty(&s)) // 結點非慷訓者堆疊非空才繼續回圈
{
while (T != NULL)
{
StackPush(&s, T); // 先將根結點到左邊的左孩子集體入堆疊
T = T->leftChild; // 先將左孩子入堆疊
}
if (!StackEmpty(&s))
{
T = StackTop(&s);//訪問左孩子
StackPop(&s);// 左孩子出堆疊
printf("%c ", T->data); // 左孩子和根訪問完了，在將右入堆疊
T = T->rightChild;
}
}
}
后序遍歷（堆疊實作）
- 后序相對于前序和中序來說比較麻煩一點，后序遍歷訪問順序是：左右根，這也就意味著先要暫存根結點的地址，所以這里必須表明是在左子樹（L）還是在右子樹（R）中，
- 先用堆疊暫存根結點地址，在遍歷左子樹，此時根結點的標記 tag = L，當訪問完左子樹結點之后，還要去訪問右子樹，此時修改根結點的標記 tag = R，右子樹訪問完在訪問根結點，
這里用到了其他結構體，與前序、中序有所不同，讀者注意區分
void PostOrder(BinTree* T)
{
if (T != NULL)
{
Stack s;
StackInit(&s);
StkNode w;//標記結構體
do
{
while (T != NULL)
{
w.p = T;
w.tag = L;
StackPush(&s, w);
T = T->leftChild;//一直將左孩子入堆疊
}
bool flag = true; // 繼續回圈標記，用于 R
while (flag && !StackEmpty(&s))
{
w = StackTop(&s);
StackPop(&s);
T = w.p;
switch (w.tag) // 判斷堆疊頂的 tag 標記
{
case L:
w.tag = R; // 修改根結點的標簽，這樣才能訪問右孩子
StackPush(&s, w);
flag = false; // 修改回圈標記
T = T->rightChild; // 遍歷右孩子，入堆疊
break;
case R:
printf("%c ", T->data); // 左右孩子出堆疊
break;
default:
break;
}
}
} while (!StackEmpty(&s)); // 回圈遍歷
}
}
層次遍歷（佇列實作）
- 在訪問二叉樹的某一結點時，把下一層的結點記憶在佇列中，每當訪問一個結點時，將它的子女依次加到佇列的隊尾，然后再去訪問隊頭的結點，依次回圈
用佇列實作的，寫了博客的，在目錄里面，不理解的結合看
void LevelOrder(BinTree* T)
{
Queue q;
QueueInit(&q);
if (T != NULL)
{
QueuePush(&q, T); // 根結點先入隊訪問
}
while (!QueueEmpty(&q))
{
T = QueueFront(&q);
QueuePop(&q); printf("%c", T->data); // 訪問隊頭元素
if(T->leftChild)
QueuePush(&q, T->leftChild); // 記錄左孩子
if (T->rightChild)
QueuePush(&q, T->rightChild); // 記錄右孩子
}
}
ps：涉及到堆疊和佇列的內容，需讀者先掌握著兩塊的知識，才能更好理解二叉樹的非遞回遍歷
制作不易，記得三連！！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/295175.html
標籤：其他
上一篇：【C語言】程式的編譯與預處理操作