这是一篇水文，逃，代码已经经过一定的测试，但无法保证没有 Bug。介绍网上一大堆这里就不介绍了，直接放代码吧(￣ ▽ ￣)"
package MyTreeDemo;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
/**
* MyTreeDemo
*/
public class MyTreeDemo {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// MyTree<Integer> tree = new MyTree<Integer>();
// MyTree.Node temp = tree.addRoot(1);
// tree.add(temp, -1, 2);
// temp = tree.add(temp, 1, 3);
// MyTree.Node temp1 = tree.add(temp, -1, 4);
// MyTree.Node temp2 = tree.add(temp, 1, 5);
// tree.add(temp2, -1, 6);
// tree.add(temp2, 1, 7);
// System.out.println(tree.layerOrder(false));
// Object[] arr = tree.toArrayTree(-1);
// Integer[] arr2 = new Integer[arr.length];
// for (int i = 0; i < arr.length; i++) {
// arr2[i] = (Integer)arr[i];
// }
// MyTree<Integer> tree2 = new MyTree<Integer>();
// tree2.arrayToTree(arr2, -1);
// System.out.println(tree2.layerOrder(false));
// System.out.println(Arrays.toString(arr));
// System.out.println(tree.search(tree.root, 4).data);
// Character[] arr = {'A','B','C','D','.','E','F','.','G'};
// MyTree<Character> tree = new MyTree<Character>();
// tree.arrayToTree(arr, '.');
// tree.layerOrder(true);
// Object[] arr2 = tree.toArrayTree(' ');
// System.out.println(Arrays.toString(arr2));
// System.out.println(tree.LeafNodeList());
while(in.hasNext()) {
MyTree<String> tree = new MyTree<String>();
tree.stringListsToTree(in.nextLine(), '(', ')', ',', "^");
tree.preOrder(true);
}
in.close();
}
}
/**
* MyTree
*/
class MyTree<T extends Comparable> {
// 根节点
Node root = null;
// Build临时存放节点
Node build = null;
// 节点类
class Node {
// 父节点
Node parent;
// 左子树
Node left;
// 右子树
Node right;
// 数据域
T data;
Node() {
}
Node(T data) {
this.data = data;
}
}
/**
* 添加根节点
*/
public Node addRoot(T data) {
this.root = new Node(data);
return this.root;
}
/**
* 添加节点
* @param Node root 添加节点的根节点
* @param int LeftOrRight 添加方向 {-1:添加到左子树,1:添加到右子树}
* @param T data 数据
*/
public Node add(Node root, int LeftOrRight, T data) {
Node reNode = null;
if (root == null) {
this.root = new Node(data);
reNode = this.root;
} else if (LeftOrRight == -1) {
root.left = new Node(data);
root.left.parent = root;
reNode = root.left;
} else if (LeftOrRight == 1) {
root.right = new Node(data);
root.right.parent = root;
reNode = root.right;
}
return reNode;
}
/**
* 添加节点
* @param Node root 添加节点的根节点
* @param int LeftOrRight 添加方向 {-1:添加到左子树,1:添加到右子树}
* @param Node havaNode 要添加的节点
*/
public Node add(Node root, int LeftOrRight, Node havaNode) {
Node reNode = havaNode;
if (root == null) {
this.root = havaNode;
reNode = this.root;
} else if (LeftOrRight == -1) {
root.left = havaNode;
root.left.parent = root;
reNode = root.left;
} else if (LeftOrRight == 1) {
root.right = havaNode;
root.right.parent = root;
reNode = root.right;
}
return reNode;
}
/**
* 建立层次结构的二叉树 - 不完全版
* 目前缺失功能：添加空节点
*/
public void buildAdd(Node root, T data) {
// add this.root
if(this.root == null) {
this.root = new Node(data);
this.build = this.root;
return;
}
// add this.root.left or this.root.right
if(root.parent == null) {
if(root.left == null) {
root.left = new Node(data);
root.left.parent = root;
this.build = root.left;
return;
} else {
root.right = new Node(data);
root.right.parent = root;
this.build = root.right;
return;
}
}
if(root.parent.left == root) {
root.parent.right = new Node(data);
root.parent.right.parent = root.parent;
this.build = root.parent.right;
return;
}
if(root.parent.right == root) {
root = root.parent;
int i = 1;
while (root.parent != null) {
if(root.parent.left == root) {
for (int j = 0; j < i; j++) {
root = root.left;
}
root.left = new Node(data);
root.left.parent = root;
this.build = root.left;
return;
} else {
root = root.parent;
i++;
}
}
while(true) {
if(root.left == null) {
root.left = new Node(data);
root.left.parent = root;
this.build = root.left;
return;
}
root = root.left;
}
}
}
public boolean buildAdd(T data) {
if(root != null && this.build == null) return false;
// if(this.build == null) {
// root = build
this.buildAdd(this.build, data);
// }
return true;
}
/**
* 获取树高
*/
public int getHeight() {
return this.getHeight(this.root);
}
private int getHeight(Node root) {
if (root == null) {
return 0;
} else {
int leftHeight = this.getHeight(root.left);
int rightHeight = this.getHeight(root.right);
return leftHeight > rightHeight ? (leftHeight + 1) : (rightHeight + 1);
}
}
/**
* 获取节点总数
*/
public int getSize() {
return getSize(this.root);
}
private int getSize(Node root) {
if (root == null) {
return 0;
} else {
return 1 + this.getSize(root.left) + this.getSize(root.right);
}
}
/**
* 获取父节点
* @param Node child 子节点
*/
public Node getParentNode(Node child) {
if (child == null) {
return null;
} else {
return child.parent;
}
}
/**
* 获取左子树
* @param Node root 父节点
*/
public Node getLeftChildNode(Node root) {
if (root == null) {
return null;
} else {
return root.left;
}
}
/**
* 获取右子树
* @param Node root 父节点
*/
public Node getRightChildNode(Node root) {
if (root == null) {
return null;
} else {
return root.right;
}
}
/**
* 获取root树
*/
public Node getRoot() {
return this.root;
}
/**
* 删除指定节点
* @param Node root 父节点
* @param int LeftOrRight 方向
*/
public void delete(Node root, int LeftOrRight) {
if(root == null) {
return;
} else if(LeftOrRight == -1) {
root.left = null;
} else if(LeftOrRight == 1) {
root.right = null;
}
}
/**
* 销毁整棵树
*/
public void destroy() {
if (root==null)
return ;
root = null;
}
/**
* 自动搜寻子树删除
*/
public void delete(Node root, Node target) {
if(root == null) return;
if(root.left == target) root.left = null;
if(root.right == target) root.right = null;
}
/**
* 搜索节点
* 需修改
*/
public Node search(Node root, T data) {
if(root == null) {
return null;
} else if(root.data.compareTo(data) == 0) {
return root;
} else {
Node temp = search(root.left, data);
if(temp == null) {
return search(root.right, data);
} else {
return temp;
}
}
}
/**
* 前序遍历
*/
private void preOrder(Node tree, List<T> list) {
if(tree != null) {
list.add(tree.data);
preOrder(tree.left, list);
preOrder(tree.right, list);
}
}
public List<T> preOrder(boolean print) {
List<T> list = new LinkedList<T>();
preOrder(root, list);
if(print) {
System.out.println(list);
return null;
} else {
return list;
}
}
/**
* 中序遍历
*/
private void inOrder(Node tree, List<T> list) {
if(tree != null) {
inOrder(tree.left, list);
list.add(tree.data);
inOrder(tree.right, list);
}
}
public List<T> inOrder(boolean print) {
List<T> list = new LinkedList<T>();
inOrder(root, list);
if(print) {
System.out.println(list);
return null;
} else {
return list;
}
}
/**
* 后序遍历
*/
private void postOrder(Node tree, List<T> list) {
if(tree != null)
{
postOrder(tree.left, list);
postOrder(tree.right, list);
list.add(tree.data);
}
}
public List<T> postOrder(boolean print) {
List<T> list = new LinkedList<T>();
postOrder(root, list);
if(print) {
System.out.println(list);
return null;
} else {
return list;
}
}
/**
* 层次遍历
*/
private void layerOrder(List<T> list) {
if(root != null) {
List<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.remove(0);
list.add(node.data);
if(node.left != null) {
queue.add(node.left);
}
if(node.right != null) {
queue.add(node.right);
}
}
}
}
public List<T> layerOrder(boolean print) {
List<T> list = new LinkedList<T>();
this.layerOrder(list);
if(print) {
System.out.println(list);
return null;
} else {
return list;
}
}
/**
* 普通二叉树转换为数组二叉树
*/
private void toArrayTree(Object[] array, Node root, int start, T emptyData) {
int lnode = 2*start + 1;
int rnode = 2*start + 2;
if(start >= (int)(Math.pow(2, this.getHeight())-1)) return;
if(root == null) {
array[start] = emptyData;
toArrayTree(array, null, lnode, emptyData);
toArrayTree(array, null, rnode, emptyData);
} else {
array[start] = root.data;
toArrayTree(array, root.left, lnode, emptyData);
toArrayTree(array, root.right, rnode, emptyData);
}
}
public Object[] toArrayTree(T emptyData) {
Object[] array = new Object[(int)(Math.pow(2, this.getHeight())-1)];
this.toArrayTree(array, this.root, 0, emptyData);
return array;
}
/**
* 将数组二叉树转化为普通二叉树
*/
private Node arrayToTree(List<T> list, int start, T emptyData) {
if(list.get(start).compareTo(emptyData) == 0) {
return null;
}
Node root = new Node(list.get(start));
int lnode = 2*start + 1;
int rnode = 2*start + 2;
if(lnode > list.size() -1) {
root.left = null;
} else {
root.left = arrayToTree(list, lnode, emptyData);
}
if(rnode > list.size() -1) {
root.right = null;
} else {
root.right = arrayToTree(list, rnode, emptyData);
}
return root;
}
public void arrayToTree(T[] array, T emptyData) {
List<T> list = new LinkedList<T>(Arrays.asList(array));
this.root = arrayToTree(list, 0, emptyData);
}
/**
* 将String广义表转换为二叉树
*/
private Node stringListsToTreeFun(String lists, char leftMark, char rightMark, char midMark, String emptyData) {
if(lists.equals(emptyData)) return null;
int index = lists.indexOf(leftMark);
Node root = null;
if(index == -1) {
root = new Node((T)lists);
return root;
}
root = new Node((T)lists.substring(0, index));
List<Character> queue = new LinkedList<Character>();
int midIndex = 0;
int i = lists.indexOf(leftMark)+1;
queue.add(leftMark);
while(!queue.isEmpty()) {
if(lists.charAt(i) == leftMark) {
queue.add(leftMark);
} else if(lists.charAt(i) == rightMark) {
if(queue.get(queue.size()-1) == midMark && queue.get(queue.size()-2) == leftMark) {
queue.remove(queue.size()-1);
queue.remove(queue.size()-1);
} else {
queue.add(rightMark);
}
} else if(lists.charAt(i) == midMark) {
if(queue.size() == 1) {
midIndex = i;
break;
} else {
queue.add(midMark);
midIndex = i;
}
}
i++;
}
root.left = stringListsToTreeFun(lists.substring(lists.indexOf(leftMark)+1, midIndex), leftMark, rightMark, midMark, emptyData);
root.right = stringListsToTreeFun(lists.substring(midIndex+1, lists.lastIndexOf(rightMark)), leftMark, rightMark, midMark, emptyData);
return root;
}
public void stringListsToTree(String lists, char leftMark, char rightMark, char midMark, String emptyData) {
this.root = stringListsToTreeFun(lists, leftMark, rightMark, midMark, emptyData);
}
/**
* 将二叉树转换为String广义表
*/
private String toListsString(Node root, char leftMark, char rightMark, char midMark, String emptyData) {
if(root != null) {
if(root.left != null || root.right != null) {
String leftString = emptyData;
String rightString = emptyData;
if(root.left != null) leftString = toListsString(root.left, leftMark, rightMark, midMark, emptyData);
if(root.right != null) rightString = toListsString(root.right, leftMark, rightMark, midMark, emptyData);
return root.data.toString()+leftMark+leftString+midMark+rightString+rightMark;
} else {
return root.data.toString();
}
}
return "";
}
public String toListsString(char leftMark, char rightMark, char midMark, String emptyData) {
return toListsString(this.root, leftMark, rightMark, midMark, emptyData);
}
/**
* 判断是否是叶节点
*/
public boolean isLeafNode(Node node) {
if(node.left == null && node.right == null) {
return true;
} else {
return false;
}
}
/**
* 获得二叉树叶节点的个数
*/
public int LeafNodeSize() {
if(root != null) {
int size = 0;
List<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.remove(0);
if(node.left == null && node.right == null) size++;
if(node.left != null) {
queue.add(node.left);
}
if(node.right != null) {
queue.add(node.right);
}
}
return size;
}
return 0;
}
/**
* 获得叶节点列表，层次遍历
*/
public List<T> LeafNodeList() {
if(root != null) {
List<T> list = new LinkedList<T>();
List<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.remove(0);
if(node.left == null && node.right == null) {
list.add(node.data);
}
if(node.left != null) {
queue.add(node.left);
}
if(node.right != null) {
queue.add(node.right);
}
}
return list;
}
return null;
}
/**
* 获得叶节点列表，中序遍历
*/
private void inLeafNodeList(Node tree, List<T> list) {
if(tree != null) {
inLeafNodeList(tree.left, list);
if(tree.left == null && tree.right == null) {
list.add(tree.data);
}
inLeafNodeList(tree.right, list);
}
}
public List<T> inLeafNodeList() {
if(root != null) {
List<T> list = new LinkedList<T>();
this.inLeafNodeList(this.root, list);
return list;
}
return null;
}
/**
* 判断是否是完全二叉树
*/
public boolean isGoodTree() {
if(root != null) {
List<Node> queue = new LinkedList<Node>();
queue.add(root);
while(!queue.isEmpty()) {
Node node = queue.remove(0);
if(node != null) {
if(node.left != null) {
queue.add(node.left);
}
if(node.right != null) {
queue.add(node.right);
}
if(node.left == null && node.right != null) {
return false;
}
if (node.left == null && node.right == null) {
while (!queue.isEmpty()) {
node = queue.get(0);
if((node.left != null && node.right == null) || (node.left == null && node.right == null)) {
queue.remove(0);
} else {
return false;
}
}
return true;
}}
}
return true;
}
return false;
}
}package MyTreeDemo;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
/**
* MyTreeDemo
*/
public class MyTreeDemo {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// MyTree<Integer> tree = new MyTree<Integer>();
// MyTree.Node temp = tree.addRoot(1);
// tree.add(temp, -1, 2);
// temp = tree.add(temp, 1, 3);
// MyTree.Node temp1 = tree.add(temp, -1, 4);
// MyTree.Node temp2 = tree.add(temp, 1, 5);
// tree.add(temp2, -1, 6);
// tree.add(temp2, 1, 7);
// System.out.println(tree.layerOrder(false));
// Object[] arr = tree.toArrayTree(-1);
// Integer[] arr2 = new Integer[arr.length];
// for (int i = 0; i < arr.length; i++) {
// arr2[i] = (Integer)arr[i];
// }
// MyTree<Integer> tree2 = new MyTree<Integer>();
// tree2.arrayToTree(arr2, -1);
// System.out.println(tree2.layerOrder(false));
// System.out.println(Arrays.toString(arr));
// System.out.println(tree.search(tree.root, 4).data);
// Character[] arr = {'A','B','C','D','.','E','F','.','G'};
// MyTree<Character> tree = new MyTree<Character>();
// tree.arrayToTree(arr, '.');
// tree.layerOrder(true);
// Object[] arr2 = tree.toArrayTree(' ');
// System.out.println(Arrays.toString(arr2));
// System.out.println(tree.LeafNodeList());
while(in.hasNext()) {
MyTree<String> tree = new MyTree<String>();
tree.stringListsToTree(in.nextLine(), '(', ')', ',', "^");
tree.preOrder(true);
}
in.close();
}
}
/**
* MyTree
*/
class MyTree<T extends Comparable> {
// 根节点
Node root = null;
// Build临时存放节点
Node build = null;
// 节点类
class Node {
// 父节点
Node parent;
// 左子树
Node left;
// 右子树
Node right;
// 数据域
T data;
Node() {
}
Node(T data) {
this.data = data;
}
}
/**
* 添加根节点
*/
public Node addRoot(T data) {
this.root = new Node(data);
return this.root;
}
/**
* 添加节点
* @param Node root 添加节点的根节点
* @param int LeftOrRight 添加方向 {-1:添加到左子树,1:添加到右子树}
* @param T data 数据
*/
public Node add(Node root, int LeftOrRight, T data) {
Node reNode = null;
if (root == null) {
this.root = new Node(data);
reNode = this.root;
} else if (LeftOrRight == -1) {
root.left = new Node(data);
root.left.parent = root;
reNode = root.left;
} else if (LeftOrRight == 1) {
root.right = new Node(data);
root.right.parent = root;
reNode = root.right;
}
return reNode;
}
/**
* 添加节点
* @param Node root 添加节点的根节点
* @param int LeftOrRight 添加方向 {-1:添加到左子树,1:添加到右子树}
* @param Node havaNode 要添加的节点
*/
public Node add(Node root, int LeftOrRight, Node havaNode) {
Node reNode = havaNode;
if (root == null) {
this.root = havaNode;
reNode = this.root;
} else if (LeftOrRight == -1) {
root.left = havaNode;
root.left.parent = root;
reNode = root.left;
} else if (LeftOrRight == 1) {
root.right = havaNode;
root.right.parent = root;
reNode = root.right;
}
return reNode;
}
/**
* 建立层次结构的二叉树 - 不完全版
* 目前缺失功能：添加空节点
*/
public void buildAdd(Node root, T data) {
// add this.root
if(this.root == null) {
this.root = new Node(data);
this.build = this.root;
return;
}
// add this.root.left or this.root.right
if(root.parent == null) {
if(root.left == null) {
root.left = new Node(data);
root.left.parent = root;
this.build = root.left;
return;
} else {
root.right = new Node(data);
root.right.parent = root;
this.build = root.right;
return;
}
}
if(root.parent.left == root) {
root.parent.right = new Node(data);
root.parent.right.parent = root.parent;
this.build = root.parent.right;
return;
}
if(root.parent.right == root) {
root = root.parent;
int i = 1;
while (root.parent != null) {
if(root.parent.left == root) {
for (int j = 0; j < i; j++) {
root = root.left;
}
root.left = new Node(data);
root.left.parent = root;
this.build = root.left;
return;
} else {
root = root.parent;
i++;
}
}
while(true) {
if(root.left == null) {
root.left = new Node(data);
root.left.parent = root;
this.build = root.left;
return;
}
root = root.left;
}
}
}
public boolean buildAdd(T data) {
if(root != null && this.build == null) return false;
// if(this.build == null) {
// root = build
this.buildAdd(this.build, data);
// }
return true;
}
/**
* 获取树高
*/
public int getHeight() {
return this.getHeight(this.root);
}
private int getHeight(Node root) {
if (root == null) {
return 0;
} else {
int leftHeight = this.getHeight(root.left);
int rightHeight = this.getHeight(root.right);
return leftHeight > rightHeight ? (leftHeight + 1) : (rightHeight + 1);
}
}
/**
* 获取节点总数
*/
public int getSize() {
return getSize(this.root);
}
private int getSize(Node root) {
if (root == null) {
return 0;
} else {
return 1 + this.getSize(root.left) + this.getSize(root.right);
}
}
/**
* 获取父节点
* @param Node child 子节点
*/
public Node getParentNode(Node child) {
if (child == null) {
return null;
} else {
return child.parent;
}
}
/**
* 获取左子树
* @param Node root 父节点
*/
public Node getLeftChildNode(Node root) {
if (root == null) {
return null;
} else {
return root.left;
}
}
/**
* 获取右子树
* @param Node root 父节点
*/
public Node getRightChildNode(Node root) {
if (root == null) {
return null;
} else {
return root.right;
}
}
/**
* 获取root树
*/
public Node getRoot() {
return this.root;
}
/**
* 删除指定节点
* @param Node root 父节点
* @param int LeftOrRight 方向
*/
public void delete(Node root, int LeftOrRight) {
if(root == null) {
return;
} else if(LeftOrRight == -1) {
root.left = null;
} else if(LeftOrRight == 1) {
root.right = null;
}
}
/**
* 销毁整棵树
*/
public void destroy() {
if (root==null)
return ;
root = null;
}
/**
* 自动搜寻子树删除
*/
public void delete(Node root, Node target) {
if(root == null) return;
if(root.left == target) root.left = null;
if(root.right == target) root.right = null;
}
/**
* 搜索节点
* 需修改
*/
public Node search(Node root, T data) {
if(root == null) {
return null;
} else if(root.data.compareTo(data) == 0) {
return root;
} else {
Node temp = search(root.left, data);
if(temp == null) {
return search(root.right, data);
} else {
return temp;
}
}
}
/**
* 前序遍历
*/
private void preOrder(Node tree, List<T> list) {
if(tree != null) {
list.add(tree.data);
preOrder(tree.left, list);
preOrder(tree.right, list);
}
}
public List<T> preOrder(boolean print) {
List<T> list = new LinkedList<T>();
preOrder(root, list);
if(print) {
System.out.println(list);
return null;
} else {
return list;
}
}
/**
* 中序遍历
*/
private void inOrder(Node tree, List<T> list) {
if(tree != null) {
inOrder(tree.left, list);
list.add(tree.data);
inOrder(tree.right, list);
}
}
public List<T> inOrder(boolean print) {
List<T> list = new LinkedList<T>();
inOrder(root, list);
if(print) {
System.out.println(list);
return null;
} else {
return list;
}
}
/**
* 后序遍历
*/
private void postOrder(Node tree, List<T> list) {
if(tree != null)
{
postOrder(tree.left, list);
postOrder(tree.right, list);
list.add(tree.data);
}
}
public List<T> postOrder(boolean print) {
List<T> list = new LinkedList<T>();
postOrder(root, list);
if(print) {
System.out.println(list);
return null;
} else {
return list;
}
}
/**
* 层次遍历
*/
private void layerOrder(List<T> list) {
if(root != null) {
List<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.remove(0);
list.add(node.data);
if(node.left != null) {
queue.add(node.left);
}
if(node.right != null) {
queue.add(node.right);
}
}
}
}
public List<T> layerOrder(boolean print) {
List<T> list = new LinkedList<T>();
this.layerOrder(list);
if(print) {
System.out.println(list);
return null;
} else {
return list;
}
}
/**
* 普通二叉树转换为数组二叉树
*/
private void toArrayTree(Object[] array, Node root, int start, T emptyData) {
int lnode = 2*start + 1;
int rnode = 2*start + 2;
if(start >= (int)(Math.pow(2, this.getHeight())-1)) return;
if(root == null) {
array[start] = emptyData;
toArrayTree(array, null, lnode, emptyData);
toArrayTree(array, null, rnode, emptyData);
} else {
array[start] = root.data;
toArrayTree(array, root.left, lnode, emptyData);
toArrayTree(array, root.right, rnode, emptyData);
}
}
public Object[] toArrayTree(T emptyData) {
Object[] array = new Object[(int)(Math.pow(2, this.getHeight())-1)];
this.toArrayTree(array, this.root, 0, emptyData);
return array;
}
/**
* 将数组二叉树转化为普通二叉树
*/
private Node arrayToTree(List<T> list, int start, T emptyData) {
if(list.get(start).compareTo(emptyData) == 0) {
return null;
}
Node root = new Node(list.get(start));
int lnode = 2*start + 1;
int rnode = 2*start + 2;
if(lnode > list.size() -1) {
root.left = null;
} else {
root.left = arrayToTree(list, lnode, emptyData);
}
if(rnode > list.size() -1) {
root.right = null;
} else {
root.right = arrayToTree(list, rnode, emptyData);
}
return root;
}
public void arrayToTree(T[] array, T emptyData) {
List<T> list = new LinkedList<T>(Arrays.asList(array));
this.root = arrayToTree(list, 0, emptyData);
}
/**
* 将String广义表转换为二叉树
*/
private Node stringListsToTreeFun(String lists, char leftMark, char rightMark, char midMark, String emptyData) {
if(lists.equals(emptyData)) return null;
int index = lists.indexOf(leftMark);
Node root = null;
if(index == -1) {
root = new Node((T)lists);
return root;
}
root = new Node((T)lists.substring(0, index));
List<Character> queue = new LinkedList<Character>();
int midIndex = 0;
int i = lists.indexOf(leftMark)+1;
queue.add(leftMark);
while(!queue.isEmpty()) {
if(lists.charAt(i) == leftMark) {
queue.add(leftMark);
} else if(lists.charAt(i) == rightMark) {
if(queue.get(queue.size()-1) == midMark && queue.get(queue.size()-2) == leftMark) {
queue.remove(queue.size()-1);
queue.remove(queue.size()-1);
} else {
queue.add(rightMark);
}
} else if(lists.charAt(i) == midMark) {
if(queue.size() == 1) {
midIndex = i;
break;
} else {
queue.add(midMark);
midIndex = i;
}
}
i++;
}
root.left = stringListsToTreeFun(lists.substring(lists.indexOf(leftMark)+1, midIndex), leftMark, rightMark, midMark, emptyData);
root.right = stringListsToTreeFun(lists.substring(midIndex+1, lists.lastIndexOf(rightMark)), leftMark, rightMark, midMark, emptyData);
return root;
}
public void stringListsToTree(String lists, char leftMark, char rightMark, char midMark, String emptyData) {
this.root = stringListsToTreeFun(lists, leftMark, rightMark, midMark, emptyData);
}
/**
* 将二叉树转换为String广义表
*/
private String toListsString(Node root, char leftMark, char rightMark, char midMark, String emptyData) {
if(root != null) {
if(root.left != null || root.right != null) {
String leftString = emptyData;
String rightString = emptyData;
if(root.left != null) leftString = toListsString(root.left, leftMark, rightMark, midMark, emptyData);
if(root.right != null) rightString = toListsString(root.right, leftMark, rightMark, midMark, emptyData);
return root.data.toString()+leftMark+leftString+midMark+rightString+rightMark;
} else {
return root.data.toString();
}
}
return "";
}
public String toListsString(char leftMark, char rightMark, char midMark, String emptyData) {
return toListsString(this.root, leftMark, rightMark, midMark, emptyData);
}
/**
* 判断是否是叶节点
*/
public boolean isLeafNode(Node node) {
if(node.left == null && node.right == null) {
return true;
} else {
return false;
}
}
/**
* 获得二叉树叶节点的个数
*/
public int LeafNodeSize() {
if(root != null) {
int size = 0;
List<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.remove(0);
if(node.left == null && node.right == null) size++;
if(node.left != null) {
queue.add(node.left);
}
if(node.right != null) {
queue.add(node.right);
}
}
return size;
}
return 0;
}
/**
* 获得叶节点列表，层次遍历
*/
public List<T> LeafNodeList() {
if(root != null) {
List<T> list = new LinkedList<T>();
List<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.remove(0);
if(node.left == null && node.right == null) {
list.add(node.data);
}
if(node.left != null) {
queue.add(node.left);
}
if(node.right != null) {
queue.add(node.right);
}
}
return list;
}
return null;
}
/**
* 获得叶节点列表，中序遍历
*/
private void inLeafNodeList(Node tree, List<T> list) {
if(tree != null) {
inLeafNodeList(tree.left, list);
if(tree.left == null && tree.right == null) {
list.add(tree.data);
}
inLeafNodeList(tree.right, list);
}
}
public List<T> inLeafNodeList() {
if(root != null) {
List<T> list = new LinkedList<T>();
this.inLeafNodeList(this.root, list);
return list;
}
return null;
}
/**
* 判断是否是完全二叉树
*/
public boolean isGoodTree() {
if(root != null) {
List<Node> queue = new LinkedList<Node>();
queue.add(root);
while(!queue.isEmpty()) {
Node node = queue.remove(0);
if(node != null) {
if(node.left != null) {
queue.add(node.left);
}
if(node.right != null) {
queue.add(node.right);
}
if(node.left == null && node.right != null) {
return false;
}
if (node.left == null && node.right == null) {
while (!queue.isEmpty()) {
node = queue.get(0);
if((node.left != null && node.right == null) || (node.left == null && node.right == null)) {
queue.remove(0);
} else {
return false;
}
}
return true;
}}
}
return true;
}
return false;
}
}Java二叉树实现
https://blog.ixk.me/post/java-binary-tree-implementation许可协议
BY-NC-SA
本文作者
Otstar Lin
发布于
2019/04/05
转载或引用本文时请遵守许可协议，注明出处、不得用于商业用途！