用java怎么构造一个二叉树？

Question

如题所述

Answer 1

二叉树的相关操作，包括创建，中序、先序、后序（递归和非递归），其中重点的是java在先序创建二叉树和后序非递归遍历的的实现。
package com.algorithm.tree;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

public class Tree {

private Node root;

public Tree() {
}

public Tree(Node root) {
this.root = root;
}

//创建二叉树
public void buildTree() {

Scanner scn = null;
try {
scn = new Scanner(new File("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
root = createTree(root,scn);
}
//先序遍历创建二叉树
private Node createTree(Node node,Scanner scn) {

String temp = scn.next();

if (temp.trim().equals("#")) {
return null;
} else {
node = new Node((T)temp);
node.setLeft(createTree(node.getLeft(), scn));
node.setRight(createTree(node.getRight(), scn));
return node;
}

}

//中序遍历(递归)
public void inOrderTraverse() {
inOrderTraverse(root);
}

public void inOrderTraverse(Node node) {
if (node != null) {
inOrderTraverse(node.getLeft());
System.out.println(node.getValue());
inOrderTraverse(node.getRight());
}
}

//中序遍历(非递归)
public void nrInOrderTraverse() {

Stack<Node> stack = new Stack<Node>();
Node node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
node = stack.pop();
System.out.println(node.getValue());
node = node.getRight();

}

}
//先序遍历(递归)
public void preOrderTraverse() {
preOrderTraverse(root);
}

public void preOrderTraverse(Node node) {
if (node != null) {
System.out.println(node.getValue());
preOrderTraverse(node.getLeft());
preOrderTraverse(node.getRight());
}
}

//先序遍历（非递归）
public void nrPreOrderTraverse() {

Stack<Node> stack = new Stack<Node>();
Node node = root;

while (node != null || !stack.isEmpty()) {

while (node != null) {
System.out.println(node.getValue());
stack.push(node);
node = node.getLeft();
}
node = stack.pop();
node = node.getRight();
}

}

//后序遍历(递归)
public void postOrderTraverse() {
postOrderTraverse(root);
}

public void postOrderTraverse(Node node) {
if (node != null) {
postOrderTraverse(node.getLeft());
postOrderTraverse(node.getRight());
System.out.println(node.getValue());
}
}

//后续遍历(非递归)
public void nrPostOrderTraverse() {

Stack<Node> stack = new Stack<Node>();
Node node = root;
Node preNode = null;//表示最近一次访问的节点

while (node != null || !stack.isEmpty()) {

while (node != null) {
stack.push(node);
node = node.getLeft();
}

node = stack.peek();

if (node.getRight() == null || node.getRight() == preNode) {
System.out.println(node.getValue());
node = stack.pop();
preNode = node;
node = null;
} else {
node = node.getRight();
}

}

}

//按层次遍历
public void levelTraverse() {
levelTraverse(root);
}

public void levelTraverse(Node node) {

Queue<Node> queue = new LinkedBlockingQueue<Node>();
queue.add(node);
while (!queue.isEmpty()) {

Node temp = queue.poll();
if (temp != null) {
System.out.println(temp.getValue());
queue.add(temp.getLeft());
queue.add(temp.getRight());
}

}

}

}

//树的节点

class Node {

private Node left;
private Node right;
private T value;

public Node() {
}
public Node(Node left,Node right,T value) {
this.left = left;
this.right = right;
this.value = value;
}

public Node(T value) {
this(null,null,value);
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}

}
测试代码：
package com.algorithm.tree;

public class TreeTest {

/**
* @param args
*/
public static void main(String[] args) {
Tree tree = new Tree();
tree.buildTree();
System.out.println("中序遍历");
tree.inOrderTraverse();
tree.nrInOrderTraverse();
System.out.println("后续遍历");
//tree.nrPostOrderTraverse();
tree.postOrderTraverse();
tree.nrPostOrderTraverse();
System.out.println("先序遍历");
tree.preOrderTraverse();
tree.nrPreOrderTraverse();

//
}

}

Answer 2

定义一个结点类：
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;
HashMap<String, Integer> map = new HashMap<String, 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(HashMap<String, 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());
}
}本回答被网友采纳