数据结构学习笔记-二叉树的遍历（JAVA）
xingweiyong 2015-04-07
二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。
两种遍历：
递归遍历和层次遍历.
前序：根左右
中序：左根右
后序：左右根
publicclassTree
{
publicTreemLeft;
publicTreemRight;
privateDatamData;
publicList<Tree>treeList=newArrayList<Tree>();
publicstaticfinalintMAX=40;
//层次遍历时保存各个节点
Tree[]elements=newTree[MAX];
//层次遍历时队首
intfront;
//层次遍历时队尾
intrear;
publicTree(Treeleft,Treeright,Datadata)
{
this.mLeft=left;
this.mRight=right;
this.mData=data;
}
publicTree(Treeleft,Treeright,Stringdata)
{
this.mLeft=left;
this.mRight=right;
this.mData=newData(data);
}
//前序遍历，根左右
publicvoidpreOrder(Treeparent)
{
if(parent==null)
return;
System.out.print(parent.mData.desc+"");
preOrder(parent.mLeft);
preOrder(parent.mRight);
}
//中序遍历，左根右
publicvoidinOrder(Treeparent)
{
if(parent==null)
return;
inOrder(parent.mLeft);
System.out.print(parent.mData.desc+"");
inOrder(parent.mRight);
}
//后序遍历，左右根
publicvoidpostOrder(Treeparent)
{
if(parent==null)
return;
postOrder(parent.mLeft);
postOrder(parent.mRight);
System.out.print(parent.mData.desc+"");
}
//遍历treeList并生成下次要遍历的
publicvoidlayerOrder()
{
if(treeList.isEmpty())
return;
List<Tree>buff=newArrayList<Tree>();
for(Treet:treeList)
{
if(t!=null)
{
System.out.print(t.mData.desc+"");
buff.add(t.mLeft);
buff.add(t.mRight);
}
}
treeList.clear();
if(!buff.isEmpty())
{
treeList.addAll(buff);
layerOrder();
}
}
//另外一种利用数组层次遍历的实现
publicvoidlayerOrder1(Treeparent)
{
elements[0]=parent;
front=0;
rear=1;
while(front<rear)
{
if(elements[front].mData!=null)
{
System.out.print(elements[front].mData.desc+"");
if(elements[front].mLeft!=null)
{
elements[rear++]=elements[front].mLeft;
}
if(elements[front].mRight!=null)
{
elements[rear++]=elements[front].mRight;
}
front++;
}
}
}
publicstaticclassData
{
publicStringdesc;
publicData(Strings)
{
this.desc=s;
}
@Override
publicStringtoString()
{
returndesc;
}
}
}
publicclassTreeMain
{
publicstaticvoidmain(String[]args)
{
Treed=newTree(null,null,"D");
Treee=newTree(null,null,"E");
Treef=newTree(null,null,"F");
Treeg=newTree(null,null,"G");
Treeb=newTree(d,e,"B");
Treec=newTree(f,g,"C");
Treea=newTree(b,c,"A");
a.preOrder(a);
System.out.println("");
a.inOrder(a);
System.out.println("");
a.postOrder(a);
System.out.println("");
a.treeList.add(a);
a.layerOrder();
}
}
