Java ---- 遍历链表(递归与非递归实现)

package test;
//前序遍历的递归实现与非递归实现
import java.util.Stack;
public class Test
{
public static void main(String[] args)
{
TreeNode[] node = new TreeNode[10];//以数组形式生成一棵完全二叉树
for(int i = 0; i < 10; i++)
{
node[i] = new TreeNode(i);
}
for(int i = 0; i < 10; i++)
{
if(i*2+1 < 10)
node[i].left = node[i*2+1];
if(i*2+2 < 10)
node[i].right = node[i*2+2];
} preOrderRe(node[0]);
} public static void preOrderRe(TreeNode biTree)
{//递归实现
System.out.println(biTree.value);
TreeNode leftTree = biTree.left;
if(leftTree != null)
{
preOrderRe(leftTree);
}
TreeNode rightTree = biTree.right;
if(rightTree != null)
{
preOrderRe(rightTree);
}
} public static void preOrder(TreeNode biTree)
{//非递归实现
Stack<TreeNode> stack = new Stack<TreeNode>();
while(biTree != null || !stack.isEmpty())
{
while(biTree != null)
{
System.out.println(biTree.value);
stack.push(biTree);
biTree = biTree.left;
}
if(!stack.isEmpty())
{
biTree = stack.pop();
biTree = biTree.right;
}
}
}
} class TreeNode//节点结构
{
int value;
TreeNode left;
TreeNode right; TreeNode(int value)
{
this.value = value;
}
}

二叉树的遍历

二叉树的遍历分为三种:前序遍历 中序遍历 后序遍历

前序遍历:按照“根左右”,先遍历根节点,再遍历左子树 ,再遍历右子树

中序遍历:按照“左根右“,先遍历左子树,再遍历根节点,最后遍历右子树

后续遍历:按照“左右根”,先遍历左子树,再遍历右子树,最后遍历根节点

其中前,后,中指的是每次遍历时候的根节点被遍历的顺序

二叉树遍历:

前根左右

中左根右

后左右根

上一篇:iOS Category 添加属性实现原理 - 关联对象


下一篇:sql clr项目注意