首页 / JAVA / java 树的遍历(递归与非递归)
java 树的遍历(递归与非递归)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java 树的遍历(递归与非递归),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3169字,纯文字阅读大概需要5分钟。
内容图文
![java 树的遍历(递归与非递归)](/upload/InfoBanner/zyjiaocheng/1211/da4d93faf5c64ed29d69a8758c7bcc12.jpg)
package wangChaoPA实习工作练习.com.leetcode;
import java.util.ArrayList;
import java.util.Stack;
class TreeNode
{
TreeNode left;
TreeNode right;
int val;
TreeNode(int x)
{
val = x;
}
}
public class TreeTrivel
{
// 测试
public static void main(String[] args)
{
TreeTrivel aa = new TreeTrivel();
TreeNode treeNode1 = new TreeNode(1);
TreeNode treeNode2 = new TreeNode(2);
TreeNode treeNode3 = new TreeNode(3);
TreeNode treeNode4 = new TreeNode(4);
TreeNode treeNode5 = new TreeNode(5);
TreeNode treeNode6 = new TreeNode(6);
TreeNode treeNode7 = new TreeNode(7);
treeNode1.left = treeNode2;
treeNode1.right = treeNode3;
treeNode2.left = treeNode4;
treeNode2.right = treeNode5;
treeNode3.left = treeNode6;
treeNode3.right = treeNode7;
//三个方法相互有点影响,所以单独运行
/*
* ArrayList<Integer> postorder = aa.postorderTraversal(treeNode1); for
* (Integer temp : postorder) { System.out.print(temp + " "); }
* System.out.println();
*/
/*
* ArrayList<Integer> preorder = aa.preorderTraversal(treeNode1); for
* (Integer temp : preorder) { System.out.print(temp + " "); }
* System.out.println();
*/
ArrayList<Integer> inorder = aa.inorderTraversal(treeNode1);
for (Integer temp : inorder)
{
System.out.print(temp + " ");
}
System.out.println();
}
// 非递归中序遍历
/*
* 最重要的是判断结点p有没有作结点,若有则p.left进栈,并使p.left=null,否则将p.val保存到链表中,并判断p.
* right是否为null 若不为null则把p.right进栈
*/
public ArrayList<Integer> inorderTraversal(TreeNode root)
{
ArrayList<Integer> res = new ArrayList<Integer>();
if (root == null)
{
return res;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while (!stack.empty())
{
TreeNode temp = stack.peek();
if (temp.left == null)
{
TreeNode p = stack.pop();
res.add(p.val);
if (p.right != null)
{
stack.push(temp.right);
}
}
else
{
stack.push(temp.left);
temp.left = null;
}
}
return res;
}
/*
* 非递归后序遍历 思路:要保证根结点在其左孩子和右孩子访问之后才能访问,因此对于任一结点p,先将其入栈.
* 如果p不存在左孩子和右孩子,则可直接访问;否则将p的右孩子和左孩子依次入栈然后把p的左右孩子结点赋值null,这样就保证了每次取栈顶的元素的时候
* 左孩子在右孩子前面被访问, 左孩子和右孩子都在根结点前面被访问
*/
public ArrayList<Integer> postorderTraversal(TreeNode root)
{
ArrayList<Integer> res = new ArrayList<Integer>();
if (root == null)
{
return res;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while (!stack.isEmpty())
{
TreeNode temp = stack.peek();
if (temp.left == null && temp.right == null)
{
TreeNode pop = stack.pop();
res.add(pop.val);
}
else
{
if (temp.right != null)
{
stack.push(temp.right);
temp.right = null;
}
if (temp.left != null)
{
stack.push(temp.left);
temp.left = null;
}
}
}
return res;
}
// 非递归前序遍历
/*
* p.val直接保存到链表中,然后判断p.right是否为null若不为null则将p.right进栈 然后判断
* p.left是否为null若不为null则将p.left进栈
*/
public ArrayList<Integer> preorderTraversal(TreeNode root)
{
ArrayList<Integer> res = new ArrayList<Integer>();
if (root == null)
{
return res;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while (!stack.empty())
{
TreeNode temp = stack.pop();
res.add(temp.val);
if (temp.right != null)
{
stack.push(temp.right);
}
if (temp.left != null)
{
stack.push(temp.left);
}
}
return res;
}
}
原文:http://www.cnblogs.com/qingtianBKY/p/6869669.html
内容总结
以上是互联网集市为您收集整理的java 树的遍历(递归与非递归)全部内容,希望文章能够帮你解决java 树的遍历(递归与非递归)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。