https://www.bilibili.com/video/BV15a4y1a7B5?from=search&seid=1889880629413614926
image.png
image.png
image.png
image.png
image.png
image.png
29:13秒
image.png
image.png
比較完整的代碼：
image.png
image.png
image.png
image.png
image.png
image.png
image.png
=========================
========================用棧遞歸的方法。
56分鐘：
image.png
========================
遇到了問題：
https://www.cnblogs.com/hiloves/p/4678848.html
error LNK2019: 無法解析的外部符號
https://www.cnblogs.com/imzhstar/p/4110870.html
http://www.itdecent.cn/p/7df6e7194d02
這個方法靠譜，測試成功了！
image.png
image.png
版本一，3中遍歷方式，前序，中序，后序
//#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
//#include <locale.h>
//遇到了一個難題，解決辦法：http://www.itdecent.cn/p/7df6e7194d02
//描述單一個體
typedef struct treeNode
{
char data; //數(shù)據(jù)域字符表示
struct treeNode* LChild;
struct treeNode* RChild;
}TREE,*LPTREE;
LPTREE createNode(char data )
{
LPTREE newNode = (LPTREE)malloc(sizeof(TREE));
newNode->data = data;
newNode->LChild = NULL;
newNode->RChild = NULL;
return newNode;
}
//沒有規(guī)律的樹
void insertNode(LPTREE parentNode, LPTREE LChild, LPTREE RChild)
{
parentNode->LChild = LChild;
parentNode->RChild = RChild;
}
void printCurNodeData(LPTREE CurData )
{
printf("%c\t", CurData->data);
}
//遞歸法；領(lǐng)悟
//前序，根，左，右
void preOrder(LPTREE root )
{
if (root!=NULL )
{
printCurNodeData(root); //根
preOrder(root->LChild); //左
preOrder(root->RChild); //右
}
}
//左序：左，根，右
void MidOrder(LPTREE root)
{
if (root != NULL)
{
MidOrder(root->LChild); //左
printCurNodeData(root); //根
MidOrder(root->RChild); //右
}
}
//后序：左，根，右
void lastOrder(LPTREE root)
{
if (root != NULL)
{
lastOrder(root->LChild); //左
lastOrder(root->RChild); //右
printCurNodeData(root); //根
}
}
int main()
{
//死板的創(chuàng)建過程，無任何實際意義
LPTREE A = createNode('A');
LPTREE B = createNode('B');
LPTREE C = createNode('C');
LPTREE D = createNode('D');
LPTREE E = createNode('E');
LPTREE F = createNode('F');
LPTREE G = createNode('G');
insertNode(A, B, C);
insertNode(B, D, NULL);
insertNode(D, NULL, G);
insertNode(C, E, F);
printf("前序遍歷：\n");
preOrder(A);
printf("\n中序遍歷：\n");
MidOrder(A);
printf("\n后序遍歷：\n");
lastOrder(A);
system("pause");
return 0;
}
結(jié)果如圖所示：
image.png
接下來，用非遞歸方法，中序方法遍歷節(jié)點。
image.png
最終結(jié)果，2個方法遍歷，遞歸和非遞歸都成功了，代碼如下：
//#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
//#include <locale.h>
//遇到了一個難題，解決辦法：http://www.itdecent.cn/p/7df6e7194d02
//描述單一個體
typedef struct treeNode
{
char data; //數(shù)據(jù)域字符表示
struct treeNode* LChild;
struct treeNode* RChild;
}TREE,*LPTREE;
LPTREE createNode(char data )
{
LPTREE newNode = (LPTREE)malloc(sizeof(TREE));
newNode->data = data;
newNode->LChild = NULL;
newNode->RChild = NULL;
return newNode;
}
//沒有規(guī)律的樹
void insertNode(LPTREE parentNode, LPTREE LChild, LPTREE RChild)
{
parentNode->LChild = LChild;
parentNode->RChild = RChild;
}
void printCurNodeData(LPTREE CurData )
{
printf("%c\t", CurData->data);
}
//遞歸法；領(lǐng)悟
//前序，根，左，右
void preOrder(LPTREE root )
{
if (root!=NULL )
{
printCurNodeData(root); //根
preOrder(root->LChild); //左
preOrder(root->RChild); //右
}
}
//前序遍歷，采用棧方式，非遞歸方式遍歷
void preOrderByStack(LPTREE root)
{
if (root == NULL)
{
return;
}
//準(zhǔn)備一個棧
LPTREE stack[10]; //結(jié)構(gòu)體指針，用來存放節(jié)點的位置。存儲每次打印的節(jié)點的位置
// struct treeNode* stack[10];
int stackTop = -1; //棧頂標(biāo)記,等于-1，是為了跟數(shù)組下標(biāo)保持一致而已
LPTREE pMove = root; //從根節(jié)點開始打印
while (stackTop != -1 || pMove) //當(dāng)棧中沒有路徑可以退，或者當(dāng)前節(jié)點不等于空的時候，
{
//根，左，右
//找到最左邊
while (pMove)
{
//把路徑入棧+打印走過的節(jié)點
printf("%c\t", pMove->data);
stack[++stackTop] = pMove;
pMove = pMove->LChild;
}
//無路可走的處理
if (stackTop != -1)
{
pMove = stack[stackTop]; //獲取棧頂元素
stackTop--; //這個才是出棧操作
pMove = pMove->RChild; //找右邊的
}
}
}
//中序：左，根，右
void MidOrder(LPTREE root)
{
if (root != NULL)
{
MidOrder(root->LChild); //左
printCurNodeData(root); //根
MidOrder(root->RChild); //右
}
}
void MidOrderByStack(LPTREE root)
{
if (root == NULL)
{
return;
}
//棧的準(zhǔn)備動作
struct treeNode* stack[10];
int stackTop = -1;
//定義的移動的指針
LPTREE pMove = root;
while (stackTop!= -1||pMove )
{
//走到最左邊，把走過的結(jié)點入棧
while (pMove )
{
stack[++stackTop] = pMove;
pMove = pMove->LChild;
}
//出棧
if (stackTop!=-1 )
{
pMove = stack[stackTop--];
printf("%c \t", pMove->data);
pMove = pMove->RChild;
}
}
}
//后序：左，根，右
void lastOrder(LPTREE root)
{
if (root != NULL)
{
lastOrder(root->LChild); //左
lastOrder(root->RChild); //右
printCurNodeData(root); //根
}
}
void lastOrderByStack(LPTREE root)
{
if (root == NULL)
{
return;
}
struct treeNode* Stack[10];
int stackTop = -1;
struct treeNode* pMove = root;
struct treeNode* pLastVisit = NULL; //訪問標(biāo)記
//左，右，根
while (pMove)
{
Stack[++stackTop] = pMove;
pMove = pMove->LChild;
}
while (stackTop!=-1 )
{
pMove = Stack[stackTop--];
//當(dāng)前節(jié)點左右是否被訪問
if (pMove->RChild == NULL || pMove->RChild == pLastVisit)
{
//左，右，根
//如果被訪問，就可以打印當(dāng)前節(jié)點數(shù)據(jù)
printf("%c\t", pMove->data);
pLastVisit = pMove; //改變標(biāo)記的位置
}
else
{
//右邊沒有被訪問
Stack[++stackTop] = pMove;
pMove = pMove->RChild;
while (pMove)
{
Stack[++stackTop] = pMove;
pMove = pMove->LChild;
}
}
}
}
int main()
{
//死板的創(chuàng)建過程，無任何實際意義
LPTREE A = createNode('A');
LPTREE B = createNode('B');
LPTREE C = createNode('C');
LPTREE D = createNode('D');
LPTREE E = createNode('E');
LPTREE F = createNode('F');
LPTREE G = createNode('G');
insertNode(A, B, C);
insertNode(B, D, NULL);
insertNode(D, NULL, G);
insertNode(C, E, F);
printf("前序遍歷：\n");
preOrder(A);
printf("\n");
preOrderByStack(A);
printf("\n中序遍歷：\n");
MidOrder(A);
printf("\n");
MidOrderByStack(A);
printf("\n后序遍歷：\n");
lastOrder(A);
printf("\n");
lastOrderByStack(A);
system("pause");
return 0;
}
