Created
April 23, 2024 21:10
-
-
Save Cubik65536/e0642881d0e4c9e47fca6883dd65d7ed to your computer and use it in GitHub Desktop.
Java Binary Tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 二叉树的节点 | |
*/ | |
class BinaryTreeNode { | |
int data; | |
BinaryTreeNode left; | |
BinaryTreeNode right; | |
} | |
/** | |
* 二叉树 | |
*/ | |
class BinaryTree { | |
BinaryTreeNode root; | |
public BinaryTreeNode insert(int data) { | |
BinaryTreeNode newNode = new BinaryTreeNode(); | |
newNode.data = data; | |
newNode.left = null; | |
newNode.right = null; | |
return newNode; | |
} | |
/** | |
* 先序遍历,即先访问根节点,再访问左子节点,最后访问右子节点 | |
* 使用递归实现 | |
* @param node 二叉树的根节点 | |
*/ | |
public void preOrder(BinaryTreeNode node) { | |
if (node != null) { // 如果节点不为空,就访问这个节点 | |
System.out.print(node.data + " "); // 访问节点的数据 | |
preOrder(node.left); // 递归访问左子节点的数据 | |
preOrder(node.right); // 递归访问右子节点的数据 | |
} | |
} | |
/** | |
* 中序遍历,即先访问左子节点,再访问根节点,最后访问右子节点 | |
* 使用递归实现 | |
* @param node 二叉树的根节点 | |
*/ | |
public void inOrder(BinaryTreeNode node) { | |
if (node != null) { // 如果节点不为空,就访问这个节点 | |
inOrder(node.left); // 递归访问左子节点的数据 | |
System.out.print(node.data + " "); // 访问节点的数据 | |
inOrder(node.right); // 递归访问右子节点的数据 | |
} | |
} | |
/** | |
* 后序遍历,即先访问左子节点,再访问右子节点,最后访问根节点 | |
* 使用递归实现 | |
* @param node 二叉树的根节点 | |
*/ | |
public void postOrder(BinaryTreeNode node) { | |
if (node != null) { // 如果节点不为空,就访问这个节点 | |
postOrder(node.left); // 递归访问左子节点的数据 | |
postOrder(node.right); // 递归访问右子节点的数据 | |
System.out.print(node.data + " "); // 访问节点的数据 | |
} | |
} | |
/** | |
* 广度优先遍历,即按层次遍历 | |
* @param root 二叉树的根节点 | |
*/ | |
public void widthFirst(BinaryTreeNode root) { | |
if (root == null) { // 如果根节点为空,直接返回 | |
return; | |
} | |
BinaryTreeNode[] queue = new BinaryTreeNode[20]; // 一个队列,用于存储节点 | |
int rear = 0, front = 0; // rear 是队尾指针,front 是队首指针 | |
queue[rear++] = root; // 将根节点放入队列,队尾指针加一 | |
BinaryTreeNode n; // 用于存储从队列中取出的节点 | |
while (front < rear) { // 如果队首指针小于队尾指针,说明队列中还有节点 | |
n = queue[front]; // 取出队首的节点 | |
System.out.print(queue[front++].data + " "); // 输出这个节点的数据,同时队首指针加一,这样下一个被取出的就是下一个节点了 | |
if (n.left != null) queue[rear++] = n.left; // 如果这个节点有左子节点,将左子节点放入队列,队尾指针加一 | |
if (n.right != null) queue[rear++] = n.right; // 如果这个节点有右子节点,将右子节点放入队列,队尾指针加一 | |
} | |
// 这样的遍历方式,可以保证每一层的节点都先被访问并被放进队列 | |
// 在这层被打印之后,这些节点的子节点(下一层)才会被放进队列 | |
// 这样就可以保证按层次遍历 | |
} | |
/** | |
* 广度优先遍历,即按层次遍历,每一层打印一行 | |
* @param root 二叉树的根节点 | |
*/ | |
public void widthFirstLn(BinaryTreeNode root) { | |
if (root == null) { // 如果根节点为空,直接返回 | |
return; | |
} | |
BinaryTreeNode[] queue = new BinaryTreeNode[20]; // 一个队列,用于存储节点 | |
int rear = 0, front = 0; // rear 是队尾指针,front 是队首指针 | |
queue[rear++] = root; // 将根节点放入队列,队尾指针加一 | |
int lvl = rear; // 用于记录当前层的最后一个节点的下标,用于换行 | |
// 默认是 1,因为根节点只有 1 个,从 1 开始就是下一层了(正好也是刚将根节点放入队列后队尾指针的值) | |
BinaryTreeNode n; // 用于存储从队列中取出的节点 | |
while (front < rear) { // 如果队首指针小于队尾指针,说明队列中还有节点 | |
n = queue[front]; // 取出队首的节点 | |
System.out.print(queue[front++].data + " "); // 输出这个节点的数据,同时队首指针加一,这样下一个被取出的就是下一个节点了 | |
if (n.left != null) queue[rear++] = n.left; // 如果这个节点有左子节点,将左子节点放入队列,队尾指针加一 | |
if (n.right != null) queue[rear++] = n.right; // 如果这个节点有右子节点,将右子节点放入队列,队尾指针加一 | |
if (front == lvl) { // 如果队首指针等于当前层的最后一个节点的下标,说明这一层已经遍历完了 | |
System.out.println(); // 打印一个换行 | |
lvl = rear; // 同时,目前的队尾指针的值就是下一层的最后一个节点的下标,因为下一层的节点都已经放入队列了 | |
} | |
} | |
} | |
} | |
public class TreeExample { | |
public static void main(String[] args) { | |
/* | |
* 构建一个如下图所示的二叉树 | |
* 2 | |
* / \ | |
* / \ | |
* 7 5 | |
* / \ \ | |
* 2 6 9 | |
* / \ / | |
* 5 11 4 | |
*/ | |
BinaryTree tree = new BinaryTree(); | |
tree.root = tree.insert(2); | |
tree.root.left = tree.insert(7); | |
tree.root.right = tree.insert(5); | |
tree.root.left.left = tree.insert(2); | |
tree.root.left.right = tree.insert(6); | |
tree.root.left.right.left = tree.insert(5); | |
tree.root.left.right.right = tree.insert(11); | |
tree.root.right.right = tree.insert(9); | |
tree.root.right.right.left = tree.insert(4); | |
System.out.println("Pre-order traversal: "); | |
tree.preOrder(tree.root); | |
System.out.println(); | |
System.out.println("In-order traversal: "); | |
tree.inOrder(tree.root); | |
System.out.println(); | |
System.out.println("Post-order traversal: "); | |
tree.postOrder(tree.root); | |
System.out.println(); | |
System.out.println("Width-first traversal: "); | |
tree.widthFirst(tree.root); | |
System.out.println(); | |
System.out.println("Width-first traversal with line break: "); | |
tree.widthFirstLn(tree.root); | |
System.out.println(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment