java遍历多叉树_用java建立二叉树

‘壹’ 哪位仁兄有java实现的多叉树源码

多叉树到单链表结构的转换源代码

由于Animation结构体的定义为单链表形式，需要把多叉树骨骼数据转换为单链表中，十分头疼。

写之前要把转换的逻辑顺序想清楚，我在这采取深度优先（先深度后宽度）搜索，类似二叉树的前序遍历。把相关的几个函数帖出，区区几十行，但要把逻辑顺序想明白了，或许还有不对的地方。

/********************************************************
函数名称：FindFirstLeaf
功能描述：寻找本节点的叶子节点
参数说明：无

返回值：叶子节点
*********************************************************/
Frame_EX* Frame_EX::FindFirstLeaf()
{
Frame_EX* pFrame = FirstChildHaveSibling();
if(pFrame == this || pFrame->IsLeaf())
return pFrame;
else
return pFrame->m_pFrameSibling->LastLeaf();
}

//宽度搜索本节点的最后一个兄弟节点，如果没有则返回自身
Frame_EX* Frame_EX::LastSibling()
{
Frame_EX* pFrame = m_pFrameSibling;
if(!pFrame)
return this;

Frame_EX* pFramePrev;
while(pFrame)
{
pFramePrev = pFrame;
pFrame = pFrame->m_pFrameSibling;
}
return pFramePrev;
}

//深度搜索本节点下第一个有兄弟节点的孩子节点
//如果无孩子节点则返回自身，如果所有孩子节点均无兄弟节点则返回最后一个孩子节点
Frame_EX* Frame_EX::FirstChildHaveSibling()
{
Frame_EX* pFrame = m_pFrameFirstChild;
if(!pFrame)
return this;

Frame_EX* pFrameAfter = pFrame->m_pFrameFirstChild;

while(!pFrame->m_pFrameSibling && pFrameAfter)
{
pFrame = pFrameAfter;
pFrameAfter = pFrameAfter->m_pFrameFirstChild;
}
return pFrame;
}

//宽度优先（先宽度后深度）搜索本节点下最后一个叶子节点
Frame_EX* Frame_EX::LastLeaf()
{
if(IsLeaf())
return this;

Frame_EX* pFrame;
pFrame = LastSibling(); //先宽度
pFrame = pFrame->FirstChildHaveSibling(); //后深度

return pFrame->LastLeaf();
}

/********************************************************
函数名称：AddAnimationRecursive
功能描述：递归创建骨骼动画
参数说明：pFramePrev 动画链表中上一级动画相关联的骨骼
pFrame 待加入到链表中的骨骼动画

返回值：无
*********************************************************/
void SkeletonAnimation::AddAnimationRecursive(Frame_EX* pFramePrev, Frame_EX* pFrame)
{
if(!pFrame)
return;

LPAnimation pAnimation = new Animation();
pAnimation->pBoneName = pFrame->m_name;
pAnimation->pBone = pFrame;

//加入当前动画集合，pFramePrev为NULL加入到m_pAnimationSet中
if(!pFramePrev)
{
pAnimation->pNext = m_pAnimationSet->pAnimations;
m_pAnimationSet->pAnimations = pAnimation;
m_pAnimationSet->nAnimation++;
}
else
{
pAnimation->pNext = NULL;
m_pAnimationSet->Find(pFramePrev)->pNext = pAnimation;
m_pAnimationSet->nAnimation++;
}

if(pFrame->m_pFrameFirstChild)
AddAnimationRecursive(pFrame, pFrame->m_pFrameFirstChild);

if(pFrame->m_pFrameSibling)
AddAnimationRecursive(pFrame->FindFirstLeaf(), pFrame->m_pFrameSibling);
}

‘贰’ JAVA多叉树，递归输出为什么少了两行

系统被你打乱出故障了

‘叁’ 怎样用Java实现一个多叉树数据结构

这是一个典型的多叉树问题！最早的祖先用根节点表示，以下依次是他的/她的子女。这个就组成一棵树。每一棵树的数据包括了：名称、父节点指针、第一个孩子的指针、配偶指针、下一个兄弟姐妹的指针

