二叉树的三种递归遍历算法和中序遍历的非递归算法
2021/4/11 22:26:00
本文主要是介绍二叉树的三种递归遍历算法和中序遍历的非递归算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
二叉树本身是一种递归的数据类型,二叉树的许多操作离不开递归。非递归遍历包括结点入栈,先访问右子树,再访问根节点,访问左子树,先序和后序的非递归算法有待调试。
include <stdio.h>
#include<stdlib.h> #include<stdbool.h> typedef char TElemtype; typedef struct BiTNode { TElemtype Data; struct BiTNode* Lchild, * Rchild; }BiTNode; typedef BiTNode* BiTree; typedef BiTNode ElemType; typedef struct { ElemType* base; int top; int SatckSize; }Stack; typedef Stack* PStack; void PrintTree(BiTree Tree) { printf("%c", Tree->Data); } void PreOrder(BiTree Tree, void(*Visit)(BiTree)) { if (Tree) { Visit(Tree); PreOrder(Tree->Lchild, Visit); PreOrder(Tree->Rchild, Visit); } } void InOrder(BiTree Tree, void(*Visit)(BiTree)) { if (Tree) { InOrder(Tree->Lchild, Visit); Visit(Tree); InOrder(Tree->Rchild, Visit); } } void PostOrder(BiTree Tree, void (*Visit)(BiTree)) { if (Tree) { PostOrder(Tree, Visit); PostOrder(Tree, Visit); Visit(Tree); } } void Array_InOrder(BiTree Tree, void(*Visit)(BiTree)) { PStack S; InitStack(S, 100); BiTree p = Tree; while (p || !IsEmpty(S)) { if (p) { Push(S, *p); p = p->Lchild; } else { Pop(S, p); Visit(p); p->Rchild; } } } }
附上栈的一些操作
void InitStack(PStack S, int size) { if (!S) exit(1); if (size > 0) S->base = (ElemType*)malloc(sizeof(ElemType) * size); if (!S->base)exit(1); S->SatckSize = size; S->top = 0; } bool Pop(PStack S, ElemType* PopItem) { if (S->top <= 0) { printf("Stack is empty\n"); return false; } S->top--; *PopItem = *(S->base + S->top); return true; } bool Push(PStack S, ElemType PushItem) { if (S->top >= S->SatckSize) { printf("Stack is full\n"); return false; } *(S->base + S->top) = PushItem; S->top++; return true; } ElemType GetTop(PStack S, ElemType* TopItem) { if (S->top <= 0) { printf("NO Item\n"); } *TopItem = *(S->base + S->top - 1); return *TopItem; } bool IsEmpty(PStack S) { if (S->top == 0) return true; else return false; }
这篇关于二叉树的三种递归遍历算法和中序遍历的非递归算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现