java二叉链表
时间: 2023-07-10 12:20:11 浏览: 65
二叉链表是一种常见的二叉树存储结构,它由一个节点数据域、一个指向左子树的指针和一个指向右子树的指针组成。在Java中,可以通过类来实现二叉链表。下面是一个简单的二叉链表的实现示例:
```
public class BinaryTreeNode {
private int data;
private BinaryTreeNode leftChild;
private BinaryTreeNode rightChild;
public BinaryTreeNode(int data) {
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public BinaryTreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(BinaryTreeNode leftChild) {
this.leftChild = leftChild;
}
public BinaryTreeNode getRightChild() {
return rightChild;
}
public void setRightChild(BinaryTreeNode rightChild) {
this.rightChild = rightChild;
}
}
```
在这个类中,我们定义了一个二叉树节点的数据结构,包括数据域和左右子树的指针。我们可以通过实例化这个类来创建一个二叉链表,其中每个节点都包含一个数据和指向左右子树节点的指针。
下面是一个简单的二叉链表的创建和遍历示例:
```
public class BinaryTree {
private BinaryTreeNode rootNode;
public void createBinaryTree(int[] array) {
for (int i = 0; i < array.length; i++) {
insert(array[i]);
}
}
public void insert(int data) {
BinaryTreeNode newNode = new BinaryTreeNode(data);
if (rootNode == null) {
rootNode = newNode;
} else {
BinaryTreeNode currentNode = rootNode;
BinaryTreeNode parentNode;
while (true) {
parentNode = currentNode;
if (data < currentNode.getData()) {
currentNode = currentNode.getLeftChild();
if (currentNode == null) {
parentNode.setLeftChild(newNode);
return;
}
} else {
currentNode = currentNode.getRightChild();
if (currentNode == null) {
parentNode.setRightChild(newNode);
return;
}
}
}
}
}
public void preOrderTraversal(BinaryTreeNode currentNode) {
if (currentNode != null) {
System.out.print(currentNode.getData() + " ");
preOrderTraversal(currentNode.getLeftChild());
preOrderTraversal(currentNode.getRightChild());
}
}
public void inOrderTraversal(BinaryTreeNode currentNode) {
if (currentNode != null) {
inOrderTraversal(currentNode.getLeftChild());
System.out.print(currentNode.getData() + " ");
inOrderTraversal(currentNode.getRightChild());
}
}
public void postOrderTraversal(BinaryTreeNode currentNode) {
if (currentNode != null) {
postOrderTraversal(currentNode.getLeftChild());
postOrderTraversal(currentNode.getRightChild());
System.out.print(currentNode.getData() + " ");
}
}
public static void main(String[] args) {
int[] array = {10, 6, 14, 4, 8, 12, 16};
BinaryTree binaryTree = new BinaryTree();
binaryTree.createBinaryTree(array);
System.out.print("PreOrder Traversal: ");
binaryTree.preOrderTraversal(binaryTree.rootNode);
System.out.println();
System.out.print("InOrder Traversal: ");
binaryTree.inOrderTraversal(binaryTree.rootNode);
System.out.println();
System.out.print("PostOrder Traversal: ");
binaryTree.postOrderTraversal(binaryTree.rootNode);
}
}
```
在这个示例中,我们先定义了一个`BinaryTree`类,其中包含了创建二叉链表、插入数据和三种遍历方式的方法。在`createBinaryTree`方法中,我们可以通过传入一个整形数组来创建一个二叉链表。在`insert`方法中,我们可以向二叉链表中插入一个数据。在三种遍历方式的方法中,我们分别实现了先序遍历、中序遍历、后序遍历。在`main`方法中,我们创建了一个二叉链表,然后分别使用三种遍历方式输出二叉树中的节点数据。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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://csdnimg.cn/download_wenku/file_type_ask_c1.png)