Java：二叉树的创建

您所在的位置：网站首页 › java二叉树的遍历算法 › Java：二叉树的创建

Java：二叉树的创建

2023-07-25 20:48| 来源: 网络整理| 查看: 265

普通的二叉树有两种创建方式，一种是基于数组存储的，一种是基于先序遍历的。

1、基于数组的。默认：若数组的元素出现’0’【字符串】，则代表不存在该节点。假设数组内容为：1 2 3 4 0 5 6 7 8 0 0 9 10 则树的形状为：

1 / \ 2 3 / / \ 4 5 6 / \ / \ 7 8 9 10

Node.java：

public class Node { Node left; Node right; char data; public Node(char data) { left = null; right = null; this.data = data; } public char getData() { return data; } public Node getLeft() { return left; } public Node getRight() { return right; } public void setLeft(Node left) { this.left = left; } public void setRight(Node right) { this.right = right; } public void setData(char data) { this.data = data; } }

很简单，就是定义了get、set方法

Tree.java：

public class Tree { Node root; // 根节点 int size; // 树长度 char[] data; // 数的数据 public Tree(char[] data) { this.data = data; size = data.length; root = createTree(0); } public Node createTree(int index) { // 采用递归生成二叉树 if (index >= size) return null; if (data[index] == '0') return null; Node node = new Node(data[index]); node.setLeft(createTree(2 * index + 1)); node.setRight(createTree(2 * index + 2)); return node; } public void preShow(Node node) { // 先序遍历 if (node != null) { System.out.print(node.getData() + " "); preShow(node.getLeft()); preShow(node.getRight()); } } public void middleShow(Node node) { // 中序遍历 if (node != null) { middleShow(node.getLeft()); System.out.print(node.getData() + " "); middleShow(node.getRight()); } } public void backShow(Node node) { // 后序遍历 if (node != null) { backShow(node.getLeft()); backShow(node.getRight()); System.out.print(node.getData() + " "); } } public Node getRoot() { // 得到根节点 return root; } }

重点就在于createTree(int index)函数。

MainClass.java：

public class MainClass { public static void main(String[] args) { char[] chars = new char[] {'1', '2', '3', '4', '0', '5', '6', '7', '8', '0', '0', '9', 'A'}; Tree tree = new Tree(chars); System.out.println("先序遍历"); tree.preShow(tree.getRoot()); System.out.println(); System.out.println("中序遍历"); tree.middleShow(tree.getRoot()); System.out.println(); System.out.println("后序遍历"); tree.backShow(tree.getRoot()); System.out.println(); } }

运行结果：

先序遍历 1 2 4 7 8 3 5 9 A 6 中序遍历 7 4 8 2 1 9 5 A 3 6 后序遍历 7 8 4 2 9 A 5 6 3 1

2、基于先序遍历建树 Node.java不变。 Tree.java：

public class Tree { Node root; // 根节点 int size; // 树长度 String data; // 数的数据 int index; public Tree(String data) { this.data = data; size = data.length(); index = 0; root = createTree(); } public Node createTree() { // 采用递归生成二叉树 char ch = data.charAt(index ++); if(ch == '0') return null; else { Node node = new Node(ch); node.setLeft(createTree()); node.setRight(createTree()); return node; } } public void preShow(Node node) { // 先序遍历 if (node != null) { System.out.print(node.getData() + " "); preShow(node.getLeft()); preShow(node.getRight()); } } public void middleShow(Node node) { // 中序遍历 if (node != null) { middleShow(node.getLeft()); System.out.print(node.getData() + " "); middleShow(node.getRight()); } } public void backShow(Node node) { if (node != null) { backShow(node.getLeft()); backShow(node.getRight()); System.out.print(node.getData() + " "); } } public Node getRoot() { return root; } }

MainClass.java：

public class MainClass { public static void main(String[] args) { String data = "AB0C00D00"; Tree tree = new Tree(data); System.out.println("先序遍历"); tree.preShow(tree.getRoot()); System.out.println(); System.out.println("中序遍历"); tree.middleShow(tree.getRoot()); System.out.println(); System.out.println("后序遍历"); tree.backShow(tree.getRoot()); System.out.println(); } }

运行结果：

先序遍历 A B C D 中序遍历 B C A D 后序遍历 C B D A

【本文地址】

Java：二叉树的创建

Java：二叉树的创建

今日新闻

推荐新闻