|
字符串构建二叉树
我们都知道二叉树的遍历很简单的写法就是通过递归方式实现的。但很少写构建一颗二叉树，其实构建二叉树和遍历差不多，这里通过字符串来实现二叉树的构建。后续通过这棵树来学习一些二叉树的算法或者用来刷leetcode上的二叉树题型。
// 节点信息
public class TreeNode {
private Character data;
private TreeNode leftChild;
private TreeNode rightChild;
public TreeNode(Character data) {
this.data = data;
}
public Character getData() {
return data;
}
public void setData(Character data) {
this.data = data;
}
public TreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(TreeNode leftChild) {
this.leftChild = leftChild;
}
public TreeNode getRightChild() {
return rightChild;
}
public void setRightChild(TreeNode rightChild) {
this.rightChild = rightChild;
}
}
/**
*
* A
* B E
* C D F
* 构造数字符串前序遍历： A B C # # D # # E # F # #
* 打印：
* 前序： A B C D E F
* 中序： C B D A E F
* 后序： C D B F E A
* */
public class BinaryTree {
private static int index = 0;
// 创建一棵树
public TreeNode buildTree(String treeInfo) {
if (index >= treeInfo.length()) {
return null;
}
if (treeInfo.charAt(index) == '#') {
index++;
return null;
}
TreeNode node = new TreeNode(treeInfo.charAt(index));
index++;
node.setLeftChild(buildTree(treeInfo));
node.setRightChild(buildTree(treeInfo));
return node;
}
// 递归方式前序遍历
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.getData());
preOrder(root.getLeftChild());
preOrder(root.getRightChild());
}
// 中序
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.getLeftChild());
System.out.print(root.getData());
inOrder(root.getRightChild());
}
// 后续
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.getLeftChild());
postOrder(root.getRightChild());
System.out.print(root.getData());
}
}
// 测试函数
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
TreeNode root = tree.buildTree("ABC##D##E#F##");
tree.preOrder(root); // ABCDEF
System.out.println();
tree.inOrder(root); // CBDAEF
System.out.println();
tree.postOrder(root); // CDBFEA
}
|