根据Java所学内容,基于链式存储结构,实现二叉树类的定义,并实现其基本操作 (假定二叉树中所有结点值为单个字符,逻辑结构采用括号表示串,基本操作包括 创建、返回、求高度)。
时间: 2024-12-19 17:24:25 浏览: 4
建立二叉树,并对树进行操作数据结构课程设计
为了实现一个基于链式存储结构的二叉树类及其基本操作,我们可以按照递归的方式来构建节点和实现遍历。这里我们仅给出基本的二叉树节点定义以及创建、返回和求高度的方法。
首先,定义一个简单的二叉树节点类,包含字符值、左子树和右子树:
```java
class TreeNode {
char val;
TreeNode left;
TreeNode right;
TreeNode(char val) {
this.val = val;
left = null;
right = null;
}
}
```
接着,创建二叉树类,包含构造方法、插入节点、返回根节点和计算高度的方法:
```java
public class BinaryTree {
private TreeNode root;
// 构造器,如果给定的字符数组代表二叉树,则创建对应的树结构
public BinaryTree(String[] preorder, String[] inorder) {
root = buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
// 根据前序和中序遍历重构二叉树
private TreeNode buildTree(String[] preorder, String[] inorder, int preStart, int preEnd,
int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
TreeNode node = new TreeNode(preorder[preStart]);
int inIndex = inorder.indexOf(node.val, inStart);
node.left = buildTree(preorder, inorder, preStart + 1, preEnd, inStart, inIndex - 1);
node.right = buildTree(preorder, inorder, preStart + inIndex - inStart + 1, preEnd,
inIndex + 1, inEnd);
return node;
}
// 返回根节点
public TreeNode getRoot() {
return root;
}
// 计算二叉树的高度
public int getHeight(TreeNode node) {
if (node == null) {
return 0;
} else {
int leftHeight = getHeight(node.left);
int rightHeight = getHeight(node.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
}
```
阅读全文