栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

二叉树的创建和深度优先递归

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

二叉树的创建和深度优先递归

二叉树的深度遍历分为前中后遍历,关于前中后遍历的概念,别的博客有讲,我们主要研究一下二叉树的创建原理和遍历的代码
首先我们创建树的节点:

 private static class TreeNode {
            int data;
            TreeNode leftChild;
            TreeNode rightChild;

            TreeNode(int data) {
                this.data = data;
            }
        }

里面有左右节点和本身的数据

由于深度遍历是以链表为基础的,所以我们创建一个链表数组

 LinkedList inputList = new LinkedList(Arrays.asList(new Integer[]{3,2,9,null,null,10,null,null,8,null,4,}));

接下来我们用递归的方法将数据创建一个数,这个代码最主要是画图,或者自己debug一下,我用注释讲一下

public static TreeNode createBinaryTree(LinkedList inputList){
   TreeNode node = null;//创建一个空节点
   if(inputList==null || inputList.isEmpty()){
   return null;
   }//如果传入的链表数组为空,那么就创建完成了
   Integer data = inputList.removeFirst();//这个函数的是取出链表第一个数据并将其删除,这样链表的长度会一点点减少,直到为empyt;
   if(data != null){ //这里的判空很关键。如果元素是空,说明该节点不存在,跳出这一层递归;如果元素非空,继续递归构建该节点的左右孩子。
    node = new TreeNode(data);//将数据传入节点
    node.leftChild = createBinaryTree(inputList);//开始左递归;递归到最后一个数据后,开始右递归
    node.rightChild = createBinaryTree(inputList);//开始右递归;递归到最后一个数据后,返回上一个节点
    }
 return node;递归到null后,如果是左节点,开始递归右节点,如果是右节点,则返回上一个节点
        }

这个树是这样的:

接下来是三种遍历,其实三种遍历的思想是一样的,就是先递归哪个代码的问题;
前序遍历:

public static void preOrderTraversal(TreeNode node){
            if(node == null){
                return;
            }
            System.out.println(node.data);
            preOrderTraversal(node.leftChild);
            preOrderTraversal(node.rightChild);
        }

前序遍历是先输出节点的数据,然后一直递归左子树,左子树递归后,递归右子树
所以结果是这样的:3 2 9 10 8 4

中序遍历:

public static void inOrderTraversal(TreeNode node){
            if(node == null){
                return;
            }
            inOrderTraversal(node.leftChild);
            System.out.println(node.data);
            inOrderTraversal(node.rightChild);
        }

中序遍历是先递归左子树,然后输出,再递归右子树
所以结果是:9 2 10 3 8 4
后序遍历:

 public static void postOrderTraversal(TreeNode node){
            if(node == null){
                return;
            }
            postOrderTraversal(node.leftChild);
            postOrderTraversal(node.rightChild);
            System.out.println(node.data);
        }

后序遍历是先一直左递归,然后右递归,最后输出数据
所以结果是:9 10 2 4 8 3

总代码:

package tree;
import java.util.Arrays;
import java.util.LinkedList;
    public class BinaryTreeTraversal {

        public static TreeNode createBinaryTree(LinkedList inputList){
            TreeNode node = null;
            if(inputList==null || inputList.isEmpty()){
                return null;
            }
            Integer data = inputList.removeFirst();
            //这里的判空很关键。如果元素是空,说明该节点不存在,跳出这一层递归;如果元素非空,继续递归构建该节点的左右孩子。
            if(data != null){
                node = new TreeNode(data);
                node.leftChild = createBinaryTree(inputList);
                node.rightChild = createBinaryTree(inputList);
            }
            return node;
        }

        
        public static void preOrderTraversal(TreeNode node){
            if(node == null){
                return;
            }
            System.out.println(node.data);
            preOrderTraversal(node.leftChild);
            preOrderTraversal(node.rightChild);
        }

        
        public static void inOrderTraversal(TreeNode node){
            if(node == null){
                return;
            }
            inOrderTraversal(node.leftChild);
            System.out.println(node.data);
            inOrderTraversal(node.rightChild);
        }


        
        public static void postOrderTraversal(TreeNode node){
            if(node == null){
                return;
            }
            postOrderTraversal(node.leftChild);
            postOrderTraversal(node.rightChild);
            System.out.println(node.data);
        }

        
        private static class TreeNode {
            int data;
            TreeNode leftChild;
            TreeNode rightChild;

            TreeNode(int data) {
                this.data = data;
            }
        }

        public static void main(String[] args) {
            LinkedList inputList = new LinkedList(Arrays.asList(new Integer[]{3,2,9,null,null,10,null,null,8,null,4,}));
            TreeNode treeNode = createBinaryTree(inputList);
            System.out.println("前序遍历:");
            preOrderTraversal(treeNode);
            System.out.println("中序遍历:");
            inOrderTraversal(treeNode);
            System.out.println("后序遍历:");
            postOrderTraversal(treeNode);
        }

    }

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/937592.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号