JAVA二叉树递归和非递归遍历的用法.doc

《JAVA二叉树递归和非递归遍历的用法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、JAVA二叉树递归和非递归遍历的用法1、递归遍历[java]//先序遍历（递归实现）-------------------------------------------------------------/*1.Visitthenode.1.Callitselftotraversethenode’sleftsubtree.3.Callitselftotraversethenode’srightsubtree.4.basecase:thereisnonode*/privatevoidpreOrder(NodelocalRoot){if(localRoot!=null

2、){visit(localRoot);//System.out.print(localRoot.iData+"");preOrder(localRoot.leftChild);preOrder(localRoot.rightChild);}}//中序遍历（递归实现）-------------------------------------------------------------privatevoidinOrder(NodelocalRoot){if(localRoot!=null){inOrder(localRoot.leftChild);visit(loc

3、alRoot);//System.out.print(localRoot.iData+"");inOrder(localRoot.rightChild);}}//后序遍历（递归实现）-------------------------------------------------------------privatevoidpostOrder(NodelocalRoot){if(localRoot!=null){postOrder(localRoot.leftChild);postOrder(localRoot.rightChild);visit(localRoot

4、);//System.out.print(localRoot.iData+"");}}//-------------------------------------------------------------//先序遍历（递归实现）-------------------------------------------------------------/*1.Visitthenode.1.Callitselftotraversethenode’sleftsubtree.3.Callitselftotraversethenode’srightsubtree.4.b

5、asecase:thereisnonode*/privatevoidpreOrder(NodelocalRoot){if(localRoot!=null){visit(localRoot);//System.out.print(localRoot.iData+"");preOrder(localRoot.leftChild);preOrder(localRoot.rightChild);}}//中序遍历（递归实现）-------------------------------------------------------------privatevoidinOrd

6、er(NodelocalRoot){if(localRoot!=null){inOrder(localRoot.leftChild);visit(localRoot);//System.out.print(localRoot.iData+"");inOrder(localRoot.rightChild);}}//后序遍历（递归实现）-------------------------------------------------------------privatevoidpostOrder(NodelocalRoot){if(localRoot!=null){po

7、stOrder(localRoot.leftChild);postOrder(localRoot.rightChild);visit(localRoot);//System.out.print(localRoot.iData+"");}}//-------------------------------------------------------------2、非递归遍历[java]/*总体思想是：因为递归的本质是用栈实现的，所以写出非递归的形式要用到栈。入栈的顺序与访问的顺序相反，如中序遍历访问顺序是left,current,right,所以入栈的顺序相反