import java.util.ArrayDeque;
public class BinaryTree {
static class TreeNode{
int value;
TreeNode left;
TreeNode right;
public TreeNode(int value){
this.value=value;
}
}
TreeNode root;
public BinaryTree(int[] array){
root=makeBinaryTreeByArray(array,1);
}
/**
* 采用递归的方式创建一颗二叉树
* 传入的是二叉树的数组表示法
* 构造后是二叉树的二叉链表表示法
*/
public static TreeNode makeBinaryTreeByArray(int[] array,int index){
if(index<array.length){
int value=array[index];
if(value!=0){
TreeNode t=new TreeNode(value);
array[index]=0;
t.left=makeBinaryTreeByArray(array,index*2);
t.right=makeBinaryTreeByArray(array,index*2+1);
return t;
}
}
return null;
}
/**
* 深度优先遍历,相当于先根遍历
* 采用非递归实现
* 需要辅助数据结构:栈
*/
public void depthOrderTraversal(){
if(root==null){
System.out.println("empty tree");
return;
}
ArrayDeque<TreeNode> stack=new ArrayDeque<TreeNode>();
stack.push(root);
while(stack.isEmpty()==false){
TreeNode node=stack.pop();
System.out.print(node.value+" ");
if(node.right!=null){
stack.push(node.right);
}
if(node.left!=null){
stack.push(node.left);
}
}
System.out.print("\n");
}
/**
* 广度优先遍历
* 采用非递归实现
* 需要辅助数据结构:队列
*/
public void levelOrderTraversal(){
if(root==null){
System.out.println("empty tree");
return;
}
ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();
queue.add(root);
while(queue.isEmpty()==false){
TreeNode node=queue.remove();
System.out.print(node.value+" ");
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
System.out.print("\n");
}
/**
* 13
* / \
* 65 5
* / \ \
* 97 25 37
* / /\ /
* 22 4 28 32
*/
public static void main(String[] args) {
int[] arr={0,13,65,5,97,25,0,37,22,0,4,28,0,0,32,0};
BinaryTree tree=new BinaryTree(arr);
tree.depthOrderTraversal();
tree.levelOrderTraversal();
}
}
- 浏览: 249865 次
- 性别:
- 来自: 深圳
最新评论
-
liliang880504:
bitnami_redmine_merge这个数据库是创建和合 ...
bitnami-redmine服务器迁移
相关推荐
java实现创建二叉树,并且遍历二叉树(此处使用递归方式遍历); 创建二叉树的方式有很多,此处使用线性的链表转化成二叉树,链表节点的顺序就是前序遍历的顺序,链表中的null值,代表二叉树左节点或者右节点为null...
java实现二叉树非递归前序中序后序遍历
该算法采用欧拉路径遍历二叉树,使用java语言实现的
遍历二叉树java代码
一个简单的课程设计,使用Java来实现二叉树的中序遍历
用java实现二叉树遍历 包括先序,中序,后序 后续是自己写的算法 可以运行
在Java中,实现二叉树的先序遍历可以通过递归来完成。先序遍历的顺序是:首先访问根节点,然后递归地先序遍历左子树,最后递归地先序遍历右子树。 在这段代码中,Node类定义了二叉树的节点,包含数据域和指向左右子...
建立二叉树,前后中序遍历二叉树,求二叉树的深度
java编程,二叉树的中序遍历,递归实现
java实现创建二叉树,并且遍历二叉树(此处使用非递归方式遍历); 用出栈入栈的方式遍历二叉树。
使用java语言,对数据结构中的二叉树进行遍历,包含算法逻辑。
非递归中序遍历二叉树
编写先序遍历二叉树的非递归算法程序,要求: (1)以二叉链表建立二叉树。 (2)输出遍历的结点序列。 (3)有实例验算。
java实现 二叉树的遍历 前序遍历用到递归, 中序和后序遍历用到栈, 其实还是有一定难度的
分层遍历二叉树
java语言实现的二叉树的各种操作(包括递归与非递归遍历二叉树,求二叉树的高度,节点总数,叶子节点等)
在Java中,实现二叉树的中序遍历同样可以通过递归来完成。中序遍历的顺序是:首先递归地中序遍历左子树,然后访问根节点,最后递归地中序遍历右子树。 在这段代码中,Node类定义了二叉树的节点,BinaryTree类包含一...
在Java中,实现二叉树的后序遍历可以通过递归来完成。后序遍历的顺序是:首先递归地遍历左子树,然后递归地遍历右子树,最后访问根节点。 在这段代码中,Node类定义了二叉树的节点,BinaryTree类包含一个指向根节点...
Java版二叉树遍历非递归程序,里面写的一般,希望大家喜欢!
NULL 博文链接:https://sun810.iteye.com/blog/1261373