本文目录一览：
- 1、java构建二叉树算法
- 2、java实现二叉树层次遍历
- 3、写一个java层次遍历二叉树,简单点就可以,我要的是代码,不是纯文字说明
- 4、java一个关于二叉树的简单编程题
- 5、java Map 怎么遍历
java构建二叉树算法
//******************************************************************************************************//
//*****本程序包括简单的二叉树类的实现和前序,中序,后序,层次遍历二叉树算法,*******//
//******以及确定二叉树的高度,制定对象在树中的所处层次以及将树中的左右***********//
//******孩子节点对换位置,返回叶子节点个数删除叶子节点,并输出所删除的叶子节点**//
//*******************************CopyRight By phoenix*******************************************//
//************************************Jan 12,2008*************************************************//
//****************************************************************************************************//
public class BinTree {
public final static int MAX=40;
private Object data; //数据元数
private BinTree left,right; //指向左,右孩子结点的链
BinTree []elements = new BinTree[MAX];//层次遍历时保存各个节点
int front;//层次遍历时队首
int rear;//层次遍历时队尾
public BinTree()
{
}
public BinTree(Object data)
{ //构造有值结点
this.data = data;
left = right = null;
}
public BinTree(Object data,BinTree left,BinTree right)
{ //构造有值结点
this.data = data;
this.left = left;
this.right = right;
}
public String toString()
{
return data.toString();
}//前序遍历二叉树
public static void preOrder(BinTree parent){
if(parent == null)
return;
System.out.print(parent.data+" ");
preOrder(parent.left);
preOrder(parent.right);
}//中序遍历二叉树
public void inOrder(BinTree parent){
if(parent == null)
return;
inOrder(parent.left);
System.out.print(parent.data+" ");
inOrder(parent.right);
}//后序遍历二叉树
public void postOrder(BinTree parent){
if(parent == null)
return;
postOrder(parent.left);
postOrder(parent.right);
System.out.print(parent.data+" ");
}// 层次遍历二叉树
public void LayerOrder(BinTree parent)
{
elements[0]=parent;
front=0;rear=1;
while(frontrear)
{
try
{
if(elements[front].data!=null)
{
System.out.print(elements[front].data + " ");
if(elements[front].left!=null)
elements[rear++]=elements[front].left;
if(elements[front].right!=null)
elements[rear++]=elements[front].right;
front++;
}
}catch(Exception e){break;}
}
}//返回树的叶节点个数
public int leaves()
{
if(this == null)
return 0;
if(left == nullright == null)
return 1;
return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());
}//结果返回树的高度
public int height()
{
int heightOfTree;
if(this == null)
return -1;
int leftHeight = (left == null ? 0 : left.height());
int rightHeight = (right == null ? 0 : right.height());
heightOfTree = leftHeightrightHeight?rightHeight:leftHeight;
return 1 + heightOfTree;
}
//如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层
public int level(Object object)
{
int levelInTree;
if(this == null)
return -1;
if(object == data)
return 1;//规定根节点为第一层
int leftLevel = (left == null?-1:left.level(object));
int rightLevel = (right == null?-1:right.level(object));
if(leftLevel0rightLevel0)
return -1;
levelInTree = leftLevelrightLevel?rightLevel:leftLevel;
return 1+levelInTree;
}
//将树中的每个节点的孩子对换位置
public void reflect()
{
if(this == null)
return;
if(left != null)
left.reflect();
if(right != null)
right.reflect();
BinTree temp = left;
left = right;
right = temp;
}// 将树中的所有节点移走,并输出移走的节点
public void defoliate()
{
String innerNode = "";
if(this == null)
return;
//若本节点是叶节点，则将其移走
if(left==nullright == null)
{
System.out.print(this + " ");
data = null;
return;
}
//移走左子树若其存在
if(left!=null){
left.defoliate();
left = null;
}
//移走本节点，放在中间表示中跟移走...
innerNode += this + " ";
data = null;
//移走右子树若其存在
if(right!=null){
right.defoliate();
right = null;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BinTree e = new BinTree("E");
BinTree g = new BinTree("G");
BinTree h = new BinTree("H");
BinTree i = new BinTree("I");
BinTree d = new BinTree("D",null,g);
BinTree f = new BinTree("F",h,i);
BinTree b = new BinTree("B",d,e);
BinTree c = new BinTree("C",f,null);
BinTree tree = new BinTree("A",b,c);
System.out.println("前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍历二叉树结果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("后序遍历二叉树结果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的层次: "+tree.level("F"));
System.out.println("这棵二叉树的高度: "+tree.height());
System.out.println("--------------------------------------");
tree.reflect();
System.out.println("交换每个节点的孩子节点后......");
System.out.println("前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍历二叉树结果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("后序遍历二叉树结果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的层次: "+tree.level("F"));
System.out.println("这棵二叉树的高度: "+tree.height());
}
java实现二叉树层次遍历
import java.util.ArrayList;
public class TreeNode {
private TreeNode leftNode;
private TreeNode rightNode;
private String nodeName;
public TreeNode getLeftNode() {
return leftNode;
}
public void setLeftNode(TreeNode leftNode) {
this.leftNode = leftNode;
}
public TreeNode getRightNode() {
return rightNode;
}
public void setRightNode(TreeNode rightNode) {
this.rightNode = rightNode;
}
public String getNodeName() {
return nodeName;
}
public void setNodeName(String nodeName) {
this.nodeName = nodeName;
}
public static int level=0;
public static void findNodeByLevel(ArrayListTreeNode nodes){
if(nodes==null||nodes.size()==0){
return ;
}
level++;
ArrayListTreeNode temp = new ArrayList();
for(TreeNode node:nodes){
System.out.println("第"+level+"层:"+node.getNodeName());
if(node.getLeftNode()!=null){
temp.add(node.getLeftNode());
}
if(node.getRightNode()!=null){
temp.add(node.getRightNode());
}
}
nodes.removeAll(nodes);
findNodeByLevel(temp);
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeNode root = new TreeNode();
root.setNodeName("root");
TreeNode node1 = new TreeNode();
node1.setNodeName("node1");
TreeNode node3 = new TreeNode();
node3.setNodeName("node3");
TreeNode node7 = new TreeNode();
node7.setNodeName("node7");
TreeNode node8 = new TreeNode();
node8.setNodeName("node8");
TreeNode node4 = new TreeNode();
node4.setNodeName("node4");
TreeNode node2 = new TreeNode();
node2.setNodeName("node2");
TreeNode node5 = new TreeNode();
node5.setNodeName("node5");
TreeNode node6 = new TreeNode();
node6.setNodeName("node6");
root.setLeftNode(node1);
node1.setLeftNode(node3);
node3.setLeftNode(node7);
node3.setRightNode(node8);
node1.setRightNode(node4);
root.setRightNode(node2);
node2.setLeftNode(node5);
node2.setRightNode(node6);
ArrayListTreeNode nodes = new ArrayListTreeNode();
nodes.add(root);
findNodeByLevel(nodes);
}
}
写一个java层次遍历二叉树,简单点就可以,我要的是代码,不是纯文字说明
public class BinaryNode {
Object element;
BinaryNode left;
BinaryNode right;
}
import java.util.*;
public class Queue {
protected LinkedList list;
// Postcondition: this Queue object has been initialized.
public Queue() {
list = new LinkedList();
} // default constructor
// Postcondition: the number of elements in this Queue object has been
// returned.
public int size() {
return list.size();
} // method size
// Postcondition: true has been returned if this Queue object has no
// elements. Otherwise, false has been returned.
public boolean isEmpty() {
return list.isEmpty();
} // method isEmpty
// Postconditon: A copy of element has been inserted at the back of this
// Queue object. The averageTime (n) is constant and
// worstTime (n) is O (n).
public void enqueue(Object element) {
list.addLast(element);
} // method enqueue
// Precondition: this Queue object is not empty. Otherwise,
// NoSuchElementException will be thrown.
// Postcondition: The element that was at the front of this Queue object -
// just before this method was called -- has been removed
// from this Queue object and returned.
public Object dequeue() {
return list.removeFirst();
} // method dequeue
// Precondition: this Queue object is not empty. Otherwise,
// NoSuchElementException will be thrown.
// Postcondition: the element at index 0 in this Queue object has been
// returned.
public Object front() {
return list.getFirst();
} // method front
} // Queue class
import java.io.IOException;
public class BinaryTree {
BinaryNode root;
public BinaryTree() {
super();
// TODO 自动生成构造函数存根
root=this.createPre();
}
public BinaryNode createPre()
//按照先序遍历的输入方法，建立二叉树
{
BinaryNode t=null;
char ch;
try {
ch = (char)System.in.read();
if(ch==' ')
t=null;
else
{
t=new BinaryNode();
t.element=(Object)ch;
t.left=createPre();
t.right=createPre();
}
} catch (IOException e) {
// TODO 自动生成 catch 块
e.printStackTrace();
}
return t;
}
public void inOrder()
{
this.inOrder(root);
}
public void inOrder(BinaryNode t)
//中序遍历二叉树
{
if(t!=null)
{
inOrder(t.left);
System.out.print(t.element);
inOrder(t.right);
}
}
public void postOrder()
{
this.postOrder(root);
}
public void postOrder(BinaryNode t)
//后序遍历二叉树
{
if(t!=null)
{
postOrder(t.left);
System.out.print(t.element);
postOrder(t.right);
}
}
public void preOrder()
{
this.preOrder(root);
}
public void preOrder(BinaryNode t)
//前序遍历二叉树
{
if(t!=null)
{
System.out.print(t.element);
preOrder(t.left);
preOrder(t.right);
}
}
public void breadthFirst()
{
Queue treeQueue=new Queue();
BinaryNode p;
if(root!=null)
treeQueue.enqueue(root);
while(!treeQueue.isEmpty())
{
System.out.print(((BinaryNode)(treeQueue.front())).element);
p=(BinaryNode)treeQueue.dequeue();
if(p.left!=null)
treeQueue.enqueue(p.left);
if(p.right!=null)
treeQueue.enqueue(p.right);
}
}
}
public class BinaryTreeTest {
/**
* @param args
*/
public static void main(String[] args) {
// TODO 自动生成方法存根
BinaryTree tree = new BinaryTree();
System.out.println("先序遍历：");
tree.preOrder();
System.out.println();
System.out.println("中序遍历：");
tree.inOrder();
System.out.println();
System.out.println("后序遍历：");
tree.postOrder();
System.out.println();
System.out.println("层次遍历：");
tree.breadthFirst();
System.out.println();
}
}
java一个关于二叉树的简单编程题
定义一个结点类：
public class Node {
private int value;
private Node leftNode;
private Node rightNode;
public Node getRightNode() {
return rightNode;
}
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeftNode() {
return leftNode;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
}
初始化结点树：
public void initNodeTree()
{
int nodeNumber;
HashMapString, Integer map = new HashMapString, Integer();
Node nodeTree = new Node();
Scanner reader = new Scanner(System.in);
nodeNumber = reader.nextInt();
for(int i = 0; i nodeNumber; i++) {
int value = reader.nextInt();
String str = reader.next();
map.put(str, value);
}
if (map.containsKey("#")) {
int value = map.get("#");
nodeTree.setValue(value);
setChildNode(map, value, nodeTree);
}
preTraversal(nodeTree);
}
private void setChildNode(HashMapString, Integer map, int nodeValue, Node parentNode) {
int value = 0;
if (map.containsKey("L" + nodeValue)) {
value = map.get("L" + nodeValue);
Node leftNode = new Node();
leftNode.setValue(value);
parentNode.setLeftNode(leftNode);
setChildNode(map, value, leftNode);
}
if (map.containsKey("R" + nodeValue)) {
value = map.get("R" + nodeValue);
Node rightNode = new Node();
rightNode.setValue(value);
parentNode.setRightNode(rightNode);
setChildNode(map, value, rightNode);
}
}
前序遍历该结点树：
public void preTraversal(Node nodeTree) {
if (nodeTree != null) {
System.out.print(nodeTree.getValue() + "\t");
preTraversal(nodeTree.getLeftNode());
preTraversal(nodeTree.getRightNode());
}
}
java Map 怎么遍历
java Map 遍历一般有四种方式
方式一: 这是最常见的并且在大多数情况下也是最可取的遍历方式。在键值都需要时使用。
方式二： 在for-each循环中遍历keys或values。
如果只需要map中的键或者值，你可以通过keySet或values来实现遍历，而不是用entrySet。
该方法比entrySet遍历在性能上稍好（快了10%），而且代码更加干净。
方式三：使用Iterator遍历
使用泛型：
不使用泛型：
你也可以在keySet和values上应用同样的方法。
方法四: 通过键找值遍历（效率低）
作为方法一的替代，这个代码看上去更加干净；但实际上它相当慢且无效率。
因为从键取值是耗时的操作（与方法一相比，在不同的Map实现中该方法慢了20%~200%）。如果安装了FindBugs，它会做出检查并警告你关于哪些是低效率的遍历。所以尽量避免使用。
总结:
如果仅需要键(keys)或值(values)使用方法二。
如果所使用的语言版本低于java 5，或是打算在遍历时删除entries，必须使用方法三。
否则使用方法一(键值都要)。
扩展资料：
类似的遍历算法：
二叉树的遍历算法
1、先（根）序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
⑴ 访问根结点；
⑵ 遍历左子树；
⑶ 遍历右子树。
2、中（根）序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
⑴遍历左子树；
⑵访问根结点；
⑶遍历右子树。
3、后（根）序遍历得递归算法定义：
若二叉树非空，则依次执行如下操作：
⑴遍历左子树；
⑵遍历右子树；
⑶访问根结点。
参考资料：百度百科——Java
