二叉树的先根遍历

2019-11-06 08:19:04

字体：大中小

来源：转载

供稿：网友

二叉树的先根遍历

转载请保留出处： http://blog.csdn.net/xiaxl/article/details/60134694

面试时，经常问道类似与，获取某一文件夹下所有文件和文件夹；二叉树遍历等问题。这是一类问题，以二叉树的先根遍历举例：

递归实现

public class Test { /** * 二叉树节点类 */ public static class BinaryTreeNode { // 根节点数据 int data; // 左子树 BinaryTreeNode leftNode; // 右子树 BinaryTreeNode rightNode; // 实例化二叉树类 public BinaryTreeNode(int data) { this.data = data; } } /** * 向二叉树中插入子节点 * * 插入规则：左节点小于根节点，右节点大于根节点 * * @param rootNode * 二叉树根节点 * @param data * 插入的数据 */ public static void insertBinaryTreeNode(BinaryTreeNode rootNode, int data) { // 二叉树的左节点都比根节点小 if (data <= rootNode.data) { // 没有左节点，则创建左节点 if (rootNode.leftNode == null) { rootNode.leftNode = new BinaryTreeNode(data); } else { // 有左节点，则以左节点为节点向下一级别递归 insertBinaryTreeNode(rootNode.leftNode, data); } } // 二叉树的右节点都比根节点大 else { // 没有右节点，则创建右节点 if (rootNode.rightNode == null) { rootNode.rightNode = new BinaryTreeNode(data); } else { // 有右节点，则以右节点为节点向下一级别递归 insertBinaryTreeNode(rootNode.rightNode, data); } } } /** * 先根遍历(中左右) * * @param rootNode * 二叉树根节点 */ public static void PReOrderBinaryTree(BinaryTreeNode rootNode) { if (rootNode != null) { System.out.print(rootNode.data + "-"); // preOrderBinaryTree(rootNode.leftNode); preOrderBinaryTree(rootNode.rightNode); } } /** * 程序入口 * * @param arg */ public static void main(String arg[]) { // ----------创建二叉树--------- int[] array = { 6, 6, 8, 16, 15, 18, 17 }; // 以12为根节点,创建二叉树 BinaryTreeNode rootNode = new BinaryTreeNode(12); for (int i = 0; i < array.length; i++) { // 向二叉树中插入数据 insertBinaryTreeNode(rootNode, array[i]); } // ----------先根遍历(中左右)--------- System.out.println("先根遍历："); preOrderBinaryTree(rootNode); }}