‘肆’ 简单的JAVA多叉树问题实现

TreeNode.java
/*
*CopyrightWalkerStudio
*AllRightsReserved.
*
*文件名称：TreeNode.java
*摘要：
*作者：Walker
*创建时间：2013-03-19
*/
packagecom.walker.commons.data.model;

/**
*树节点
*
*@authorWalker
*@version1.0.0.0
*/
publicclassTreeNode
{
	/**节点Id*/
	privateStringnodeId;
	/**父节点Id*/
	privateStringparentId;
	/**文本内容*/
	privateStringtext;
	
	/**
	*构造函数
	*
	*@paramnodeId节点Id
	*/
	publicTreeNode(StringnodeId)
	{
		this.nodeId=nodeId;
	}
	
	/**
	*构造函数
	*
	*@paramnodeId节点Id
	*@paramparentId父节点Id
	*/
	publicTreeNode(StringnodeId,StringparentId)
	{
		this.nodeId=nodeId;
		this.parentId=parentId;
	}

	publicStringgetNodeId(){
		returnnodeId;
	}

	publicvoidsetNodeId(StringnodeId){
		this.nodeId=nodeId;
	}

	publicStringgetParentId(){
		returnparentId;
	}

	publicvoidsetParentId(StringparentId){
		this.parentId=parentId;
	}

	publicStringgetText(){
		returntext;
	}

	publicvoidsetText(Stringtext){
		this.text=text;
	}
	
}


ManyTreeNode.java

/*
*CopyrightWalkerStudio
*AllRightsReserved.
*
*文件名称：ManyTreeNode.java
*摘要：
*作者：Walker
*创建时间：2013-03-19
*/
packagecom.walker.commons.data.model;

importjava.util.ArrayList;
importjava.util.List;

/**
*多叉树节点
*
*@authorWalker
*@verion1.0.0.0
*/
publicclassManyTreeNode
{
	/**树节点*/
	privateTreeNodedata;
	/**子树集合*/
	privateList<ManyTreeNode>childList;
	
	/**
	*构造函数
	*
	*@paramdata树节点
	*/
	publicManyTreeNode(TreeNodedata)
	{
		this.data=data;
		this.childList=newArrayList<ManyTreeNode>();
	}
	
	/**
	*构造函数
	*
	*@paramdata树节点
	*@paramchildList子树集合
	*/
	publicManyTreeNode(TreeNodedata,List<ManyTreeNode>childList)
	{
		this.data=data;
		this.childList=childList;
	}

	publicTreeNodegetData(){
		returndata;
	}

	publicvoidsetData(TreeNodedata){
		this.data=data;
	}

	publicList<ManyTreeNode>getChildList(){
		returnchildList;
	}

	publicvoidsetChildList(List<ManyTreeNode>childList){
		this.childList=childList;
	}

}


ManyNodeTree.java

/*
*CopyrightWalkerStudio
*AllRightsReserved.
*
*文件名称：ManyNodeTree.java
*摘要：
*作者：Walker
*创建时间：2013-03-19
*/
packagecom.walker.commons.data.model;

importjava.util.ArrayList;
importjava.util.List;

