【11】-java递归和非递归二叉树前序中序后序遍历

本文主要是介绍【11】-java递归和非递归二叉树前序中序后序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树的遍历

对于二叉树来讲最主要、最基本的运算是遍历。
遍历二叉树 是指以一定的次序访问二叉树中的每个结点。所谓 访问结点 是指对结点进行各种操作的简称。例如，查询结点数据域的内容，或输出它的值，或找出结点位置，或是执行对结点的其他操作。遍历二叉树的过程实质是把二叉树的结点进行线性排列的过程。假设遍历二叉树时访问结点的操作就是输出结点数据域的值，那么遍历的结果得到一个线性序列。
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：
　（1）访问结点本身(N)，
　（2）遍历该结点的左子树(L)，
　（3）遍历该结点的右子树(R)。

以上三种操作有六种执行次序：

　NLR、LNR、LRN、NRL、RNL、RLN。

注意：
前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。
　　由于被访问的结点必是某子树的根，所以N(Node)、L(Left subtlee)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
　　

前序

非递归

    public void preordernorec(TreeNode root){//System.out.println("先序遍历（非递归）：");//用数组模拟栈，假设有节点个数不超过32个TreeNode[] stack = new TreeNode[32];for(int i =0;i<32;i++){stack[i] = null;}int index =0;TreeNode pnode = root;while(pnode!=null||index>0){while(pnode!=null){System.out.print(pnode.getKey()+",");stack[index++] = pnode;             pnode = pnode.getLeftchlid();}pnode = stack[--index];pnode = pnode.getRightchild();}//System.out.println("");}

递归

public void preorder(TreeNode root){if(root!=null){System.out.print(root.getKey()+",");preorder(root.getLeftchlid());preorder(root.getRightchild());}}

中序

非递归

    public void inordernorec(TreeNode root){TreeNode[] stack = new TreeNode[32];int index=0;for(int i =0;i<32;i++){stack[i] = null;}TreeNode pnode = root;while(pnode!=null||index>0){while(pnode!=null){stack[index++] = pnode;pnode = pnode.getLeftchlid();}pnode = stack[--index];System.out.print(pnode.getKey()+",");pnode = pnode.getRightchild();}//System.out.println("");}

递归

public void inorder(TreeNode root){if(root!=null){inorder(root.getLeftchlid());System.out.print(root.getKey()+",");inorder(root.getRightchild());}}

后序遍历

非递归

public void postordernorec(TreeNode root){TreeNode[] stack = new TreeNode[32];int index=0;for(int i =0;i<32;i++){stack[i] = null;}TreeNode pnode = root;TreeNode LastVisit = null;while(pnode!=null||index>0){while(pnode!=null){stack[index++] = pnode;pnode = pnode.getLeftchlid();} pnode=stack[index-1];if(pnode.getRightchild()==null||pnode.getRightchild()==LastVisit){System.out.print(pnode.getKey()+",");LastVisit = pnode;index--;pnode = null;}else{pnode = pnode.getRightchild();}}
}

递归

public void postorder(TreeNode root){if(root!=null){postorder(root.getLeftchlid());postorder(root.getRightchild());System.out.print(root.getKey()+",");}
}

参考

http://blog.csdn.net/wuwenxiang91322/article/details/12231657
http://blog.csdn.net/tanyujing/article/details/9381451

这篇关于【11】-java递归和非递归二叉树前序中序后序遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---