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
https://www.jianshu.com/p/7df6e7194d02
这个方法靠谱，测试成功了！
image.png
image.png
版本一，3中遍历方式，前序，中序，后序
//#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
//#include <locale.h>
//遇到了一个难题，解决办法：https://www.jianshu.com/p/7df6e7194d02
//描述单一个体
typedef struct treeNode
{
char data; //数据域字符表示
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;
}
//没有规律的树
void insertNode(LPTREE parentNode, LPTREE LChild, LPTREE RChild)
{
parentNode->LChild = LChild;
parentNode->RChild = RChild;
}
void printCurNodeData(LPTREE CurData )
{
printf("%c\t", CurData->data);
}
//递归法；领悟
//前序，根，左，右
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()
{
//死板的創建過程，无任何实际意义
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;
}
结果如图所示：
image.png
接下来，用非递归方法，中序方法遍历节点。
image.png
最终结果，2个方法遍历，递归和非递归都成功了，代码如下：
//#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
//#include <locale.h>
//遇到了一个难题，解决办法：https://www.jianshu.com/p/7df6e7194d02
//描述单一个体
typedef struct treeNode
{
char data; //数据域字符表示
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;
}
//没有规律的树
void insertNode(LPTREE parentNode, LPTREE LChild, LPTREE RChild)
{
parentNode->LChild = LChild;
parentNode->RChild = RChild;
}
void printCurNodeData(LPTREE CurData )
{
printf("%c\t", CurData->data);
}
//递归法；领悟
//前序，根，左，右
void preOrder(LPTREE root )
{
if (root!=NULL )
{
printCurNodeData(root); //根
preOrder(root->LChild); //左
preOrder(root->RChild); //右
}
}
//前序遍历，采用栈方式，非递归方式遍历
void preOrderByStack(LPTREE root)
{
if (root == NULL)
{
return;
}
//准备一个栈
LPTREE stack[10]; //结构体指针，用来存放节点的位置。存储每次打印的节点的位置
// struct treeNode* stack[10];
int stackTop = -1; //栈顶标记,等于-1，是为了跟数组下标保持一致而已
LPTREE pMove = root; //从根节点开始打印
while (stackTop != -1 || pMove) //当栈中没有路径可以退，或者当前节点不等于空的时候，
{
//根，左，右
//找到最左边
while (pMove)
{
//把路径入栈+打印走过的节点
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;
}
//栈的准备动作
struct treeNode* stack[10];
int stackTop = -1;
//定义的移动的指针
LPTREE pMove = root;
while (stackTop!= -1||pMove )
{
//走到最左边，把走过的结点入栈
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; //访问标记
//左，右，根
while (pMove)
{
Stack[++stackTop] = pMove;
pMove = pMove->LChild;
}
while (stackTop!=-1 )
{
pMove = Stack[stackTop--];
//当前节点左右是否被访问
if (pMove->RChild == NULL || pMove->RChild == pLastVisit)
{
//左，右，根
//如果被访问，就可以打印当前节点数据
printf("%c\t", pMove->data);
pLastVisit = pMove; //改变标记的位置
}
else
{
//右边没有被访问
Stack[++stackTop] = pMove;
pMove = pMove->RChild;
while (pMove)
{
Stack[++stackTop] = pMove;
pMove = pMove->LChild;
}
}
}
}
int main()
{
//死板的創建過程，无任何实际意义
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;
}
网友评论