/**
*多叉树生成、遍历工具
*
*@authorWalker
*@version1.0.0.0
*/
publicclassManyNodeTree
{
	/**树根*/
	privateManyTreeNoderoot;
	
	/**
	*构造函数
	*/
	publicManyNodeTree()
	{
		root=newManyTreeNode(newTreeNode("root"));
	}
	
	/**
	*生成一颗多叉树，根节点为root
	*
	*@paramtreeNodes生成多叉树的节点集合
	*@returnManyNodeTree
	*/
	publicManyNodeTreecreateTree(List<TreeNode>treeNodes)
	{
		if(treeNodes==null||treeNodes.size()<0)
			returnnull;
		
		ManyNodeTreemanyNodeTree=newManyNodeTree();
		
		//将所有节点添加到多叉树中
		for(TreeNodetreeNode:treeNodes)
		{
			if(treeNode.getParentId().equals("root"))
			{
				//向根添加一个节点
				manyNodeTree.getRoot().getChildList().add(newManyTreeNode(treeNode));
			}
			else
			{
				addChild(manyNodeTree.getRoot(),treeNode);
			}
		}
		
		returnmanyNodeTree;
	}
	
	/**
	*向指定多叉树节点添加子节点
	*
	*@parammanyTreeNode多叉树节点
	*@paramchild节点
	*/
	publicvoidaddChild(ManyTreeNodemanyTreeNode,TreeNodechild)
	{
		for(ManyTreeNodeitem:manyTreeNode.getChildList())
		{
			if(item.getData().getNodeId().equals(child.getParentId()))
			{
				//找到对应的父亲
				item.getChildList().add(newManyTreeNode(child));
				break;
			}
			else
			{
				if(item.getChildList()!=null&&item.getChildList().size()>0)
				{
					addChild(item,child);
				}				
			}
		}
	}
	
	/**
	*遍历多叉树
	*
	*@parammanyTreeNode多叉树节点
	*@return
	*/
	publicStringiteratorTree(ManyTreeNodemanyTreeNode)
	{
		StringBuilderbuffer=newStringBuilder();
		buffer.append("
");
		
		if(manyTreeNode!=null)
		{	
			for(ManyTreeNodeindex:manyTreeNode.getChildList())
			{
				buffer.append(index.getData().getNodeId()+",");
				
				if(index.getChildList()!=null&&index.getChildList().size()>0)
				{	
					buffer.append(iteratorTree(index));
				}
			}
		}
		
		buffer.append("
");
		
		returnbuffer.toString();
	}
	
	publicManyTreeNodegetRoot(){
		returnroot;
	}

	publicvoidsetRoot(ManyTreeNoderoot){
		this.root=root;
	}
	
	publicstaticvoidmain(String[]args)
	{
		List<TreeNode>treeNodes=newArrayList<TreeNode>();
			treeNodes.add(newTreeNode("系统权限管理","root"));
			treeNodes.add(newTreeNode("用户管理","系统权限管理"));
			treeNodes.add(newTreeNode("角色管理","系统权限管理"));
			treeNodes.add(newTreeNode("组管理","系统权限管理"));
			treeNodes.add(newTreeNode("用户菜单管理","系统权限管理"));
			treeNodes.add(newTreeNode("角色菜单管理","系统权限管理"));
			treeNodes.add(newTreeNode("用户权限管理","系统权限管理"));
			treeNodes.add(newTreeNode("站内信","root"));
			treeNodes.add(newTreeNode("写信","站内信"));
			treeNodes.add(newTreeNode("收信","站内信"));
			treeNodes.add(newTreeNode("草稿","站内信"));
			
			ManyNodeTreetree=newManyNodeTree();
			
			System.out.println(tree.iteratorTree(tree.createTree(treeNodes).getRoot()));
	}
	
}

‘伍’ Java 多叉树遍历

public class test {

private List<String[]> lists = new ArrayList<String[]>();
public test(){
lists.add(new String[]{"0","1"});
lists.add(new String[]{"0","2"});
lists.add(new String[]{"0","3"});
lists.add(new String[]{"3","4"});
lists.add(new String[]{"3","5"});
lists.add(new String[]{"3","6"});
lists.add(new String[]{"6","7"});
lists.add(new String[]{"6","8"});
}
public boolean testA(String s,String sysos){
boolean f = true;
for (int j = 0; j < lists.size(); j++) {
String[] str = lists.get(j);
if(str[0].equals(s)){
if(testA(str[1],sysos+s)){
f = false;
}
}
}
if(f){
System.out.println(sysos+s);
}
return f;
}

public static void main(String[] args){
test t = new test();
t.testA("0","");
}
}

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

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

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
}

‘玖’ 求多叉树的后序遍历代码。。。

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

#include <stdio.h>
#include <malloc.h>
#include <math.h>
#include <conio.h>
#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 < MAX_CHILDREN_NUM; ++n)
create(&(*t)->children[n], *t);
}
}

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

