java创建二叉树并实现非递归中序遍历二叉树-阿里云开发者社区

开发者社区> 云栖-lxl> 正文

java创建二叉树并实现非递归中序遍历二叉树

简介: java创建二叉树并递归遍历二叉树前面已有讲解:http://www.cnblogs.com/lixiaolun/p/4658659.html。 在此基础上添加了非递归中序遍历二叉树: 二叉树类的代码: package binarytree; import linkedstack.
+关注继续查看

java创建二叉树并递归遍历二叉树前面已有讲解:http://www.cnblogs.com/lixiaolun/p/4658659.html

在此基础上添加了非递归中序遍历二叉树:

二叉树类的代码:

package binarytree;

import linkedstack.LinkStack;
import linkqueue.LinkQueue;

public class BinaryTree {

	class Node
	{
		public Object data;
		public Node lchild;
		public Node rchild;
		
		public Node(Object data)
		{
			this.data = data;
			this.lchild = null;
			this.rchild = null;
		}
	}

	//根节点
	private Node root = null;
	private Node node = null;
	/**
	 * 创建树
	 * 
	 * 以完全二叉树的格式来创建(子树不存在的用0填充),
	 * 对完全二叉树中每一个节点从0开始进行编号,
	 * 那么第i个节点的左孩子的编号为2*i+1,右孩子为2*i+2。
	 * 
	 * */
	void createTree(String strtree)
	{
		LinkQueue lQueue = new LinkQueue();
		lQueue.initQueue();
		/**
		 * 完全二叉树中第i层的结点的个数最多为第1到i-1层上所有节点的个数和
		 * 所以父节点的个数最多为N-1个,N表示节点个数
		 * */
		for(int parentIndex =0; parentIndex<strtree.split(" ").length/2;parentIndex++)
		{
			if(root == null)
			{
				root= new Node(strtree.split(" ")[parentIndex]);
				//左孩子
				root.lchild = new Node(strtree.split(" ")[parentIndex*2+1]);
				lQueue.enQueue(root.lchild);
				//右孩子
				root.rchild = new Node(strtree.split(" ")[parentIndex*2+2]);
				lQueue.enQueue(root.rchild);
			}else
			{
				if(!lQueue.isEmpty() && parentIndex*2+1<strtree.split(" ").length)//队列不空
				{
					node = (Node) lQueue.deQueue();
					if(parentIndex*2+1<strtree.split(" ").length)
					{
						//左孩子
						node.lchild = new Node(strtree.split(" ")[parentIndex*2+1]);
						lQueue.enQueue(node.lchild);
					}
					if(parentIndex*2+2<strtree.split(" ").length)
					{
						//右孩子
						node.rchild = new Node(strtree.split(" ")[parentIndex*2+2]);
						lQueue.enQueue(node.rchild);
					}
				}else
				{
					return;
				}
			}
		}
	}
	
	/**
	 * 先序遍历二叉树
	 * */
	void preOrderTraverse(Node node)
	{
		if(node == null)
		{
			return;
		}
		visit(node);
		preOrderTraverse(node.lchild);
		preOrderTraverse(node.rchild);
	}
	/**
	 * 中序遍历二叉树
	 * */
	void inOrderTraverse(Node node)
	{
		if(node == null)
		{
			return;
		}
		inOrderTraverse(node.lchild);
		visit(node);
		inOrderTraverse(node.rchild);
	}
	
	/**
	 * 非递归中序遍历二叉树
	 * */
	void inOrderTraverse2(Node node)
	{
		if(node == null)
		{
			return;
		}
		LinkStack lStack = new LinkStack();
		lStack.initStack();//初始化栈
		Node p =node;
		while(p!=null || !lStack.isEmpty())
		{
			if(p!=null)//遍历左子树,向左走到尽头,并将走过的节点入栈
			{
				lStack.push(p);
				p=p.lchild;
			}else//访问节点,向右走一步
			{
				p=(Node) lStack.pop();
				visit(p);
				p=p.rchild;
			}
		}
	}
	
	/**
	 * 后序遍历二叉树
	 * */
	void postOrderTraverse(Node node)
	{
		if(node == null)
		{
			return;
		}
		postOrderTraverse(node.lchild);
		postOrderTraverse(node.rchild);
		visit(node);
	}

	/**
	 * 打印二叉树
	 * */
	public void print()
	{
		System.out.print("先序遍历:");
		preOrderTraverse(root);
		System.out.print("\n中序遍历:");
		inOrderTraverse(root);
		System.out.print("\n非递归中序遍历:");
		inOrderTraverse2(root);
		System.out.print("\n后序遍历:");
		postOrderTraverse(root);
		
	}
	
	/**
	 * 访问节点
	 * */
	private void visit(Node node)
	{
		if(!node.data.equals("0"))
		{
			System.out.print(node.data);
		}
	}
}

  

测试类代码:

package binarytree;

public class BinaryTreeMain {

	public static void main(String[] args) {
		BinaryTree binaryTree = new BinaryTree();
		String strtree="- + / a * e f 0 0 b - 0 0 0 0 0 0 0 0 0 0 c d";//0表示没有值的位置
		binaryTree.createTree(strtree);
		binaryTree.print();
	}
}

  

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
一种从JSON数据创建Java类的高效办法
JSON格式的数据经常会遇到,比如调用Web服务,取回的数据通常就是JSON格式的。如何高效地把JSON数据转换成实际的Java类对象,就是本文要说明的问题。 写一个操纵JSON数据的Java程序,通常代码会重度依赖于JSON API,你总是需要对JSON数据进行反序列化,再转换成原生Java对象。
569 0
采用栈数据结构的二叉树非递归遍历
  【前言】树的遍历,根据访问自身和其子节点之间的顺序关系,分为前序,后序遍历。对于二叉树,每个节点至多有两个子节点(特别的称为左,右子节点),又有中序遍历。由于树自身具有的递归性,这些遍历函数使用递归函数很容易实现,代码也非常简洁。
892 0
怎么设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程
8478 0
intellij 创建java web项目(maven管理的SSH)
intellij 创建java web项目(maven管理的SSH) 环境intellij IDEA14、MAVEN、Spring、Struts2、Hibernate、Java Web。工程搭建。 1、创建maven项目 1、关闭现有项目,或者new progect 2、创建maven的web工程 3 4 5 2、添加web工程 6、添加web
1287 0
使用IntelliJ IDEA 14和Maven创建java web项目
原文:使用IntelliJ IDEA 14和Maven创建java web项目 http://mark.leanote.com/post/%E4%BD%BF%E7%94%A8IntelliJ-IDEA-14%E5%92%8CMaven%E5%88%9B%E5%BB%BAjava-web%E9%A1%B9%E7%9B%AE 安装Maven 下载安装 去maven官网下载最新版。
1283 0
+关注
云栖-lxl
java程序员
319
文章
2
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载