java创建二叉树及遍历

2019-11-06 06:59:22

字体：大中小

来源：转载

供稿：网友

已知外部提供创建树所需要的数据。

方法1：按照从上到下从左到右依次把数据放在对应结点来创建树。即数组中index处的数据在树中仍然是放在index处，而它的左右子结点分别是 2*index+1 , 2*index+2

-- BinaryTree.javapublic class BinaryTree { Node root; int size; // 结点总个数 Object[] data; // 内部类 PRivate class Node{ private Node left; private Node right; private Object data; public Node(Object data){ this.left = null; this.right = null; this.data = data; } } public BinaryTree(Object[] data){ this.data = data; size = data.length; root = createTree(0); } // 创建下标为index处的结点及其子树,递归 public Node createTree(int index){ if (index >= size) return null; Node node = new Node(data[index]); node.left = createTree(2*index+1); node.right = createTree(2*index+2); return node; } // 先序遍历 public void preShow(Node node) { if(node!=null){ System.out.print(node.data + " "); preShow(node.left); preShow(node.right); } } // 中序遍历 public void middleShow(Node node) { if (node != null) { middleShow(node.left); System.out.print(node.data + " "); middleShow(node.right); } } // 后序遍历 public void backShow(Node node) { if (node != null) { middleShow(node.left); middleShow(node.right); System.out.print(node.data + " "); } } public static void main(String[] args) { Object[] my = new Object[]{'1', '2', '3', '4', '0', '5', '6', '7', '8', '0', '0', '9', 'A'}; BinaryTree tree = new BinaryTree(my); tree.preShow(tree.root); System.out.println(); tree.middleShow(tree.root); }}

法2：采用先序遍历创建二叉树

-- BinaryTree2.javapublic class BinaryTree2 { Node root; int size; // 结点总个数 Object[] data; int index; //表示取到数组中下标为index的元素了 // 内部类 private class Node{ private Node left; private Node right; private Object data; public Node(Object data){ this.left = null; this.right = null; this.data = data; } } public BinaryTree2(Object[] data){ size = data.length; this.data = data; index = 0; root = createTree(); } // 按照先序遍历创造树 public Node createTree(){ if(index>=size) return null; Object o = data[index++]; Node node = new Node(o); node.left = createTree(); node.right = createTree(); return node; } // 先序遍历 public void preShow(Node node) { if(node!=null){ System.out.print(node.data + " "); preShow(node.left); preShow(node.right); } } // 中序遍历 public void middleShow(Node node) { if (node != null) { middleShow(node.left); System.out.print(node.data + " "); middleShow(node.right); } } // 后序遍历 public void backShow(Node node) { if (node != null) { middleShow(node.left); middleShow(node.right); System.out.print(node.data + " "); } } public static void main(String[] args) { Object[] my = new Object[]{'1', '2', '3', '4', '0', '5', '6', '7', '8', '0', '0', '9', 'A'}; BinaryTree2 tree = new BinaryTree2(my); tree.preShow(tree.root); System.out.println(); tree.middleShow(tree.root); }}

上一篇：Java学习-装箱和拆箱

下一篇：Java多线程（二）