void postorder1(tnode *t)
{
int i;
if(t)
{
for(i = 0; i < MAX_CHILDREN_NUM; ++i)
postorder1(t->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<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);
}
}
}

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

‘拾’ 用java建立二叉树

数据结构的教材里有，
建立两个类就应该可以了。

一个是树的节点，一个是树，这个是我以前编写的宽度优先遍历的树的构建和遍历，希望对你有帮助。文件名是：Tree.java

import java.util.ArrayList;

// 树的一个节点
class TreeNode {

Object _value = null; // 他的值
TreeNode _parent = null; // 他的父节点，根节点没有PARENT
ArrayList _childList = new ArrayList(); // 他的孩子节点

public TreeNode( Object value, TreeNode parent ){
this._parent = parent;
this._value = value;
}

public TreeNode getParent(){
return _parent;
}

public String toString() {
return _value.toString();
}
}

public class Tree {

// 给出宽度优先遍历的值数组，构建出一棵多叉树
// null 值表示一个层次的结束
// "|" 表示一个层次中一个父亲节点的孩子输入结束
// 如：给定下面的值数组：
// { "root", null, "left", "right", null }
// 则构建出一个根节点，带有两个孩子("left","right")的树
public Tree( Object[] values ){
// 创建根
_root = new TreeNode( values[0], null );

// 创建下面的子节点
TreeNode currentParent = _root; // 用于待创建节点的父亲
//TreeNode nextParent = null;
int currentChildIndex = 0; // 表示 currentParent 是他的父亲的第几个儿子
//TreeNode lastNode = null; // 最后一个创建出来的TreeNode，用于找到他的父亲
for ( int i = 2; i < values.length; i++ ){

// 如果null ,表示下一个节点的父亲是当前节点的父亲的第一个孩子节点
if ( values[i] == null ){
currentParent = (TreeNode)currentParent._childList.get(0);
currentChildIndex = 0;
continue;
}

// 表示一个父节点的所有孩子输入完毕
if ( values[i].equals("|") ){
if ( currentChildIndex+1 < currentParent._childList.size() ){
currentChildIndex++;
currentParent = (TreeNode)currentParent._parent._childList.get(currentChildIndex);
}
continue;
}

TreeNode child = createChildNode( currentParent, values[i] );
}
}

TreeNode _root = null;

public TreeNode getRoot(){
return _root;
}
/**
// 按宽度优先遍历，打印出parent子树所有的节点
private void printSteps( TreeNode parent, int currentDepth ){
for ( int i = 0; i < parent._childList.size(); i++ ){
TreeNode child = (TreeNode)parent._childList.get(i);
System.out.println(currentDepth+":"+child);
}
if ( parent._childList.size() != 0 ) System.out.println(""+null);// 为了避免叶子节点也会打印null

//打印 parent 同层的节点的孩子
if ( parent._parent != null ){ // 不是root
int i = 1;
while ( i < parent._parent._childList.size() ){// parent 的父亲还有孩子
TreeNode current = (TreeNode)parent._parent._childList.get(i);
printSteps( current, currentDepth );
i++;
}
}

// 递归调用，打印所有节点
for ( int i = 0; i < parent._childList.size(); i++ ){
TreeNode child = (TreeNode)parent._childList.get(i);
printSteps( child, currentDepth+1 );
}

}

// 按宽度优先遍历，打印出parent子树所有的节点
public void printSteps(){
System.out.println(""+_root);
System.out.println(""+null);

printSteps(_root, 1 );
}**/

// 将给定的值做为 parent 的孩子，构建节点
private TreeNode createChildNode( TreeNode parent, Object value ){
TreeNode child = new TreeNode( value , parent );
parent._childList.add( child );
return child;
}

public static void main(String[] args) {

Tree tree = new Tree( new Object[]{ "root", null,
"left", "right", null,
"l1","l2","l3", "|", "r1","r2",null } );
//tree.printSteps();

System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(0) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(1) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(2) );

System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(0) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(1) );

}

}

导航:首页 > 编程语言 > java遍历多叉树

java遍历多叉树

与java遍历多叉树相关的资料