Question

java上机实验题，要求用java编写，完成其中随便一个就行，急求，能加多少分我就给多少分！！！

Answer 1

package testTime;

import java.util.LinkedList;

public class BinaryTree {
//根节点
private Node<Integer> root;

//二叉树中节点数量
private int size;

//无参构造器
public BinaryTree() {
root = new Node<Integer>();
}

//数组构造器
public BinaryTree(int[] values) {
System.out.print("新建binaryTree:");
for (int i : values) {
System.out.print(i);
}
System.out.println();
boolean isLeft = true;
int len = values.length;
if (len == 0)
return ;
LinkedList<Node<Integer>> queue = new LinkedList<Node<Integer>>();
root = new Node<Integer>(values[0]);
queue.addLast(root);
Node parent = null;
Node current = null;
for (int i=1; i<len; i++) {
current = new Node<Integer>(values[i]);
queue.addLast(current);
if (isLeft)
parent = queue.getFirst();
else
parent = queue.removeFirst();
if (isLeft) {
parent.setLeftChild(current);
isLeft = false;
}else {
parent.setRightChild(current);
isLeft = true;
}
}
}

//递归中序遍历
public void inorder() {
System.out.print("binaryTree递归中序遍历:");
inorderTraverseRecursion(root);
System.out.println();
}

//层次遍历
public void layerorder() {
System.out.print("binaryTree层次遍历:");
LinkedList<Node<Integer>> queue = new LinkedList<Node<Integer>>();
queue.addLast(root);
Node<Integer> current = null;
while(!queue.isEmpty()) {
current = queue.removeFirst();
if (current.getLeftChild() != null)
queue.addLast(current.getLeftChild());
if (current.getRightChild() != null)
queue.addLast(current.getRightChild());
System.out.print(current.getValue());
}
System.out.println();
}

//获得二叉树深度
public int getDepth() {
return getDepthRecursion(root);
}

private int getDepthRecursion(Node<Integer> node){
if (node == null)
return 0;
int llen = getDepthRecursion(node.getLeftChild());
int rlen = getDepthRecursion(node.getRightChild());
int maxlen = Math.max(llen, rlen);
return maxlen + 1;
}
//递归先序遍历
public void preorder() {
System.out.print("binaryTree递归先序遍历:");
preorderTraverseRecursion(root);
System.out.println();
}

private void inorderTraverseRecursion(Node<Integer> node) {
// TODO Auto-generated method stub
if (node.getLeftChild() != null)
inorderTraverseRecursion(node.getLeftChild());
System.out.print(node.getValue());
if (node.getRightChild() != null)
inorderTraverseRecursion(node.getRightChild());
}

private void preorderTraverseRecursion(Node<Integer> node){
System.out.print(node.getValue());
if (node.getLeftChild() != null)
preorderTraverseRecursion (node.getLeftChild());
if (node.getRightChild() != null)
preorderTraverseRecursion (node.getRightChild());
}

//非递归先序遍历
public void preorderNoRecursion() {
System.out.print("binaryTree非递归先序遍历:");
LinkedList<Node<Integer>> stack = new LinkedList<Node<Integer>>();
stack.push(root);
Node<Integer> current = null;
while (!stack.isEmpty()) {
current = stack.pop();
System.out.print(current.getValue());
if (current.getRightChild() != null)
stack.push(current.getRightChild());
if (current.getLeftChild() != null)
stack.push(current.getLeftChild());
}
System.out.println();
}

/**
* 非递归中序遍历
* 栈内保存将要访问的元素
*/
public void inorderNoRecursion() {
System.out.print("binaryTree非递归中序遍历:");
LinkedList<Node<Integer>> stack = new LinkedList<Node<Integer>>();
Node<Integer> current = root;
while (current != null || !stack.isEmpty()) {
while(current != null) {
stack.push(current);
current = current.getLeftChild();
}
if (!stack.isEmpty()) {
current = stack.pop();
System.out.print(current.getValue());
current = current.getRightChild();
}
}
System.out.println();
}

/**
* 非递归后序遍历

* 当上一个访问的结点是右孩子或者当前结点没有右孩子则访问当前结点
*/
public void postorderNoRecursion() {
System.out.print("binaryTree非递归后序遍历:");
Node<Integer> rNode = null;
Node<Integer> current = root;
LinkedList<Node<Integer>> stack = new LinkedList<Node<Integer>>();
while(current != null || !stack.isEmpty()) {
while(current != null) {
stack.push(current);
current = current.getLeftChild();
}
current = stack.pop();
while (current != null && (current.getRightChild() == null ||current.getRightChild() == rNode)) {
System.out.print(current.getValue());
rNode = current;
if (stack.isEmpty()){
System.out.println();
return;
}
current = stack.pop();
}
stack.push(current);
current = current.getRightChild();
}

}

public static void main(String[] args) {
BinaryTree bt = new BinaryTree(new int[]{1,2,3,4,5,6,7,8});
bt.inorder();
bt.preorder();
bt.layerorder();
bt.preorderNoRecursion();
bt.inorderNoRecursion();
bt.postorderNoRecursion();
System.out.println("深度为：" + bt.getDepth());
}
}

