首页 - 资讯 - 科技 - 教育 - 汽车 - 财经 - 健康 - 房产 - 文旅 - 娱乐 - 游戏
数码 |互联网 |名企 |IT业 |能源 |幼教 |高考 |大学 |就业 |锐评 |培训 |资讯 |焦点 |会展
当前位置： 首页> 科技> 能源 > 沈阳泌尿科十大排行医院_高端手机_怎么做好seo内容优化_2345网址导航删除办法

沈阳泌尿科十大排行医院_高端手机_怎么做好seo内容优化_2345网址导航删除办法

时间:2025/7/18 11:49:12来源：https://blog.csdn.net/2301_76781059/article/details/146279539 浏览次数:0次
沈阳泌尿科十大排行医院_高端手机_怎么做好seo内容优化_2345网址导航删除办法

 纯C语言实现，不涉及C++ 

遍历是二叉树各种操作的基础，例如对于一棵给定二叉树求结点的双亲/求结点的孩子/求二叉树的高度/求叶结点个数/判断两棵二叉树是否相等……所有这些操作都是在二叉树遍历的过程中进行的。因此必须掌握二叉树的各种遍历过程，并能灵活用以解决各种问题。

常见的遍历次序有：先序，中序，后序

->其中“序”是指根结点何时被访问。

先序：根结点->左子树->右子树

中序: 左子树->根结点->右子树

后序: 左子树->右子树->根结点

对于递归遍历还是很好实现的，如

1. 递归先序遍历

