利用括号表示串创建二叉树,并通过二叉树的中序遍历结果进行验证。java
时间: 2024-01-23 15:15:17 浏览: 76
好的,下面是代码实现:
```
public class Main {
public static void main(String[] args) {
// 创建二叉树
BinaryTree tree = new BinaryTree();
String str = "(A(B(D,E),C(,F)))";
BinaryTree.TreeNode root = tree.createTree(str);
// 中序遍历二叉树
tree.inOrder(root);
}
}
class BinaryTree {
private TreeNode root;
public BinaryTree() {
root = null;
}
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.leftChild);
System.out.print(root.item + " ");
inOrder(root.rightChild);
}
public TreeNode createTree(String str) {
Stack<TreeNode> st = new Stack<>();
TreeNode p = null;
char ch;
int i = 0;
while (i < str.length()) {
ch = str.charAt(i);
switch (ch) {
case '(':
st.push(p);
flag = true;
break;
case ')':
st.pop();
break;
case ',':
flag = false;
break;
default:
p = new TreeNode(ch);
if (root == null) {
root = p;
} else if (flag) {
st.peek().leftChild = p;
} else {
st.peek().rightChild = p;
}
break;
}
i++;
}
return root;
}
public static class TreeNode {
private TreeNode leftChild;
private TreeNode rightChild;
private char item;
public TreeNode(char item) {
this(null, null, item);
}
public TreeNode(TreeNode leftChild, TreeNode rightChild, char item) {
this.leftChild = leftChild;
this.rightChild = rightChild;
this.item = item;
}
}
}
```
输出结果为:D B E A C F,说明二叉树创建成功并且中序遍历正确。
阅读全文
相关推荐
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![-](https://img-home.csdnimg.cn/images/20241231044930.png)
![-](https://img-home.csdnimg.cn/images/20241231045021.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![-](https://img-home.csdnimg.cn/images/20241231044937.png)
![-](https://img-home.csdnimg.cn/images/20241231045021.png)
![rar](https://img-home.csdnimg.cn/images/20241231044955.png)