public class Test1 {
public static void main(String[] args) throws InterruptedException {
String perOrderStr = "ABHFDECKG";//前序序列
String inOrderStr = "HBDFAEKCG";//中序序列
BiTree node = createBiTree(perOrderStr, inOrderStr);
//输出前序遍历验证正确性
BiTree.preOrdertrasver(node);
}
static class BiTree {
char data;
BiTree left;
BiTree right;
public BiTree(char data) {
this.data = data;
}
public static void preOrdertrasver(BiTree tree) {
if (tree != null) {
System.out.print(tree.data);
preOrdertrasver(tree.left);
preOrdertrasver(tree.right);
}
}
}
static BiTree createBiTree(String preOrderStr, String inOrderStr) {
if (preOrderStr.length() == 0 || inOrderStr.length() == 0) {
return null;
}
//树的根节点
char root = preOrderStr.charAt(0);
//创建节点
BiTree node = new BiTree(root);
//左右子树的根节点索引
int index = inOrderStr.indexOf(root);
//左子树str
String leftSubTreeStr = inOrderStr.substring(0, index);
//右子树str
String rightSubTreeStr = inOrderStr.substring(index + 1);
node.left = createBiTree(preOrderStr.substring(1, index + 1), leftSubTreeStr);
node.right = createBiTree(preOrderStr.substring(index + 1), rightSubTreeStr);
return node;
}
}
使用前序和中序构造二叉树
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 描述 根据前序遍历和中序遍历树构造二叉树. 注意事项 你可以假设树中不存在相同数值的节点 样例 给出中序遍历：[1...
