二叉树遍历的非递归达成
发布时间：2021-11-19 15:38:44 所属栏目：教程 来源：互联网
导读：二叉树的非递归实现需要使用到下推栈，下面给出前序遍历的完整代码： #include stdio.h #include stdlib.h #define MAX 10 //二叉树存储结构定义 typedef char Item; typedef struct node *link; struct node {Item item; link l, r;}; int Create(link *tp)
|
二叉树的非递归实现需要使用到下推栈，下面给出前序遍历的完整代码： #include <stdio.h> #include <stdlib.h> #define MAX 10 //二叉树存储结构定义 typedef char Item; typedef struct node *link; struct node {Item item; link l, r;}; int Create(link *tp); void show(link h); void tranverse(link h, void (*visit)(link)); //下推栈存储结构定义 typedef link SItem; static SItem *s; static int N; void STACKinit(int maxN); int STACKempty(); void STACKpush(SItem item); SItem STACKpop(); int main() { link tree; Create(&tree); tranverse(tree, show); return 0; } void STACKinit(int maxN) { s = (SItem *)malloc(maxN * sizeof(SItem)); if (!s) return; N = 0; } int STACKempty() { return N==0; } void STACKpush(SItem item) { s[N++] = item; } SItem STACKpop() { return s[--N]; } int Create(link *tp) { //构造方法，或者说构造顺序：中序遍历构造 char x; scanf("%c",&x); if(x=='#') { *tp=NULL;//指针为空，树节点中的某个指针为空 return 0; } *tp=(link)malloc(sizeof(**tp));//将树节点中指针指向该地址空间 if(*tp==NULL) return 0; (*tp)->item=x; Create(&((*tp)->l)); Create(&((*tp)->r)); return 1; } void show(link h) { printf(" %c ", h->item); } //前序遍历 void tranverse(link h, void (*visit)(link)) { STACKinit(MAX); STACKpush(h); while (!STACKempty()){ (*visit)(h = STACKpop()); if (h->r != NULL) STACKpush(h->r); if (h->l != NULL) STACKpush(h->l); } }  （编辑：南通站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
