多叉樹的遍歷演算法

『壹』 多叉樹怎麼用遞歸遍歷

給的是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演算法，那可就長篇大論了去了。