用java 树的节点类的设计、二叉链表类的设计,二叉树的建立、先序、中序、和后序遍历等基本操作的实现代码。在建好的二叉树基础上,统计树中的结点数或层次和判断给定的数据元素是否在树中等方法的实现代码。
时间: 2024-12-18 21:16:51 浏览: 9
在Java中,我们可以设计一个简单的二叉树节点类和一个二叉链表类来进行相关的操作。首先,让我们定义一个二叉树节点类(Node):
```java
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
left = null;
right = null;
}
}
```
接下来,我们创建一个二叉链表类(BinaryLinkedList),虽然通常二叉树不需要使用链表存储,但在某些情况如层序遍历时可能会用到:
```java
public class BinaryTree {
private BinaryLinkedList<TreeNode> nodes;
public BinaryTree() {
nodes = new BinaryLinkedList<>();
}
// 添加节点
public void addNode(int value) {
TreeNode newNode = new TreeNode(value);
nodes.add(newNode);
}
// 先序遍历
private void inorderTraversal(TreeNode node, List<Integer> result) {
if (node != null) {
inorderTraversal(node.left, result);
result.add(node.val);
inorderTraversal(node.right, result);
}
}
public List<Integer> preorderTraversal() {
List<Integer> result = new ArrayList<>();
inorderTraversal(root, result);
return result;
}
// 中序遍历
private void inorderTraversal(TreeNode node) {
if (node != null) {
inorderTraversal(node.left);
System.out.print(node.val + " ");
inorderTraversal(node.right);
}
}
// 后序遍历
private void postorderTraversal(TreeNode node) {
if (node != null) {
postorderTraversal(node.left);
postorderTraversal(node.right);
System.out.print(node.val + " ");
}
}
// 判断元素是否存在
public boolean containsValue(int value) {
for (TreeNode node : nodes) {
if (node.val == value) {
return true;
}
}
return false;
}
// 统计节点数
public int countNodes() {
return nodes.size();
}
// 获取树的高度/层次
public int getHeight() {
return getHeights(root);
}
private int getHeights(TreeNode node) {
if (node == null) {
return 0;
} else {
return Math.max(getHeights(node.left), getHeights(node.right)) + 1;
}
}
}
// BinaryLinkedList.java (简化版本)
public class BinaryLinkedList<T> {
private Node head;
// 省略添加、删除等方法...
}
```
这里省略了链表的具体实现和一些辅助方法,如`add`方法用于向二叉链表添加节点。请注意,实际应用中,二叉树的节点通常会直接链接左右子节点,而非通过链表结构。这个示例是为了展示如何结合链表实现部分功能。如果你需要的是标准的二叉树数据结构,可以去掉`BinaryLinkedList`部分。
阅读全文