class Node<V>{
private V value;
private Node<V> leftChild;
private Node<V> rightChild;

public Node(){
};

public Node(V value) {
this.value = value;
leftChild = null;
rightChild = null;
}

public void setLeftChild(Node<V> lNode) {
this.leftChild = lNode;
}

public void setRightChild(Node<V> rNode) {
this.rightChild = rNode;
}

public V getValue() {
return value;
}

public void setValue(V value) {
this.value = value;
}

public Node<V> getLeftChild() {
return leftChild;
}

public Node<V> getRightChild() {
return rightChild;
}

}

追问

真的非常感谢！手机我没找到多给分的地方…你知道怎么缩格打印吗

Answer 2

/*做个记录*/
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Queue;
import java.util.Random;
public class BitLinkTree {
private int nodeNameStart = 1;
private Node root;
private int treeLevel;
private transient Random random = new Random();
private char[] generateLeftRightChildFlag = { 'L', 'R', 'A' };
public BitLinkTree() {
}
public static void main(String[] args) {
BitLinkTree bt = new BitLinkTree();
bt.createTree(15);
System.out.println("生成树如下：");
System.out.println(bt);
System.out.println("前序遍历，递归：");
bt.printRecursivePreorderTraversalWithSpace();
System.out.println("前序遍历，非递归：");
bt.printNonRecursivePreorderTraversalWithSpace();
System.out.println("交互左右节点：");
bt.exchangeLeftRightChild();
System.out.println(bt);
}
/**
* 创建一棵树
* @param nodeCount 节点总数
*/
public void createTree(int nodeCount) {
this.root = generateRoot();
int hasGenNodeCount = 1;
Queue<Node> waitGenChildNodes = new ArrayDeque<>();
waitGenChildNodes.add(root);
int lastNeedGenNodeCountMax = 2;
int cycleGenNodeCount = nodeCount - lastNeedGenNodeCountMax;
while (hasGenNodeCount < cycleGenNodeCount) {
for (int i = 0, len = waitGenChildNodes.size(); i < len; i++) {
Node parent = waitGenChildNodes.poll();
int childCount = randomGenerateLefRightChild(parent);
if (parent.leftChild != null) {
waitGenChildNodes.add(parent.leftChild);
}
if (parent.rightChild != null) {
waitGenChildNodes.add(parent.rightChild);
}
hasGenNodeCount += childCount;
}
}
int lastNeedGenNodeCount = nodeCount - hasGenNodeCount;
Node parent = waitGenChildNodes.poll();
if (lastNeedGenNodeCount > 1) {
generateRightChild(parent);
} else if (lastNeedGenNodeCount > 0) {
generateLeftChild(parent);
}
}

private Node generateRoot() {
Node root = createNodeOrderNumber();
root.level = 1;
treeLevel = root.level;
return root;
}
/**
* 给某个节点按概率生成左、右孩子。1:1:2
* @param parent 目标节点
* @return 孩子节点数量
*/
private int randomGenerateLefRightChild(Node parent) {
char genLeftRightChildFlag = randomLeftRightChildFlag();
int childCount = 0;
if (genLeftRightChildFlag == generateLeftRightChildFlag[0]
|| genLeftRightChildFlag == generateLeftRightChildFlag[2]) {
generateLeftChild(parent);
childCount++;
}
if (genLeftRightChildFlag == generateLeftRightChildFlag[1]
|| genLeftRightChildFlag == generateLeftRightChildFlag[2]) {
generateRightChild(parent);
childCount++;
}
return childCount;
}
private void generateLeftChild(Node parent) {
Node leftChild = createNodeOrderNumber();
parent.leftChild = leftChild;
setNodeParentRelation(leftChild, parent);
}
private void generateRightChild(Node parent) {
Node rightChild = createNodeOrderNumber();
parent.rightChild = rightChild;
setNodeParentRelation(rightChild, parent);
}
private void setNodeParentRelation(Node node, Node parent) {
node.parent = parent;
node.level = parent.level + 1;
if (treeLevel < node.level) {
treeLevel = node.level;
}
}
private char randomLeftRightChildFlag() {
int secondBit = random.nextInt(2);
int index = secondBit == 1 ? secondBit << 1 : random.nextInt(2);
return generateLeftRightChildFlag[index];
}
/**
* 按自增序号方式生成节点
*/
private Node createNodeOrderNumber() {
Node node = new Node();
node.name = String.valueOf(nodeNameStart++);
return node;
}
/**
* 缩格打印递归前序遍历树结果
*/
public void printRecursivePreorderTraversalWithSpace() {
List<Node> res = preorderRecursiveTraversalTree();
printNodesWithSpace(res);
}
public void printNonRecursivePreorderTraversalWithSpace() {
List<Node> res = preorderNonRecursiveTraversalTree();
printNodesWithSpace(res);
}
private void printNodesWithSpace(List<Node> nodes) {
for (int i = 0, len = nodes.size(); i < len; i++) {
System.out.print(" ");
System.out.print(nodes.get(i).name);
}
System.out.println();
}
/**
* 前序遍历树，递归
*/
public List<Node> preorderRecursiveTraversalTree() {
List<Node> traversalResult = new ArrayList<>();
preorderRecursiveTraversalNode(root, traversalResult);
return traversalResult;
}
/**
* 前序遍历某个节点，递归
* @param node 要遍历的目标节点
* @param traversalResult 遍历该节点前的结果
*/
private void preorderRecursiveTraversalNode(Node node, List<Node> traversalResult) {
traversalResult.add(node);
if (node.leftChild != null) {
preorderRecursiveTraversalNode(node.leftChild, traversalResult);
}
if (node.rightChild != null) {
preorderRecursiveTraversalNode(node.rightChild, traversalResult);
}
}
public List<Node> preorderNonRecursiveTraversalTree() {
return preorderNonRecursiveTraversalNode(root);
}
/**
* 前序遍历某个节点，非递归
*/
private List<Node> preorderNonRecursiveTraversalNode(Node node) {
List<Node> traversalResult = new ArrayList<>();
Deque<Node> stack = new ArrayDeque<>();
stack.addFirst(node);
while (!stack.isEmpty()) {
Node stackHead = stack.removeFirst();
traversalResult.add(stackHead);
if (stackHead.rightChild != null) {
stack.addFirst(stackHead.rightChild);
}
if (stackHead.leftChild != null) {
stack.addFirst(stackHead.leftChild);
}
}
return traversalResult;
}
/**
* 交互节点左右子节点
*/
public void exchangeLeftRightChild() {
List<Node> needExchangeNodes = new ArrayList<>();
Queue<Node> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
Node head = queue.poll();
if (head.level < treeLevel) {
boolean hasChild = false;
if (head.leftChild != null) {
queue.add(head.leftChild);
hasChild = true;
}
if (head.rightChild != null) {
queue.add(head.rightChild);
hasChild = true;
}
if (hasChild) {
needExchangeNodes.add(head);
}
}
}
for (int i = 0, len = needExchangeNodes.size(); i < len; i++) {
Node node = needExchangeNodes.get(i);
Node leftChildOld = node.leftChild;
node.leftChild = node.rightChild;
node.rightChild = leftChildOld;
}
}
private List<Node> levelTraversalTree() {
List<Node> result = new ArrayList<>();
Queue<Node> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
Node head = queue.poll();
result.add(head);
if (head.leftChild != null) {
queue.add(head.leftChild);
}
if (head.rightChild != null) {
queue.add(head.rightChild);
}
}
return result;
}
public String toString(){
String[] connectors = { "[", "]", ",", "L:", "R:" };
StringBuilder buf=new StringBuilder();
buf.append("root");
List<Node> allNodes = levelTraversalTree();
for (int i = 0, len = allNodes.size(); i < len; i++) {
Node node = allNodes.get(i);
buf.append(connectors[0]).append(node.name);
buf.append(connectors[2]).append(connectors[3])
.append(node.leftChild != null ? node.leftChild.name : "null");
buf.append(connectors[2]).append(connectors[4])
.append(node.rightChild != null ? node.rightChild.name : "null");
buf.append(connectors[1]);
}
return buf.toString();
}
class Node {
private String name;
private Node parent;
private Node leftChild;
private Node rightChild;
private int level;//在树中层级，根节点为1
}
}