java实现递归层次遍历_Java实现二叉树的前序、中序、后序、层序遍历（递归方法）...
在數(shù)據(jù)結(jié)構(gòu)中，二叉樹是樹中我們見得最多的，二叉查找樹可以加速我們查找的效率，那么輸出一個二叉樹也變得尤為重要了。
二叉樹的遍歷方法分為四種，分別為前序遍歷、中序遍歷、后序、層序遍歷。下圖即為一個二叉樹。
前序遍歷：先遍歷根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。
結(jié)果為:4 2 1 3 6 5 7 8 10
中序遍歷:先遍歷左子樹，然后遍歷根結(jié)點，最后遍歷右子樹。
結(jié)果為：1 2 3 4 5 6 7 8 10
后序遍歷:先遍歷左子樹，然后遍歷右子樹，最后遍歷根節(jié)點。
結(jié)果為：1 3 2 5 10 8 7 6 4
層序遍歷：逐層遍歷。
結(jié)果為：4 2 6 1 3 5 7 8 10
按照上面的規(guī)則，就可以很快地對一顆二叉樹進(jìn)行遍歷，并且快速寫出結(jié)果，下面我附上我使用遞歸的方法對二叉樹實施四種遍歷的Java代碼。
public class Tree>
{
private static class BinaryNode
{
BinaryNode(AnyType theElement)
{
this(theElement, null, null);
}
BinaryNode(AnyType theElement, BinaryNode lt, BinaryNode rt)
{
element = theElement;
left = lt;
right = rt;
}
AnyType element;
BinaryNode left;
BinaryNode right;
}
private BinaryNode root;
public void insert(AnyType x)
{
root = insert(x, root);
}
private BinaryNode insert(AnyType x, BinaryNode t)
{
if(t == null)
{
return new BinaryNode<>(x, null, null);
}
int compareResult = x.compareTo(t.element);
if(compareResult < 0)
{
t.left = insert(x, t.left);
}
else if(compareResult > 0)
{
t.right = insert(x, t.right);
}
else
{
;
}
return t;
}
/**
* 前序遍歷
*/
public void preOrder(BinaryNode Node)
{
if (Node != null)
{
System.out.print(Node.element + " ");
preOrder(Node.left);
preOrder(Node.right);
}
}
/**
* 中序遍歷
*/
public void midOrder(BinaryNode Node)
{
if (Node != null)
{
midOrder(Node.left);
System.out.print(Node.element + " ");
midOrder(Node.right);
}
}
/**
* 后序遍歷
*/
public void posOrder(BinaryNode Node)
{
if (Node != null)
{
posOrder(Node.left);
posOrder(Node.right);
System.out.print(Node.element + " ");
}
}
/*
* 層序遍歷
* 遞歸
*/
public void levelOrder(BinaryNode Node) {
if (Node == null) {
return;
}
int depth = depth(Node);
for (int i = 1; i <= depth; i++) {
levelOrder(Node, i);
}
}
private void levelOrder(BinaryNode Node, int level) {
if (Node == null || level < 1) {
return;
}
if (level == 1) {
System.out.print(Node.element + " ");
return;
}
// 左子樹
levelOrder(Node.left, level - 1);
// 右子樹
levelOrder(Node.right, level - 1);
}
public int depth(BinaryNode Node) {
if (Node == null) {
return 0;
}
int l = depth(Node.left);
int r = depth(Node.right);
if (l > r) {
return l + 1;
} else {
return r + 1;
}
}
public static void main( String[] args )
{
int[] input = {4, 2, 6, 1, 3, 5, 7, 8, 10};
Tree tree = new Tree<>();
for(int i = 0; i < input.length; i++)
{
tree.insert(input[i]);
}
System.out.print( "前序遍歷 ：" );
tree.preOrder(tree.root);
System.out.print( "\n中序遍歷 ：" );
tree.midOrder(tree.root);
System.out.print( "\n后序遍歷 ：" );
tree.posOrder(tree.root);
System.out.print("\n遞歸層序遍歷：");
tree.levelOrder(tree.root);
}
}
以上就完成了對二叉樹的四種遍歷，但是這只是遞歸方法的遍歷，下次我再來用非遞歸的方法實現(xiàn)對二叉樹的遍歷。
總結(jié)
以上是生活随笔為你收集整理的java实现递归层次遍历_Java实现二叉树的前序、中序、后序、层序遍历（递归方法）...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： MySQL 纯insert_MySQL使
- 下一篇： acer投影仪无信号