多叉树怎么用递归遍历?用数组保存
温馨提示:您好,感谢您使用微问,(如果能帮到你,请猛戳“有用”)给的是3叉树,可以自己改MAX_CHILDREN_NUM 3 //三叉树
输入节点,然后分别建底下的各个孩子,注意,每个孩子都要求输入数据,没有则输入0。 反正建树很烦
#include
#include
#include
#include
#define MAX_DEPTH 4
#define MAX_CHILDREN_NUM 3 //三叉树
typedef struct tnode
{
int data;
tnode **children, *parent; //parent域可不要
}tnode;
typedef ...全部
温馨提示:您好,感谢您使用微问,(如果能帮到你,请猛戳“有用”)给的是3叉树,可以自己改MAX_CHILDREN_NUM 3 //三叉树
输入节点,然后分别建底下的各个孩子,注意,每个孩子都要求输入数据,没有则输入0。
反正建树很烦
#include
#include
#include
#include
#define MAX_DEPTH 4
#define MAX_CHILDREN_NUM 3 //三叉树
typedef struct tnode
{
int data;
tnode **children, *parent; //parent域可不要
}tnode;
typedef struct
{
tnode* ptr;
int cur;//cur记录当前访问到的孩子节点下标
bool visited; //是否被访问标记
}snode;
typedef struct
{
snode *elem;
int top;
}stack;
void initstack(stack *s)
{
s->elem=(snode*)malloc(
(int)pow(MAX_CHILDREN_NUM,MAX_DEPTH)*sizeof(snode));
s->top = 0;
}
void pop(stack *s, snode *e)
{
--s->top;
*e = s->elem[s->top];
}
void push(stack *s, snode *e)
{
s->elem[s->top] = *e;
++s->top;
}
void create(tnode **t, tnode *parent)
{
int n;
scanf("%d", &n);
if(!n)
{
*t = NULL;
return;
}
else
{
*t = (tnode*)malloc(sizeof(tnode));
(*t)->data = n;
(*t)->parent = parent;//可不要
(*t)->children = (tnode**)malloc(MAX_CHILDREN_NUM*sizeof(tnode*));
for(n = 0; n children[n], *t);
}
}
void visit(tnode *t)
{
printf("%5d", t->data);
}
void postorder1(tnode *t)
{
int i;
if(t)
{
for(i = 0; i children[i]);
visit(t);
}
}
void postorder2(tnode *t)
{// 和前序遍历基本相同,只是把访问语句的执行由
// 入栈时执行改为出栈时执行
stack s;
snode e;
initstack(&s);
e。
ptr = t;
e。cur = 0;
e。visited = false;
push(&s, &e);
while(s。top)
{
while(s。
elem[s。top-1]。ptr)
{
do
{
e。ptr = s。elem[s。top-1]。
ptr->children[s。elem[s。top-1]。cur];
++s。elem[s。top-1]。cur;
}while(!e。
ptr && s。elem[s。top-1]。cur top && s。elem[s。top-1]。cur == MAX_CHILDREN_NUM)
{
if(!s。elem[s。top-1]。visited)
{
visit(s。
elem[s。top-1]。ptr);
s。elem[s。top-1]。
visited = true;
}
pop(&s, &e);
}
}
}
void main()
{
tnode *T;
create(&T, NULL);
printf("\n递归后序遍历:");
postorder1(T);
printf("\n非递归后序遍历:");
postorder2(T);
}。收起