写这篇完全就是为了后面的作业用的φ(>ω<*) ,代码都有测试过,虽然目前没有发现什么bug.
代码:
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
/**
* author : lwj
* createTime : 2019/2/15 20:07
* description : Reprint please indicate the source
*/
public class BinaryTree<T> {
private Node<T> root; // 根结点
public BinaryTree() {
}
/**
* 获取树的根结点
*
* @return
*/
public Node<T> getRoot() {
return root;
}
/**
* 判断树是否为空
*
* @return
*/
public boolean isEmpty() {
return root == null;
}
/**
* 插入结点
*
* @param item
* @param parentItem 父结点的值
* @param direction -1表示左,1表示右
*/
public void put(T item, T parentItem, int direction) {
Node<T> new_node = new Node<T>(item, null, null, null);
if (root == null) {
root = new_node;
} else {
Node<T> parentNode = find(parentItem);
if (direction == -1) {
new_node.left = parentNode.left;
parentNode.left = new_node;
new_node.parent = parentNode;
}
if (direction == 1) {
new_node.right = parentNode.right;
parentNode.right = new_node;
new_node.parent = parentNode;
}
}
}
/**
* 向指定结点插入左孩子
*
* @param parent
* @param item
*/
public void insertLeft(T parent, T item) {
Node<T> par_node = find(parent);
Node<T> left_node = new Node<T>(item, null, null, null);
if (par_node.left != null) {
left_node.left = par_node.left;
par_node.left = left_node;
par_node.left.parent = left_node;
left_node.parent = par_node;
} else {
par_node.left = left_node;
left_node.parent = par_node;
}
}
/**
* 向指定结点插入右孩子
*
* @param parent
* @param item
*/
public void insertRight(T parent, T item) {
Node<T> par_node = find(parent);
Node<T> right_node = new Node<T>(item, null, null, null);
if (par_node.right != null) {
right_node.right = par_node.right;
par_node.right = right_node;
par_node.right.parent = right_node;
right_node.parent = par_node;
} else {
par_node.right = right_node;
right_node.parent = par_node;
}
}
/**
* 查找指定结点
*
* @param item
* @return
*/
public Node<T> find(T item) {
return this.find(root, item);
}
private Node<T> find(Node<T> root, T item) {
Queue<Node<T>> queue = new LinkedList<Node<T>>();
Node<T> q_node = null;
queue.offer(root);
while (!queue.isEmpty()) {
q_node = queue.poll();
if (q_node.item.equals(item)) {
return q_node;
}
if (q_node.left != null) {
queue.offer(q_node.left);
}
if (q_node.right != null) {
queue.offer(q_node.right);
}
}
return null;
}
/**
* 删除结点
*
* @param item
* @return
*/
public boolean delete(T item) {
Node<T> temp_node = find(item);
if (temp_node == null) {
return false;
}
Node<T> par = temp_node.parent;
//如果要删除的是根结点
if (temp_node.item == this.root.item) {
clear();
}
//左子树
else if (par.left.item.equals(temp_node.item)) {
par.left = null;
}
//右子树
else {
par.right = null;
}
return true;
}
/**
* 清空树
*/
public void clear() {
this.root = null;
}
/**
* 获得二叉树的高
*
* @return
*/
public int getHeight() {
return getHeight(this.root);
}
private int getHeight(Node<T> root) {
if (root == null) {
return 0;
} else {
int leftH = getHeight(root.left);
int rightH = getHeight(root.right);
return (leftH > rightH ? leftH : rightH) + 1;
}
}
/**
* 求根结点到指定结点的路径
*
* @param item
*/
public void rootToNode(T item) {
Node<T> p_node = find(item);
if (p_node != null) {
this.rootToNode(p_node);
}
}
private void rootToNode(Node<T> x) {
if (x.parent != null) {
rootToNode(x.parent);
System.out.print("->" + x.item);
} else {
System.out.print(x.item);
}
}
/**
* 获取左子树
*
* @param item
* @return
*/
public Node<T> getLeft(T item) {
Node<T> p_node = find(item);
return p_node == null ? null : p_node.left;
}
/**
* 获取右子树
*
* @param item
* @return
*/
public Node<T> getRight(T item) {
Node<T> p_node = find(item);
return p_node == null ? null : p_node.right;
}
/**
* 统计叶子结点的个数
*
* @return
*/
public int statisticsLeafNodeCount() {
return this.statisticsLeafNodeCount(root);
}
private int statisticsLeafNodeCount(Node<T> x) {
int count = 0;
if (x == null) {
return 0;
} else if (x.left == null && x.right == null) {
return 1;
} else {
count = statisticsLeafNodeCount(x.left) + statisticsLeafNodeCount(x.right);
}
return count;
}
/**
* 判断是否是叶子结点
*
* @param item
* @return
*/
public boolean isLeafNode(T item) {
Node<T> p_node = find(item);
if (p_node.left == null && p_node.right == null) {
return true;
}
return false;
}
/**
* 获取所有结点个数
*
* @return
*/
public int statisticsNodeCount() {
Node<T> p_node = root;
return this.statisticsNodeCount(p_node);
}
private int statisticsNodeCount(Node<T> x) {
if (x == null) {
return 0;
} else {
return statisticsNodeCount(x.left) + statisticsNodeCount(x.right) + 1;
}
}
/**
* 将广义表转换为二叉树
*
* @param gLists
*/
public void createBinTreeByGLists(String gLists) {
this.root = (Node<T>) this.createByGList(gLists);
}
private Node<Character> createByGList(String gLists) {
Node<Character> root_node = null;
Node<Character> curr_node = null;
Stack<Node<Character>> stack = new Stack<Node<Character>>();
int flag = 0;
final int left = 1;
final int right = 2;
for (int i = 0; i < gLists.length(); i++) {
char ch = gLists.charAt(i);
switch (ch) {
case '(':
flag = left;
stack.push(curr_node);
break;
case ',':
flag = right;
break;
case ')':
stack.pop();
break;
case '^':
break;
default:
curr_node = new Node<Character>(ch, null, null, null);
if (root_node == null) {
root_node = curr_node;
} else {
if (flag == 1) {
stack.peek().left = curr_node;
} else {
stack.peek().right = curr_node;
}
}
}
}
return root_node;
}
/**
* 将二叉树表示为广义表
*/
public void toGeeneralizedList() {
this.toGeeneralizedList(root);
}
private void toGeeneralizedList(Node<T> root) {
System.out.print(root.item);
if (root.left != null) {
System.out.print("(");
toGeeneralizedList(root.left);
if (root.right == null) {
System.out.print(",^)");
}
}
if (root.right != null) {
if (root.left == null) {
System.out.print("(^");
}
System.out.print(",");
toGeeneralizedList(root.right);
System.out.print(")");
}
}
/**
* 判断是否为完全二叉树
*
* @return
*/
public boolean isCompleteTree() {
return this.isCompleteTree(root);
}
private boolean isCompleteTree(Node<T> root) {
Node<T> p_node = null;
Queue<Node<T>> queue = new LinkedList<Node<T>>();
queue.offer(root);
while ((p_node = queue.poll()) != null) {
queue.offer(p_node.left);
queue.offer(p_node.right);
}
while (!queue.isEmpty()) {
p_node = queue.poll();
if (p_node != null) {
return false;
}
}
return true;
}
/**
* 根据后序和中序遍历建立二叉树
*
* @param post 后续遍历集合
* @param in 中序遍历集合
* @return 树的根结点
*/
private Node<T> buildTree(T[] post, T[] in) {
int len = in.length;
return dfs(0, len - 1, 0, len - 1, post, in);
}
/**
* 递归构建树
*
* @param inl
* @param inr
* @param postl
* @param postr
* @param post
* @param in
* @return
*/
private Node<T> dfs(int inl, int inr, int postl, int postr, T[] post, T[] in) {
if (inl > inr || postl > postr) {
return null;
}
T val = post[postr];
int k = 0;
for (int i = inl; i < inr + 1; i++) {
if (in[i] == val) {
k = i;
break;
}
}
Node<T> root = new Node<T>(val, null, null, null);
// 第 4 个参数是计算出来的，依据：两边区间长度相等
root.left = dfs(inl, k - 1, postl, k - 1 - inl + postl, post, in);
// 第 3 个参数是计算出来的，依据：两边区间长度相等
root.right = dfs(k + 1, inr, postr + k - inr, postr - 1, post, in);
return root;
}
/**
* 前序遍历
*/
public void preOrderTraverse() {
this.preOrderTraverse(root);
}
private void preOrderTraverse(Node<T> root) {
if (root != null) {
System.out.print(root.item);
preOrderTraverse(root.left);
preOrderTraverse(root.right);
}
}
/**
* 前序遍历非递归
*/
public void preOrderByStack() {
this.preOrderByStack(root);
}
private void preOrderByStack(Node<T> root) {
Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> temp = root;
while(temp != null || !stack.empty()){
if(temp != null){
System.out.print(temp.item);
stack.push(temp);
temp = temp.left;
}else {
temp = stack.pop();
temp = temp.right;
}
}
}
/**
* 中序遍历
*/
public void inOrderTraverse() {
this.inOrderTraverse(root);
}
private void inOrderTraverse(Node<T> root) {
if (root != null) {
inOrderTraverse(root.left);
System.out.print(root.item);
inOrderTraverse(root.right);
}
}
/**
* 中序遍历非递归
*/
public void inOrderByStack(){
this.inOrderStack(root);
}
private void inOrderStack(Node<T> root){
Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> temp= root;
while(temp != null || !stack.empty()){
if(temp != null){
stack.push(temp);
temp = temp.left;
}else {
temp = stack.pop();
System.out.print(temp.item);
temp = temp.right;
}
}
}
/**
* 后序遍历
*/
private void postOrderTraverse() {
this.postOrderTraverse(root);
}
public void postOrderTraverse(Node<T> root) {
if (root != null) {
postOrderTraverse(root.left);
postOrderTraverse(root.right);
System.out.print(root.item);
}
}
/**
* 后序遍历非递归
*/
public void postOrderByStack(){
this.postOrderByStack(root);
}
private void postOrderByStack(Node<T> root){
Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> temp = root;
Node<T> lastNode = root;
while(temp != null || !stack.empty()){
while(temp != null){
stack.push(temp);
temp = temp.left;
}
temp = stack.peek();
if(temp.right == null || temp.right == lastNode){
System.out.print(temp.item);
stack.pop();
lastNode = temp;
temp = null;
}else {
temp = temp.right;
}
}
}
/**
* 层序遍历二叉树
*/
public void levelOrderTraverse() {
this.levelOrderTraverse(root);
}
private void levelOrderTraverse(Node<T> root) {
Node<T> temp = null;
Queue<Node<T>> queue = new LinkedList<Node<T>>();
queue.offer(root);
while (!queue.isEmpty()) {
temp = queue.poll();
System.out.print(temp.item);
if (null != temp.left)
queue.offer(temp.left);
if (null != temp.right) {
queue.offer(temp.right);
}
}
System.out.println();
}
/**
* 树的结点类
*
* @param <T>
*/
private class Node<T> {
Node<T> left;
Node<T> right;
Node<T> parent;
T item;
public Node(T item, Node<T> left, Node<T> right, Node<T> parent) {
this.left = left;
this.right = right;
this.parent = parent;
this.item = item;
}
}
public static void main(String[] args) {
// String str = "ABC.D.E..FG...H";
// char[] arr = str.toCharArray();
// BinaryTree<Character> binaryTree = new BinaryTree<Character>();
// for (int i = 0; i < arr.length; i++) {
// if (arr[i] != '.') {
// if (i % 2 == 0) {
// binaryTree.put(arr[i], arr[(i - 1) / 2], 1);
// } else {
// binaryTree.put(arr[i], arr[(i - 1) / 2], -1);
// }
// }
// }
// binaryTree.rootToNode('L');
// System.out.println(binaryTree.statisticsLeafNodeCount());
// System.out.println(binaryTree.getHeight());
// System.out.println(binaryTree.statisticsNodeCount());
// System.out.println(binaryTree.isCompleteTree());
// String str = "A(B(D(^,G),^),C(E,F))";
// BinaryTree<Character> binaryTree = new BinaryTree<Character>();
// binaryTree.createBinTreeByGLists(str);
// binaryTree.inOrderTraverse();
// Scanner sc = new Scanner(System.in);
// int n = sc.nextInt();
// Character[] post = new Character[n];
// Character[] in = new Character[n];
// for (int i = 0; i < n; i++) {
// post[i] = String.valueOf(sc.nextInt()).charAt(0);
// }
// for (int i = 0; i < n; i++) {
// in[i] = String.valueOf(sc.nextInt()).charAt(0);
// }
// System.out.print("Preorder:");
// BinaryTree<Character> binaryTree = new BinaryTree<>();
// binaryTree.preOrderTraverse(binaryTree.buildTree(post, in));
// System.out.println();
}
}
Q.E.D.
