站点图标

Java二叉树实现

2019-05-05折腾记录Java / 算法
本文最后更新于 607 天前,文中所描述的信息可能已发生改变

这是一篇水文,逃,代码已经经过一定的测试,但无法保证没有 Bug。介绍网上一大堆这里就不介绍了,直接放代码吧( ̄ ▽  ̄)”


_652
package MyTreeDemo;
_652
_652
import java.lang.reflect.Array;
_652
import java.util.ArrayList;
_652
import java.util.Arrays;
_652
import java.util.LinkedList;
_652
import java.util.List;
_652
import java.util.Scanner;
_652
_652
/**
_652
* MyTreeDemo
_652
*/
_652
public class MyTreeDemo {
_652
public static void main(String[] args) {
_652
Scanner in = new Scanner(System.in);
_652
// MyTree<Integer> tree = new MyTree<Integer>();
_652
// MyTree.Node temp = tree.addRoot(1);
_652
// tree.add(temp, -1, 2);
_652
// temp = tree.add(temp, 1, 3);
_652
// MyTree.Node temp1 = tree.add(temp, -1, 4);
_652
// MyTree.Node temp2 = tree.add(temp, 1, 5);
_652
// tree.add(temp2, -1, 6);
_652
// tree.add(temp2, 1, 7);
_652
// System.out.println(tree.layerOrder(false));
_652
// Object[] arr = tree.toArrayTree(-1);
_652
// Integer[] arr2 = new Integer[arr.length];
_652
// for (int i = 0; i < arr.length; i++) {
_652
// arr2[i] = (Integer)arr[i];
_652
// }
_652
// MyTree<Integer> tree2 = new MyTree<Integer>();
_652
// tree2.arrayToTree(arr2, -1);
_652
// System.out.println(tree2.layerOrder(false));
_652
// System.out.println(Arrays.toString(arr));
_652
// System.out.println(tree.search(tree.root, 4).data);
_652
// Character[] arr = {'A','B','C','D','.','E','F','.','G'};
_652
// MyTree<Character> tree = new MyTree<Character>();
_652
// tree.arrayToTree(arr, '.');
_652
// tree.layerOrder(true);
_652
// Object[] arr2 = tree.toArrayTree(' ');
_652
// System.out.println(Arrays.toString(arr2));
_652
// System.out.println(tree.LeafNodeList());
_652
while(in.hasNext()) {
_652
MyTree<String> tree = new MyTree<String>();
_652
tree.stringListsToTree(in.nextLine(), '(', ')', ',', "^");
_652
tree.preOrder(true);
_652
}
_652
in.close();
_652
}
_652
}
_652
_652
/**
_652
* MyTree
_652
*/
_652
class MyTree<T extends Comparable> {
_652
// 根节点
_652
Node root = null;
_652
// Build临时存放节点
_652
Node build = null;
_652
// 节点类
_652
class Node {
_652
// 父节点
_652
Node parent;
_652
// 左子树
_652
Node left;
_652
// 右子树
_652
Node right;
_652
// 数据域
_652
T data;
_652
_652
Node() {
_652
}
_652
_652
Node(T data) {
_652
this.data = data;
_652
}
_652
}
_652
_652
/**
_652
* 添加根节点
_652
*/
_652
public Node addRoot(T data) {
_652
this.root = new Node(data);
_652
return this.root;
_652
}
_652
_652
/**
_652
* 添加节点
_652
* @param Node root 添加节点的根节点
_652
* @param int LeftOrRight 添加方向 {-1:添加到左子树,1:添加到右子树}
_652
* @param T data 数据
_652
*/
_652
public Node add(Node root, int LeftOrRight, T data) {
_652
Node reNode = null;
_652
if (root == null) {
_652
this.root = new Node(data);
_652
reNode = this.root;
_652
} else if (LeftOrRight == -1) {
_652
root.left = new Node(data);
_652
root.left.parent = root;
_652
reNode = root.left;
_652
} else if (LeftOrRight == 1) {
_652
root.right = new Node(data);
_652
root.right.parent = root;
_652
reNode = root.right;
_652
}
_652
return reNode;
_652
}
_652
_652
/**
_652
* 添加节点
_652
* @param Node root 添加节点的根节点
_652
* @param int LeftOrRight 添加方向 {-1:添加到左子树,1:添加到右子树}
_652
* @param Node havaNode 要添加的节点
_652
*/
_652
public Node add(Node root, int LeftOrRight, Node havaNode) {
_652
Node reNode = havaNode;
_652
if (root == null) {
_652
this.root = havaNode;
_652
reNode = this.root;
_652
} else if (LeftOrRight == -1) {
_652
root.left = havaNode;
_652
root.left.parent = root;
_652
reNode = root.left;
_652
} else if (LeftOrRight == 1) {
_652
root.right = havaNode;
_652
root.right.parent = root;
_652
reNode = root.right;
_652
}
_652
return reNode;
_652
}
_652
_652
/**
_652
* 建立层次结构的二叉树 - 不完全版
_652
* 目前缺失功能:添加空节点
_652
*/
_652
public void buildAdd(Node root, T data) {
_652
// add this.root
_652
if(this.root == null) {
_652
this.root = new Node(data);
_652
this.build = this.root;
_652
return;
_652
}
_652
// add this.root.left or this.root.right
_652
if(root.parent == null) {
_652
if(root.left == null) {
_652
root.left = new Node(data);
_652
root.left.parent = root;
_652
this.build = root.left;
_652
return;
_652
} else {
_652
root.right = new Node(data);
_652
root.right.parent = root;
_652
this.build = root.right;
_652
return;
_652
}
_652
}
_652
if(root.parent.left == root) {
_652
root.parent.right = new Node(data);
_652
root.parent.right.parent = root.parent;
_652
this.build = root.parent.right;
_652
return;
_652
}
_652
if(root.parent.right == root) {
_652
root = root.parent;
_652
int i = 1;
_652
while (root.parent != null) {
_652
if(root.parent.left == root) {
_652
for (int j = 0; j < i; j++) {
_652
root = root.left;
_652
}
_652
root.left = new Node(data);
_652
root.left.parent = root;
_652
this.build = root.left;
_652
return;
_652
} else {
_652
root = root.parent;
_652
i++;
_652
}
_652
}
_652
while(true) {
_652
if(root.left == null) {
_652
root.left = new Node(data);
_652
root.left.parent = root;
_652
this.build = root.left;
_652
return;
_652
}
_652
root = root.left;
_652
}
_652
}
_652
}
_652
public boolean buildAdd(T data) {
_652
if(root != null && this.build == null) return false;
_652
// if(this.build == null) {
_652
// root = build
_652
this.buildAdd(this.build, data);
_652
// }
_652
return true;
_652
}
_652
_652
/**
_652
* 获取树高
_652
*/
_652
public int getHeight() {
_652
return this.getHeight(this.root);
_652
}
_652
_652
private int getHeight(Node root) {
_652
if (root == null) {
_652
return 0;
_652
} else {
_652
int leftHeight = this.getHeight(root.left);
_652
int rightHeight = this.getHeight(root.right);
_652
return leftHeight > rightHeight ? (leftHeight + 1) : (rightHeight + 1);
_652
}
_652
}
_652
_652
/**
_652
* 获取节点总数
_652
*/
_652
public int getSize() {
_652
return getSize(this.root);
_652
}
_652
_652
private int getSize(Node root) {
_652
if (root == null) {
_652
return 0;
_652
} else {
_652
return 1 + this.getSize(root.left) + this.getSize(root.right);
_652
}
_652
}
_652
_652
/**
_652
* 获取父节点
_652
* @param Node child 子节点
_652
*/
_652
public Node getParentNode(Node child) {
_652
if (child == null) {
_652
return null;
_652
} else {
_652
return child.parent;
_652
}
_652
}
_652
_652
/**
_652
* 获取左子树
_652
* @param Node root 父节点
_652
*/
_652
public Node getLeftChildNode(Node root) {
_652
if (root == null) {
_652
return null;
_652
} else {
_652
return root.left;
_652
}
_652
}
_652
_652
/**
_652
* 获取右子树
_652
* @param Node root 父节点
_652
*/
_652
public Node getRightChildNode(Node root) {
_652
if (root == null) {
_652
return null;
_652
} else {
_652
return root.right;
_652
}
_652
}
_652
_652
/**
_652
* 获取root树
_652
*/
_652
public Node getRoot() {
_652
return this.root;
_652
}
_652
_652
/**
_652
* 删除指定节点
_652
* @param Node root 父节点
_652
* @param int LeftOrRight 方向
_652
*/
_652
public void delete(Node root, int LeftOrRight) {
_652
if(root == null) {
_652
return;
_652
} else if(LeftOrRight == -1) {
_652
root.left = null;
_652
} else if(LeftOrRight == 1) {
_652
root.right = null;
_652
}
_652
}
_652
_652
/**
_652
* 销毁整棵树
_652
*/
_652
public void destroy() {
_652
if (root==null)
_652
return ;
_652
root = null;
_652
}
_652
_652
/**
_652
* 自动搜寻子树删除
_652
*/
_652
public void delete(Node root, Node target) {
_652
if(root == null) return;
_652
if(root.left == target) root.left = null;
_652
if(root.right == target) root.right = null;
_652
}
_652
_652
/**
_652
* 搜索节点
_652
* 需修改
_652
*/
_652
public Node search(Node root, T data) {
_652
if(root == null) {
_652
return null;
_652
} else if(root.data.compareTo(data) == 0) {
_652
return root;
_652
} else {
_652
Node temp = search(root.left, data);
_652
if(temp == null) {
_652
return search(root.right, data);
_652
} else {
_652
return temp;
_652
}
_652
}
_652
}
_652
_652
/**
_652
* 前序遍历
_652
*/
_652
private void preOrder(Node tree, List<T> list) {
_652
if(tree != null) {
_652
list.add(tree.data);
_652
preOrder(tree.left, list);
_652
preOrder(tree.right, list);
_652
}
_652
}
_652
public List<T> preOrder(boolean print) {
_652
List<T> list = new LinkedList<T>();
_652
preOrder(root, list);
_652
if(print) {
_652
System.out.println(list);
_652
return null;
_652
} else {
_652
return list;
_652
}
_652
}
_652
_652
/**
_652
* 中序遍历
_652
*/
_652
private void inOrder(Node tree, List<T> list) {
_652
if(tree != null) {
_652
inOrder(tree.left, list);
_652
list.add(tree.data);
_652
inOrder(tree.right, list);
_652
}
_652
}
_652
public List<T> inOrder(boolean print) {
_652
List<T> list = new LinkedList<T>();
_652
inOrder(root, list);
_652
if(print) {
_652
System.out.println(list);
_652
return null;
_652
} else {
_652
return list;
_652
}
_652
}
_652
_652
/**
_652
* 后序遍历
_652
*/
_652
private void postOrder(Node tree, List<T> list) {
_652
if(tree != null)
_652
{
_652
postOrder(tree.left, list);
_652
postOrder(tree.right, list);
_652
list.add(tree.data);
_652
}
_652
}
_652
public List<T> postOrder(boolean print) {
_652
List<T> list = new LinkedList<T>();
_652
postOrder(root, list);
_652
if(print) {
_652
System.out.println(list);
_652
return null;
_652
} else {
_652
return list;
_652
}
_652
}
_652
_652
/**
_652
* 层次遍历
_652
*/
_652
private void layerOrder(List<T> list) {
_652
if(root != null) {
_652
List<Node> queue = new LinkedList<Node>();
_652
queue.add(root);
_652
while (!queue.isEmpty()) {
_652
Node node = queue.remove(0);
_652
list.add(node.data);
_652
if(node.left != null) {
_652
queue.add(node.left);
_652
}
_652
if(node.right != null) {
_652
queue.add(node.right);
_652
}
_652
}
_652
}
_652
}
_652
public List<T> layerOrder(boolean print) {
_652
List<T> list = new LinkedList<T>();
_652
this.layerOrder(list);
_652
if(print) {
_652
System.out.println(list);
_652
return null;
_652
} else {
_652
return list;
_652
}
_652
}
_652
_652
/**
_652
* 普通二叉树转换为数组二叉树
_652
*/
_652
private void toArrayTree(Object[] array, Node root, int start, T emptyData) {
_652
int lnode = 2*start + 1;
_652
int rnode = 2*start + 2;
_652
if(start >= (int)(Math.pow(2, this.getHeight())-1)) return;
_652
if(root == null) {
_652
array[start] = emptyData;
_652
toArrayTree(array, null, lnode, emptyData);
_652
toArrayTree(array, null, rnode, emptyData);
_652
} else {
_652
array[start] = root.data;
_652
toArrayTree(array, root.left, lnode, emptyData);
_652
toArrayTree(array, root.right, rnode, emptyData);
_652
}
_652
}
_652
public Object[] toArrayTree(T emptyData) {
_652
Object[] array = new Object[(int)(Math.pow(2, this.getHeight())-1)];
_652
this.toArrayTree(array, this.root, 0, emptyData);
_652
return array;
_652
}
_652
_652
/**
_652
* 将数组二叉树转化为普通二叉树
_652
*/
_652
private Node arrayToTree(List<T> list, int start, T emptyData) {
_652
if(list.get(start).compareTo(emptyData) == 0) {
_652
return null;
_652
}
_652
Node root = new Node(list.get(start));
_652
int lnode = 2*start + 1;
_652
int rnode = 2*start + 2;
_652
if(lnode > list.size() -1) {
_652
root.left = null;
_652
} else {
_652
root.left = arrayToTree(list, lnode, emptyData);
_652
}
_652
if(rnode > list.size() -1) {
_652
root.right = null;
_652
} else {
_652
root.right = arrayToTree(list, rnode, emptyData);
_652
}
_652
return root;
_652
}
_652
public void arrayToTree(T[] array, T emptyData) {
_652
List<T> list = new LinkedList<T>(Arrays.asList(array));
_652
this.root = arrayToTree(list, 0, emptyData);
_652
}
_652
_652
/**
_652
* 将String广义表转换为二叉树
_652
*/
_652
private Node stringListsToTreeFun(String lists, char leftMark, char rightMark, char midMark, String emptyData) {
_652
if(lists.equals(emptyData)) return null;
_652
int index = lists.indexOf(leftMark);
_652
Node root = null;
_652
if(index == -1) {
_652
root = new Node((T)lists);
_652
return root;
_652
}
_652
root = new Node((T)lists.substring(0, index));
_652
List<Character> queue = new LinkedList<Character>();
_652
int midIndex = 0;
_652
int i = lists.indexOf(leftMark)+1;
_652
queue.add(leftMark);
_652
while(!queue.isEmpty()) {
_652
if(lists.charAt(i) == leftMark) {
_652
queue.add(leftMark);
_652
} else if(lists.charAt(i) == rightMark) {
_652
if(queue.get(queue.size()-1) == midMark && queue.get(queue.size()-2) == leftMark) {
_652
queue.remove(queue.size()-1);
_652
queue.remove(queue.size()-1);
_652
} else {
_652
queue.add(rightMark);
_652
}
_652
} else if(lists.charAt(i) == midMark) {
_652
if(queue.size() == 1) {
_652
midIndex = i;
_652
break;
_652
} else {
_652
queue.add(midMark);
_652
midIndex = i;
_652
}
_652
}
_652
i++;
_652
}
_652
root.left = stringListsToTreeFun(lists.substring(lists.indexOf(leftMark)+1, midIndex), leftMark, rightMark, midMark, emptyData);
_652
root.right = stringListsToTreeFun(lists.substring(midIndex+1, lists.lastIndexOf(rightMark)), leftMark, rightMark, midMark, emptyData);
_652
return root;
_652
}
_652
public void stringListsToTree(String lists, char leftMark, char rightMark, char midMark, String emptyData) {
_652
this.root = stringListsToTreeFun(lists, leftMark, rightMark, midMark, emptyData);
_652
}
_652
_652
/**
_652
* 将二叉树转换为String广义表
_652
*/
_652
private String toListsString(Node root, char leftMark, char rightMark, char midMark, String emptyData) {
_652
if(root != null) {
_652
if(root.left != null || root.right != null) {
_652
String leftString = emptyData;
_652
String rightString = emptyData;
_652
if(root.left != null) leftString = toListsString(root.left, leftMark, rightMark, midMark, emptyData);
_652
if(root.right != null) rightString = toListsString(root.right, leftMark, rightMark, midMark, emptyData);
_652
return root.data.toString()+leftMark+leftString+midMark+rightString+rightMark;
_652
} else {
_652
return root.data.toString();
_652
}
_652
}
_652
return "";
_652
}
_652
public String toListsString(char leftMark, char rightMark, char midMark, String emptyData) {
_652
return toListsString(this.root, leftMark, rightMark, midMark, emptyData);
_652
}
_652
_652
/**
_652
* 判断是否是叶节点
_652
*/
_652
public boolean isLeafNode(Node node) {
_652
if(node.left == null && node.right == null) {
_652
return true;
_652
} else {
_652
return false;
_652
}
_652
}
_652
_652
/**
_652
* 获得二叉树叶节点的个数
_652
*/
_652
public int LeafNodeSize() {
_652
if(root != null) {
_652
int size = 0;
_652
List<Node> queue = new LinkedList<Node>();
_652
queue.add(root);
_652
while (!queue.isEmpty()) {
_652
Node node = queue.remove(0);
_652
if(node.left == null && node.right == null) size++;
_652
if(node.left != null) {
_652
queue.add(node.left);
_652
}
_652
if(node.right != null) {
_652
queue.add(node.right);
_652
}
_652
}
_652
return size;
_652
}
_652
return 0;
_652
}
_652
_652
/**
_652
* 获得叶节点列表,层次遍历
_652
*/
_652
public List<T> LeafNodeList() {
_652
if(root != null) {
_652
List<T> list = new LinkedList<T>();
_652
List<Node> queue = new LinkedList<Node>();
_652
queue.add(root);
_652
while (!queue.isEmpty()) {
_652
Node node = queue.remove(0);
_652
if(node.left == null && node.right == null) {
_652
list.add(node.data);
_652
}
_652
if(node.left != null) {
_652
queue.add(node.left);
_652
}
_652
if(node.right != null) {
_652
queue.add(node.right);
_652
}
_652
}
_652
return list;
_652
}
_652
return null;
_652
}
_652
_652
/**
_652
* 获得叶节点列表,中序遍历
_652
*/
_652
private void inLeafNodeList(Node tree, List<T> list) {
_652
if(tree != null) {
_652
inLeafNodeList(tree.left, list);
_652
if(tree.left == null && tree.right == null) {
_652
list.add(tree.data);
_652
}
_652
inLeafNodeList(tree.right, list);
_652
}
_652
}
_652
public List<T> inLeafNodeList() {
_652
if(root != null) {
_652
List<T> list = new LinkedList<T>();
_652
this.inLeafNodeList(this.root, list);
_652
return list;
_652
}
_652
return null;
_652
}
_652
_652
/**
_652
* 判断是否是完全二叉树
_652
*/
_652
public boolean isGoodTree() {
_652
if(root != null) {
_652
List<Node> queue = new LinkedList<Node>();
_652
queue.add(root);
_652
while(!queue.isEmpty()) {
_652
Node node = queue.remove(0);
_652
if(node != null) {
_652
if(node.left != null) {
_652
queue.add(node.left);
_652
}
_652
if(node.right != null) {
_652
queue.add(node.right);
_652
}
_652
if(node.left == null && node.right != null) {
_652
return false;
_652
}
_652
if (node.left == null && node.right == null) {
_652
while (!queue.isEmpty()) {
_652
node = queue.get(0);
_652
if((node.left != null && node.right == null) || (node.left == null && node.right == null)) {
_652
queue.remove(0);
_652
} else {
_652
return false;
_652
}
_652
}
_652
return true;
_652
}}
_652
}
_652
return true;
_652
}
_652
return false;
_652
}
_652
}

Java二叉树实现

https://blog.ixk.me/post/java-binary-tree-implementation
  • 许可协议

    BY-NC-SA

  • 发布于

    2019-05-05

  • 本文作者

    Otstar Lin

转载或引用本文时请遵守许可协议,注明出处、不得用于商业用途!

ace编辑器设置惯性滚动Java图实现