这篇文章主要说说二叉树的遍历以及根据前序遍历反向生成二叉树
相关的性质,概念,这里就不说了。
二叉树的遍历分为广度优先遍历(这里暂时不讲)和深度优先遍历
这里主要讲讲深度优先遍历,分为三种,1前序遍历 2中序遍历 3 后序遍历
1前序遍历
基本规则:先访问根结点,再先序遍历左子树,最后再先序遍历右子树。【根 左 右】
遍历结果:1 2 4 5 3 6 7
2中序遍历
基本规则:先中序遍历左子树,然后再访问根结点,最后再中序遍历右子树【 左 右 根】
遍历结果 : 4 2 5 1 6 3 7
3后序遍历
基本规则 : 先后序遍历左子树,然后再后序遍历右子树,最后再访问根结点 【左右根】
接下来说说 根据前序遍历序列反向生成二叉树
就拿上面的例子来说,我们把二叉树采用#号补齐,之所以要补齐的原因是 :这样子树的结构是唯一的。
比如我们把5这个节点放在4节点下,先序遍历序列还是一样的。
下面JAVA代码演示 二叉树的遍历以及根据前序遍历反向生成二叉树
import java.util.ArrayList; public class Tree { // 根节点 private Node root; int count = 0; public Node getRoot() { return root; } // tree节点 包含一个数据与以及左孩子节点以及右孩子节点 class Node { private Object data; Node leftChild; Node rightChild; public Object getData() { return data; } public void setData(Object data) { this.data = data; } public Node(Object data) { super(); this.data = data; } } //先序遍历 public void beforeOrder(Node root) { if (root == null) { return; } else { System.out.print(root.getData() + " "); beforeOrder(root.leftChild); beforeOrder(root.rightChild); } } //中序遍历 public void midOrder(Node root) { if (root == null) { return; } else { midOrder(root.leftChild); System.out.print(root.getData() + " "); midOrder(root.rightChild); } } //后序遍历 public void afterOrder(Node root) { if (root == null) { return; } else { afterOrder(root.leftChild); afterOrder(root.rightChild); System.out.print(root.getData() + " "); } } public Node createTreeWithBeforeOrder(ArrayList<String> data) { count++; Node node = null; if (data == null || data.size() == 0) { return null; } String d = data.get(0); if ("#".equals(d)) { data.remove(0); return node; } node = new Node(d); if (count == 1) // 创建根节点 { root = node; } data.remove(0); node.leftChild = createTreeWithBeforeOrder(data); node.rightChild = createTreeWithBeforeOrder(data); return node; } public static void main(String[] args) { Tree tree = new Tree(); String[] dataStr = { "1", "2", "4", "#", "#", "5", "#", "#", "3", "6", "#", "#", "7", "#", "#" }; ArrayList<String> dataList = new ArrayList<>(); for (String s : dataStr) { dataList.add(s); } tree.createTreeWithBeforeOrder(dataList); Node root = tree.getRoot(); tree.beforeOrder(root); System.out.println(); tree.midOrder(root); System.out.println(); tree.afterOrder(root); } }
add
/** * 根据树的先序遍历反向生成tree<BR> * 核心思路 先生成根节点 然后在生成左孩子 然后在生成右孩子 * * @param data * @return */ public TreeNode genenateTree(LinkedList<String> data) { // 现获取一个数字 String d = data.removeFirst(); if ("#".equals(d)) { return null; } // 创建一个节点 TreeNode node = new TreeNode(0, d); // 创建左边的孩子节点 node.leftChild = genenateTree(data); node.rightChild = genenateTree(data); return node; }