将一个数组变成二叉树

2024-07-15 04:05| 来源: 网络整理| 查看: 265

二叉树是每个节点最多有两个子树的树结构。通常子树被称作 “左子树” 和 “右子树”。比如数组：

int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9} 变为二叉树为：

分析： 1、首先要定义每一个结点，每一个结点包括自身值，左结点和右结点，实现get、set方法。

public class Node { public int data; //自己本身值 public Node left; //左结点 public Node right; //右结点 public Node() { } public Node(int data, Node left, Node right) { this.data = data; this.left = left; this.right = right; } public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } }

2、创建二叉树

public class Demo2 { public static List list = new ArrayList(); //用一个集合来存放每一个Node public void createTree(int[] array) { for (int i = 0; i < array.length; i++) { Node node = new Node(array[i], null, null); //创建结点，每一个结点的左结点和右结点为null list.add(node); // list中存着每一个结点 } // 构建二叉树 if (list.size() > 0) { for (int i = 0; i < array.length / 2 - 1; i++) { // i表示的是根节点的索引，从0开始 if (list.get(2 * i + 1) != null) { // 左结点 list.get(i).left = list.get(2 * i + 1); } if (list.get(2 * i + 2) != null) { // 右结点 list.get(i).right = list.get(2 * i + 2); } } // 判断最后一个根结点：因为最后一个根结点可能没有右结点，所以单独拿出来处理 int lastIndex = array.length / 2 - 1; // 左结点 list.get(lastIndex).left = list.get(lastIndex * 2 + 1); // 右结点，如果数组的长度为奇数才有右结点 if (array.length % 2 == 1) { list.get(lastIndex).right = list.get(lastIndex * 2 + 2); } } } // 遍历，先序遍历 public static void print(Node node) { if (node != null) { System.out.print(node.data + " "); print(node.left); print(node.right); } } public static void main(String[] args) { int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; Demo2 demo = new Demo2(); demo.createTree(array); print(list.get(0)); } }

结果为： 1 2 4 8 9 5 3 6 7

【本文地址】

公司简介

联系我们