多叉树的遍历算法

‘壹’ 多叉树怎么用递归遍历

给的是3叉树，可以自己改MAX_

C

HILDREN_NUM 3 //三叉树
输入节点，然后分别建底下的各个孩子，注意，每个孩子都要求输入数据，没有则输入0.反正建树很烦

#include<stdio.h>
#include<malloc.h>
#include<math.h>
#include<conio.h>
#defineMAX_DEPTH4
#defineMAX_CHILDREN_NUM3//三叉树

typedefstructtnode
{
intdata;
tnode**children,*parent;//parent域可不要
}tnode;

typedefstruct
{
tnode*ptr;
intcur;//cur记录当前访问到的孩子节点下标
boolvisited;//是否被访问标记
}snode;

typedefstruct
{
snode*elem;
inttop;
}stack;

voidinitstack(stack*s)
{
s->elem=(snode*)malloc(
(int)pow(MAX_CHILDREN_NUM,MAX_DEPTH)*sizeof(snode));
s->top=0;
}

voidpop(stack*s,snode*e)
{
--s->top;
*e=s->elem[s->top];
}

voidpush(stack*s,snode*e)
{
s->elem[s->top]=*e;
++s->top;
}

voidcreate(tnode**t,tnode*parent)
{
intn;
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<MAX_CHILDREN_NUM;++n)
create(&(*t)->children[n],*t);
}
}

voidvisit(tnode*t)
{
printf("%5d",t->data);
}

voidpostorder1(tnode*t)
{
inti;
if(t)
{
for(i=0;i<MAX_CHILDREN_NUM;++i)
postorder1(t->children[i]);
visit(t);
}
}

voidpostorder2(tnode*t)
{//和前序遍历基本相同，只是把访问语句的执行由
//入栈时执行改为出栈时执行

stacks;
snodee;

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<MAX_CHILDREN_NUM);
e.cur=0;
e.visited=false;
push(&s,&e);
}
pop(&s,&e);

while(s.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);
}
}
}

voidmain()
{
tnode*T;
create(&T,NULL);
printf("
递归后序遍历：");
postorder1(T);
printf("
非递归后序遍历：");
postorder2(T);
}

‘贰’ 多叉树的深度遍历，要求用栈实现遍历，并要求制定结束条件，以多叉树村词条

ude<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<conio.h>
#define DataType int
#define MAXSIZE 100
//#define NULL 0 //无需定义
typedef struct
{ DataType data[MAXSIZE];
int top;
}SeqStack;

SeqStack * init_SeqStack(SeqStack *&s) //初始化栈
{
s=(SeqStack *)malloc(sizeof(SeqStack));
if(!s)
{printf("空间不足\n");
return NULL;}
else
{s->top=-1;
return s;}
}

int empty_SeqStack(SeqStack *s) //判栈空
{ if(s->top==-1)
return 1;
else return 0;
}

int push_SeqStack(SeqStack *s,DataType x) //入栈
{ if(s->top==MAXSIZE-1)
return 0;
else

}

int pop_SeqStack(SeqStack *s,DataType *x) //出栈
{if(s->top==-1)
return 0;
else
{*x=s->data[s->top];
s->top--;
return 1;
}
}

DataType top_SeqStack(SeqStack *s) //取栈顶元素
{
if(empty_SeqStack(s))
return 0;
else
return s->data[s->top];
}

int print(SeqStack *s)
{ int i;
printf("当前栈中元素：\n");
for(i=s->top;i>=0;i--)
printf("%3d",s->data[i]);
printf("\n");
return 0;
}

int main()
{ SeqStack *L;
int n;
int num;
int m;
init_SeqStack(L);
printf("初始化完成\n");
printf("栈空：%d\n",empty_SeqStack(L));
printf("请输入入栈元素个数:\n");
scanf("%d",&n);
printf("请输入要入栈的%d个元素：\n");

for(int i=0;i<n;i++)
{ scanf("%d",&num);
push_SeqStack(L,num);
}
print(L);
printf("栈顶元素:%d\n",top_SeqStack(L));
printf("请输入要出栈的元素个数：%d\n",n);
scanf("%d",&n);
printf("以此出栈的%d个元素:\n",n);
for (int i=0; i<n;i++) //加int
{pop_SeqStack(L,&m);
printf("%3d",m);
}
printf("\n");
print(L);
printf("栈顶元素:%d\n",top_SeqStack(L));
return 0;
}
另外,虚机团上产品团购,超级便宜

‘叁’ java实现多叉树的某层遍历，求思路。一棵多叉树有M层，子节点数不定，要求打印输出第N层的节点。说

树的遍历多用递归，从根节点出发，对子数进行逐级迭代

/**
*以p为根向下访问x层
*@paramlayer存储结果
*/
publicvoidlayerX(List<Node>layer,Nodep,intx){
if(p!=null){
//至访问层的节点
if(x==1){
layer.add(p);
}

//继续递归访问以字节点为(参照)根访问x-1层
Node[]c=p.getChildren();
if(c!=null){
for(Noden:c){
layerX(layer,n,x-1);
}
}
}
}

classNode{
privateStringname;//节点名称
privateNode[]children;//子节点

publicNode(Stringname,Node[]children){
this.name=name;
this.children=children;
}
//getter，setter
}

‘肆’ 请问java在一个方法函数中能实现一颗多叉树的遍历吗

能，用递归算法，算法结构的书中都有实现代码。在c语言算法结构书中有，你找一下把c语法转换成java语法就可以了。

‘伍’ 华容道算法

和A STAR算法类似，实质是多叉树最短路径遍历的算法。
一个状态为树的的一个节点，这个状态下的一种走法为多叉树的下一级走法。
和a start算法的差异是 a star算法用一个二维数组就可以表示出某个状态是否已经在树里面
华容道需要用哈希表来表示这个状态是否在树里面

a start算法对权重的算法比较简单，权重=当前坐标和目标点的距离
华容道算法可就麻烦多了，貌似只用用曹操的坐标和出口坐标的距离来做权重

--------------
感觉我的回答和没说差不多，不会 a star算法的人完全看不懂，如果要解释 a star算法，那可就长篇大论了去了。