void preOrder(BiTNode* root) {if (root != NULL) {printf("%d ", root->data);// 访问当前节点（这里是打印节点的值）preOrder(root->lchild);preOrder(root->rchild);}
}

2. 递归中序遍历

void inOrder(BiTNode* root) {if (root != NULL){inOrder(root->lchild);printf("%d ", root->data);inOrder(root->rchild);}
}

3. 递归后序遍历

void postOrder(BiTNode* root) {if (root != NULL){postOrder(root->lchild);postOrder(root->rchild);printf("%d ", root->data);}
}

下面具体来说一下二叉树的非递归的先/中/后遍历：

栈的后进先出（LIFO）特性使得它非常适合模拟递归调用过程中系统栈的行为。在二叉树的非递归遍历中，使用栈可以保存待访问的节点和控制节点的访问顺序，从而实现与递归遍历相同的效果。故：使用栈来保存待访问的节点和控制节点的访问顺序。

下面结合代码模拟二叉树的非递归的先/中/后遍历的全过程：

首先，需要先声明一下基本结构和栈的基本操作：

typedef struct BiTNode {  //树结点
    ElemType data;
    struct BiTNode* lchild;
    struct BiTNode* rchild;
}BiTNode;

typedef struct stackNode {  //栈结点
    struct BiTNode* pBiTNode;  // 指向二叉树节点的指针
    struct stackNode* next;  // 指向下一个栈节点的指针
}stackNode;

typedef struct stack {  //栈结构
    struct stackNode* top;  //指向栈顶结点
}stack;

1. 初始化栈

void initStack(stack* s) {s->top = NULL;
}

2. 判空操作

若栈顶指针为 NULL，则栈为空，返回 1；否则返回 0

int isEmpty(stack* s) {return s->top == NULL;
}

3. 入栈

用于将一个二叉树节点压入栈中

void push(stack* s, BiTNode* node) {stackNode* newStackNode = (stackNode*)malloc(sizeof(stackNode));  if (newStackNode == NULL){printf("内存分配失败!\n");return;}newStackNode->pBiTNode = node;  // 将新栈节点指向传入的二叉树节点newStackNode->next = s->top;  // 让新栈节点的 next 指针指向当前栈顶节点s->top = newStackNode;  // 更新栈顶指针为新栈节点
}

4. 出栈

用于从栈中弹出一个二叉树节点,便于后面遍历操作中进行访问

BiTNode* pop(stack* s) {if (isEmpty(s)){printf("栈空，无元素可出栈!\n");return NULL;}stackNode* temp = s->top;   // 临时保存栈顶节点BiTNode* node = temp->pBiTNode; // 取出栈顶节点所指向的二叉树节点s->top = temp->next;  // 更新栈顶指针为原栈顶节点的下一个节点free(temp);   // 释放原栈顶节点的内存return node;
}

5.销栈

在遍历结束之后，栈中不再有未处理的结点，栈已经完成了它辅助遍历的过程，此时需要销毁栈结构以释放栈中所占用的内存

void destroyStack(stack* s) {while (!isEmpty(s)) {  // 当栈不为空时，不断弹出栈顶节点pop(s);}
}

好的，有了上面的基本辅助操作后，我们来开始正式对树进行操作

1. 创建新的树结点

BiTNode* createNewBiTNode(ElemType value) {BiTNode* newBiTNode = (BiTNode*)malloc(sizeof(BiTNode));if (newBiTNode == NULL){printf("内存分配失败!\n");return NULL;}newBiTNode->data = value;newBiTNode->lchild = NULL;newBiTNode->rchild = NULL;return newBiTNode;
}

2. 销毁树结构

void destroyTree(BiTNode* root) {if (root == NULL){return;}destroyTree(root->lchild);destroyTree(root->rchild);free(root);
}

3. 非递归先序遍历

 具体思路 ：是先将根节点入栈，然后循环处理栈中的节点，每次弹出栈顶节点并访问，接着将其右子节点和左子节点依次入栈（注意顺序，因为栈是后进先出，所以先入右子结点）

void preOrderTraversal(BiTNode* root) {if (root == NULL){return;}stack s;initStack(&s);push(&s, root);while (!isEmpty(&s)) {BiTNode* p = pop(&s);printf("%d ", p->data);if (p->rchild != NULL){push(&s, p->rchild);}if (p->lchild != NULL){push(&s, p->lchild);}}printf("\n");destroyStack(&s);//遍历完记得销毁栈
}

4. 非递归中序遍历

 具体思路 ：先将根节点及左子树的所有节点依次入栈，然后出栈访问节点，再让指针指向该节点的右子树，重复上述入栈、出栈访问、指向右子树的操作直至栈空且指针为空。

void inOrderTraversal(BiTNode* root) {stack s;initStack(&s);BiTNode* p = root;while (p != NULL || !isEmpty(&s)) {while (p != NULL) {push(&s, p);p = p->lchild;}p = pop(&s);printf("%d ", p->data);p = p->rchild;}printf("\n");destroyStack(&s);遍历完记得销毁栈
}

5. 非递归后序遍历

相对复杂一些，需要使用两个栈来完成。

 具体思路 ：先将根节点压入第一个栈，然后循环处理第一个栈，每次弹出栈顶节点并压入第二个栈，接着将其左子节点和右子节点依次压入第一个栈。最后，依次弹出第二个栈的节点并访问。

void postOrderTraversal(BiTNode* root) {if (root == NULL){return;}stack s1, s2;initStack(&s1);initStack(&s2);push(&s1, root);while (!isEmpty(&s1)) {BiTNode* p = pop(&s1);push(&s2, p);if (p->lchild != NULL){push(&s1, p->lchild);}if (p->rchild != NULL){push(&s1, p->rchild);}}while (!isEmpty(&s2)) {BiTNode* p = pop(&s2);printf("%d ", p->data);}printf("\n");destroyStack(&s1);//遍历完记得销毁栈destroyStack(&s2);
}

6. 建一棵树测试遍历

int main() {//创建一棵树BiTNode* root = createNewBiTNode(1);root->lchild = createNewBiTNode(2);root->rchild = createNewBiTNode(3);root->lchild->lchild = createNewBiTNode(4);root->lchild->rchild = createNewBiTNode(5);root->rchild->lchild = createNewBiTNode(6);printf("递归先序遍历的结果：");preOrder(root);printf("\n");printf("递归中序遍历的结果：");inOrder(root);printf("\n");printf("递归后序遍历的结果：");postOrder(root);printf("\n\n");printf("非递归先序遍历的结果：");preOrderTraversal(root);printf("非递归中序遍历的结果：");inOrderTraversal(root);printf("非递归后序遍历的结果：");postOrderTraversal(root);destroyTree(root);return 0;
}

7. 完整代码

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;typedef struct BiTNode {  //树结点ElemType data;struct BiTNode* lchild;struct BiTNode* rchild;
}BiTNode;typedef struct stackNode {  //栈结点struct BiTNode* pBiTNode;  // 指向二叉树节点的指针struct stackNode* next;  // 指向下一个栈节点的指针
}stackNode;typedef struct stack {  //栈结构struct stackNode* top;  //指向栈顶结点
}stack;//1.1 初始化栈
void initStack(stack* s) {s->top = NULL;
}//2.1判空
// 该函数用于判断栈是否为空，若栈顶指针为 NULL，则栈为空，返回 1；
// 否则返回 0
int isEmpty(stack* s) {return s->top == NULL;
}//3.1 入栈该函数用于将一个二叉树节点压入栈中
void push(stack* s, BiTNode* node) {stackNode* newStackNode = (stackNode*)malloc(sizeof(stackNode));  if (newStackNode == NULL){printf("内存分配失败!\n");return;}newStackNode->pBiTNode = node;  // 将新栈节点指向传入的二叉树节点newStackNode->next = s->top;  // 让新栈节点的 next 指针指向当前栈顶节点s->top = newStackNode;  // 更新栈顶指针为新栈节点
}//4.1 出栈，返回出栈的树结点
// 该函数用于从栈中弹出一个二叉树节点
BiTNode* pop(stack* s) {if (isEmpty(s)){printf("栈空，无元素可出栈!\n");return NULL;}stackNode* temp = s->top;   // 临时保存栈顶节点BiTNode* node = temp->pBiTNode; // 取出栈顶节点所指向的二叉树节点s->top = temp->next;  // 更新栈顶指针为原栈顶节点的下一个节点free(temp);   // 释放原栈顶节点的内存return node;
}//5.1 销栈，在遍历结束之后，栈中不再有未处理的结点，栈已经完成了它辅助遍历的过程，此时需要销毁栈结构以释放栈中所占用的内存
void destroyStack(stack* s) {while (!isEmpty(s)) {  // 当栈不为空时，不断弹出栈顶节点pop(s);}
}//1.1 创建新的树结点
BiTNode* createNewBiTNode(ElemType value) {BiTNode* newBiTNode = (BiTNode*)malloc(sizeof(BiTNode));if (newBiTNode == NULL){printf("内存分配失败!\n");return NULL;}newBiTNode->data = value;newBiTNode->lchild = NULL;newBiTNode->rchild = NULL;return newBiTNode;
}//2.1 销毁树结构
void destroyTree(BiTNode* root) {if (root == NULL){return;}destroyTree(root->lchild);destroyTree(root->rchild);free(root);
}//3.1 递归先序遍历
void preOrder(BiTNode* root) {if (root != NULL) {printf("%d ", root->data);// 访问当前节点（这里是打印节点的值）preOrder(root->lchild);preOrder(root->rchild);}
}//4.1 递归中序遍历
void inOrder(BiTNode* root) {if (root != NULL){inOrder(root->lchild);printf("%d ", root->data);inOrder(root->rchild);}
}//5.1 递归后序遍历
void postOrder(BiTNode* root) {if (root != NULL){postOrder(root->lchild);postOrder(root->rchild);printf("%d ", root->data);}
}//6.1 非递归先序遍历
//先序遍历的顺序是：根节点->左子树->右子树。
// 非递归实现可以借助栈来模拟递归调用的过程。
// 具体思路是先将根节点入栈，然后循环处理栈中的节点，每次弹出栈顶节点并访问，接着将其右子节点和左子节点依次入栈
// （注意顺序，因为栈是后进先出，所以先入右子节点）。
void preOrderTraversal(BiTNode* root) {if (root == NULL){return;}stack s;initStack(&s);push(&s, root);while (!isEmpty(&s)) {BiTNode* p = pop(&s);printf("%d ", p->data);if (p->rchild != NULL){push(&s, p->rchild);}if (p->lchild != NULL){push(&s, p->lchild);}}printf("\n");destroyStack(&s);//遍历完记得销毁栈
}//7.1 非递归中序遍历
//非递归中序遍历的核心思路是利用栈来模拟递归调用的过程，
// 先将根节点及左子树的所有节点依次入栈，然后出栈访问节点，再让指针指向该节点的右子树，重复上述入栈、出栈访问、指向右子树的操作直至栈空且指针为空。
void inOrderTraversal(BiTNode* root) {stack s;initStack(&s);BiTNode* p = root;while (p != NULL || !isEmpty(&s)) {while (p != NULL) {push(&s, p);p = p->lchild;}p = pop(&s);printf("%d ", p->data);p = p->rchild;}printf("\n");destroyStack(&s);遍历完记得销毁栈
}//8.1 非递归后序遍历
//后序遍历的顺序是：左子树 -> 右子树 -> 根节点。
// 非递归实现相对复杂一些，需要使用两个栈来完成。
// 具体思路是先将根节点压入第一个栈，然后循环处理第一个栈，每次弹出栈顶节点并压入第二个栈，接着将其左子节点和右子节点依次压入第一个栈。
// 最后，依次弹出第二个栈的节点并访问。
void postOrderTraversal(BiTNode* root) {if (root == NULL){return;}stack s1, s2;initStack(&s1);initStack(&s2);push(&s1, root);while (!isEmpty(&s1)) {BiTNode* p = pop(&s1);push(&s2, p);if (p->lchild != NULL){push(&s1, p->lchild);}if (p->rchild != NULL){push(&s1, p->rchild);}}while (!isEmpty(&s2)) {BiTNode* p = pop(&s2);printf("%d ", p->data);}printf("\n");destroyStack(&s1);//遍历完记得销毁栈destroyStack(&s2);
}int main() {//创建一棵树BiTNode* root = createNewBiTNode(1);root->lchild = createNewBiTNode(2);root->rchild = createNewBiTNode(3);root->lchild->lchild = createNewBiTNode(4);root->lchild->rchild = createNewBiTNode(5);root->rchild->lchild = createNewBiTNode(6);printf("递归先序遍历的结果：");preOrder(root);printf("\n");printf("递归中序遍历的结果：");inOrder(root);printf("\n");printf("递归后序遍历的结果：");postOrder(root);printf("\n\n");printf("非递归先序遍历的结果：");preOrderTraversal(root);printf("非递归中序遍历的结果：");inOrderTraversal(root);printf("非递归后序遍历的结果：");postOrderTraversal(root);destroyTree(root);return 0;
}

8. 运行截图

 分享个小妙招 ：有什么不明白的，复制完整代码，然后问AI:“请给出以上代码中的xx操作的详细过程”。

文章如有出错不足处，欢迎评论区指出，如果觉得文章不错，就给我点个赞吧，谢谢！

关键字：沈阳泌尿科十大排行医院_高端手机_怎么做好seo内容优化_2345网址导航删除办法

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

责任编辑：
>> 相关文章
>> 热门图片
物流软件app前十名_手机应用软件开发培训班_seo官网优化怎么做_网站维护一年一般多少钱?
物流软件app前十名_手机应用软件开发培训班_seo官网优化怎么做_网站维护一年一般多少钱?
做电商哪个平台好_移动商城官网_百度权重是什么_sem投放是什么意思
做电商哪个平台好_移动商城官网_百度权重是什么_sem投放是什么意思
推广平台哪个效果最好_天元建设集团有限公司企查查_东莞企业网站模板建站_网页seo搜索引擎优化
推广平台哪个效果最好_天元建设集团有限公司企查查_东莞企业网站模板建站_网页seo搜索引擎优化
低代码开发会废了程序员吗_个人小程序开发教程_深圳seo优化公司哪家好_seo网站地图
低代码开发会废了程序员吗_个人小程序开发教程_深圳seo优化公司哪家好_seo网站地图
专业简历制作网站有哪些_江门站排名优化_企业网站制作公司_app推广平台接单渠道
专业简历制作网站有哪些_江门站排名优化_企业网站制作公司_app推广平台接单渠道
深圳华强北怎么了_泉州网站建设托管_产品网络营销策划方案_a站
深圳华强北怎么了_泉州网站建设托管_产品网络营销策划方案_a站
视频制作公司拍摄_简单安卓app开发_网络营销软件排行_百度指数里的资讯指数是什么
视频制作公司拍摄_简单安卓app开发_网络营销软件排行_百度指数里的资讯指数是什么
企业管理信息系统有哪些_邯郸求职信息网_搜狗推广登录入口_推广员网站
企业管理信息系统有哪些_邯郸求职信息网_搜狗推广登录入口_推广员网站
>> 热门搜索
评论排行
图片新闻
更多>>
武汉掌上人才网_海口云建站模板_全网优化推广_营销策划师
驻马店网站开发公司_西安搜建站科技网站_百度打广告多少钱_永久免费的网站服务器有哪些软件
深圳小程序app定制开发_网站源码推荐_网站优化推广_搜索引擎推广的三种方式
网页制作与设计先学什么_厦门网页设计培训班_市场调研报告范文大全_深圳网络推广专员
点击排行

邮箱：809451989@qq.com 网站地图
未经过本站允许,请勿将本站内容传播或复制