【数据结构与算法之树结构】创建二叉树

柔情只为你懂 2024-03-25 14:12 168阅读 0赞

#### 【数据结构与算法之树结构】创建二叉树 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之树结构】创建二叉树

利用二叉树遍历的思想，在遍历过程中生成二叉树的节点，进而建立起整棵二叉树。

一般情况下，可以按照先序序列建立一棵二叉树。

以Java算法实现：

public BinaryTreeNode CreateBiTree(LinkedList<Integer> nodeList) {
        
        BinaryTreeNode node = null;
        if (nodeList == null || nodeList.isEmpty()) {
        
            return null;
        }
    
        Integer data = nodeList.removeFirst();
        if (data != null) {
        
            node = new BinaryTreeNode(data);
            node.leftChild = CreateBiTree(nodeList);
            node.rightChild = CreateBiTree(nodeList);
        }
    
        return node;
    }

下面给出一个完整的二叉树类定义和测试程序。

import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    import java.util.zip.Inflater;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: BinaryTree
     * @Author: Ding Jiaxiong
     * @Data:2023/3/13 13:24
     */
    
    public class BinaryTree {
        
    
        private BinaryTreeNode root; // 根节点
    
        public BinaryTree() {
        
            root = null;
        }
    
    
        /**
         * 创建二叉树
         *
         * @param nodeList
         */
        public void CreateBinaryTree(LinkedList<Integer> nodeList) {
        
            root = CreateBiTree(nodeList);
        }
    
        /**
         * 先序创建二叉树
         *
         * @param nodeList
         * @return
         */
        public BinaryTreeNode CreateBiTree(LinkedList<Integer> nodeList) {
        
            BinaryTreeNode node = null;
            if (nodeList == null || nodeList.isEmpty()) {
        
                return null;
            }
    
            Integer data = nodeList.removeFirst();
            if (data != null) {
        
                node = new BinaryTreeNode(data);
                node.leftChild = CreateBiTree(nodeList);
                node.rightChild = CreateBiTree(nodeList);
            }
    
            return node;
        }
    
        // 先序遍历
        public void PreOrderTraverse() {
        
            PreOrderTraverse(root);
        }
    
        /**
         * 先序遍历二叉树
         *
         * @param root
         */
        public void PreOrderTraverse(BinaryTreeNode root) {
        
            if (root != null) {
        
                visit(root); // 访问根节点
                PreOrderTraverse(root.leftChild);
                PreOrderTraverse(root.rightChild);
            }
        }
    
        //中序遍历
        public void InOrderTraverse() {
        
            InOrderTraverse(root);
        }
    
        /**
         * 中序遍历二叉树
         *
         * @param root
         */
        public void InOrderTraverse(BinaryTreeNode root) {
        
            if (root != null) {
        
                InOrderTraverse(root.leftChild);
                visit(root);
                InOrderTraverse(root.rightChild);
            }
        }
    
        // 后序遍历
        public void PostOrderTraverse() {
        
            PostOrderTraverse(root);
        }
    
        /**
         * 后序遍历二叉树
         *
         * @param root
         */
        public void PostOrderTraverse(BinaryTreeNode root) {
        
            if (root != null) {
        
                PostOrderTraverse(root.leftChild);
                PostOrderTraverse(root.rightChild);
                visit(root);
            }
        }
    
        /**
         * 层次遍历二叉树
         */
        public void LayerOrderTraverse() {
        
            Queue<BinaryTreeNode> queue = new LinkedList<BinaryTreeNode>();
            queue.offer(root); // 根节点入队
    
            while (!queue.isEmpty()) {
        
                BinaryTreeNode node = queue.poll(); // 取出队头元素
                visit(node); // 访问该节点
                if (node.leftChild != null) {
        
                    queue.offer(node.leftChild); // 左孩子不为空就入队
                }
                if (node.rightChild != null) {
        
                    queue.offer(node.rightChild); // 右孩子不为空就入队
                }
            }
        }
    
        /**
         * 访问节点
         *
         * @param root
         */
        private void visit(BinaryTreeNode root) {
        
            System.out.print(root.data + " ");
        }
    
        /**
         * 测试
         *
         * @param args
         */
        public static void main(String[] args) {
        
    
            BinaryTree binaryTree = new BinaryTree();
            LinkedList<Integer> nodes = new LinkedList<>(Arrays.asList(new Integer[]{
        2, 3, 5, null, null, 0, null, null, 6, 7, null, null, null}));
    
            binaryTree.CreateBinaryTree(nodes);
            System.out.println("先序遍历: ");
            binaryTree.PreOrderTraverse();
            System.out.println("\n中序遍历: ");
            binaryTree.InOrderTraverse();
            System.out.println("\n后序遍历: ");
            binaryTree.PostOrderTraverse();
            System.out.println("\n按层次遍历: ");
            binaryTree.LayerOrderTraverse();
        }
    
    }
    
    class BinaryTreeNode {
        
    
        int data; // 数据域
        BinaryTreeNode leftChild; // 左孩子
        BinaryTreeNode rightChild; // 右孩子
    
        public BinaryTreeNode(int data) {
        
            this.data = data;
            leftChild = null;
            rightChild = null;
        }
    
    }

![在这里插入图片描述][a77cb3ba213d42d89eb4ff3ca3546dc1.png_pic_center]

运行结果

![在这里插入图片描述][b785f600ead34fa3a1730d28e0c311e6.png_pic_center]

[a77cb3ba213d42d89eb4ff3ca3546dc1.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b564595f2023426ab0e8d18fec2102c3.png
[b785f600ead34fa3a1730d28e0c311e6.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d1a9135921144ebd9246e7a86449c029.png