二叉树(binary tree)

这篇具有很好参考价值的文章主要介绍了二叉树(binary tree)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二叉树(binary tree)

二叉树(Binary Tree)是一种常见的树状数据结构,它由一组节点组成,每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树具有以下特点:

  1. 每个节点最多有两个子节点,分别称为左子节点和右子节点。
  2. 左子树和右子树也是二叉树,它们的结构与父节点类似。
  3. 二叉树的顺序不固定,可以是任意形状。

二叉树(binary tree)

两种特殊形式

二叉树还有两种特殊形式,一个叫作满二叉树 ,另一个叫作完全二叉树

满二叉树

如果该二叉树的所有叶子节点都在最后一层,并且结点总数= 2^n -1,n 为层数,则我们称为满二又树。简单点说,满二叉树的每一个分支都是满的。

二叉树(binary tree)

完全二叉树

对一个有n个节点的二叉树,按层级顺序编号,则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同,则这个二叉树为完全二叉树。完全二叉树的条件没有满二叉树那么苛刻: 满二叉树要求所有分支都是满的;而完全二叉树只需保证最后一个节点之前的节点都齐全即可。

二叉树(binary tree)

遍历二叉树

在计算机程序中,遍历本身是一个线性操作。所以遍历同样具有线性结构的数组或链表,是一件轻而易举的事情。反观二叉树,是典型的非线性数据结构,遍历时需要把非线性关联的点转化成一个线性的序列,以不同的方式来遍历,遍历出的序列顺序也不同。

遍历方式

深度优先和广度优先这两个概念不止局限于二叉树,它们更是一种抽象的算法思想,决定了访问某些复杂数据结构的顺序。在访问树、图,或其他一些复杂数据结构时,这两个概念常常被使用到。

1.深度优先遍历(Depth-First Search,DFS)

所谓深度优先,顾名思义,就是偏向于纵深,“一头扎到底”的访问方式。可能这种说法有些抽象,下面就通过二叉树的前序遍历、中序遍历、后序遍历 ,来看一看深度优先

2.广度优先遍历 (Breadth-First Search,BFS)

如果说深度优先遍历是在一个方向上“一头扎到底”,那么广度优先遍历则恰恰相反:先在各个方向上各走出1步,再在各个方向上走出第2步、第3步......一直到各个方向全部走完。听起来有些抽象,下面让我们通过二叉树的层序遍历

也是一种遍历或搜索树或图的算法。在广度优先遍历中,从根节点开始,按照层级顺序逐层访问节点,先访问当前层的所有节点,然后再访问下一层的节点。广度优先遍历可以使用队列来实现。

前序遍历

根节点 -> 左子树 -> 右子树。在前序遍历中,首先访问根节点,然后按照左子树和右子树的顺序递归地进行前序遍历。

    // 前序遍历二叉树(根-左-右)
    public static void preOrderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }

        System.out.print(node.val + " ");

        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }

中序遍历

左子树 -> 根节点 -> 右子树。在中序遍历中,首先按照左子树的顺序递归地进行中序遍历,然后访问根节点,最后按照右子树的顺序递归地进行中序遍历。

    // 中序遍历二叉树(左-根-右)
    public static void inOrderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }

        inOrderTraversal(node.left);

        System.out.print(node.val + " ");

        inOrderTraversal(node.right);
    }

后序遍历

左子树 -> 右子树 -> 根节点。在后序遍历中,首先按照左子树和右子树的顺序递归地进行后序遍历,然后访问根节点。

    // 后序遍历二叉树(左-右-根)
    public static void postOrderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }

        postOrderTraversal(node.left);
        postOrderTraversal(node.right);

        System.out.print(node.val + " ");
    }
 public static void main(String[] args) {
        // 创建一个二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // 前序遍历二叉树
        System.out.println("前序遍历结果:");
        preOrderTraversal(root);

        // 中序遍历二叉树
        System.out.println("\n中序遍历结果:");
        inOrderTraversal(root);

        // 后序遍历二叉树
        System.out.println("\n后序遍历结果:");
        postOrderTraversal(root);
    }

层次遍历

是一种广度优先遍历的应用,它按照层级顺序逐层访问二叉树的节点。在层次遍历中,从根节点开始,先访问根节点,然后按照从左到右的顺序逐层访问每个节点的子节点,一层一层横向遍历各个节点,可以借助于队列实现。

public static void levelOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root); // 将根节点入队
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size(); // 当前层级的节点数量
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll(); // 出队当前节点
            System.out.print(node.val + " "); // 访问当前节点
            
            if (node.left != null) {
                queue.offer(node.left); // 左子节点入队
            }
            
            if (node.right != null) {
                queue.offer(node.right); // 右子节点入队
            }
        }
        
        System.out.println(); // 换行表示进入下一层级
    }
}

存储结构

顺序结构存储

使用数组来表示二叉树的结构。按照层级顺序依次将二叉树节点存储到数组中,空缺位置用特定值(如null)表示。这种存储结构适用于完全二叉树,因为不是完全二叉树会有空间的浪费,可以通过数组下标计算节点之间的关系。

二叉树(binary tree)

特点

  • 顺序二叉树通常只考虑完全二叉树

  • 第n个元素的左子节点为 2* n +1

  • 第n个元素的右子节点为 2* n + 2

  • 第n个元素的父节点为 (n-1)/2

n: 表示二又树中的第几个元素(按0开始编号如图所示)

代码示例

public class ArrayBinaryTree {
    private int[] treeArray;
    private int size;

    public ArrayBinaryTree(int capacity) {
        treeArray = new int[capacity];
        size = 0;
    }

    public void insert(int data) {
        if (size >= treeArray.length) {
            System.out.println("The tree is full");
            return;
        }

        treeArray[size] = data;
        size++;
    }

    public void inorderTraversal(int index) {
        if (index >= size) {
            return;
        }
        
        inorderTraversal(index * 2 + 1); // 访问左子树
        System.out.print(treeArray[index] + " "); // 访问当前节点
        inorderTraversal(index * 2 + 2); // 访问右子树
    }

    public static void main(String[] args) {
        ArrayBinaryTree tree = new ArrayBinaryTree(10);
        tree.insert(1);
        tree.insert(2);
        tree.insert(3);
        tree.insert(4);
        tree.insert(5);

        System.out.print("Inorder Traversal: ");
        tree.inorderTraversal(0); // 输出: 4 2 5 1 3
    }
}

链式存储

用节点对象和指针来表示二叉树的结构。每个节点包含一个数据元素和左右子节点的指针。用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。这种存储结构可以灵活地表示任意形状的二叉树。

二叉树(binary tree)

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

线索化二叉树

线索二叉树是对普通二叉树的一种扩展,它通过在空指针位置存储指向当前节点的前驱节点和后继节点的指针,使得二叉树的遍历更加方便。可以有效地减少遍历的次数,同时也可以避免空指针的浪费。

  • n个结点的二又链表中含有n+1 [公式 2n-(n-1)=n+1] 个空指针域。利用二又链表中的空指针域,存放指向该结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为"线索")

  • 这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索叉树、中序线索二叉树和后序线索二叉树三种

  • 一个结点的前一个结点,称为前驱结点,一个结点的后一个结点,称为后继结点

二叉树(binary tree)

代码实现

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    private int leftType; // 0:左子树  1:前驱节点

    private int rightType; // 0:右子树  1:后继节点

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
    // 省略get set方法
}


class ThreadedBinaryTree {

    private TreeNode root;

    //为了实现线索化,需要创建要给指向当前结点的前驱结点的指针
    //在递归进行线索化时,pre 总是保留前一个结点
    private TreeNode pre = null;


    public void setRoot(TreeNode root) {
        this.root = root;
    }

    public void  threadedNodes(){
        this.threadedNodes(root);
    }

    // 线索化节点 中序线索化
    public void  threadedNodes(TreeNode node){

        if (node == null){
            return;
        }

        // 先线索化左子树
        threadedNodes(node.getLeft());

        // 线索化当前节点
        if (node.getLeft() == null){
            //让当前结点的左指针指向前驱结点
            node.setLeft(pre);
            node.setLeftType(1);
        }

        //处理后继结点
        if (pre != null && pre.getRight() == null) {
            //让前驱结点的右指针指向当前结点
            pre.setRight(node);
            //修改前驱结点的右指针类型
            pre.setRightType(1);
        }
        // 让当前结点是下一个结点的前驱结点
        pre = node;

        pre = node;

        // 线索化右子树
        threadedNodes(node.getRight());
    }
}

遍历线索化二叉树

因为线索化后,各个结点指向有变化,因此原来的遍历方式不能使用,这时需要使用新的方式遍历线索化二叉树,各个节点可以通过线型方式遍历,因此无需使用递归方式,这样也提高了遍历的效率。 遍历的次序应当和中序遍历保持一致。

代码实现

    // 遍历线索化二叉树
    public void threadedNodeList(){
        //定义一个变量,存储当前遍历的结点,从root开始
        TreeNode node = root;

        while (node != null){
            while (node.getLeftType() == 0){
                node = node.getLeft();
            }

            System.out.println(node);

            while (node.getRightType() == 1){
                node = node.getRight();
                System.out.println(node);
            }
            node = node.getRight();
        }

    }

以上面图中的例子,进行代码测试文章来源地址https://www.toymoban.com/news/detail-707703.html

public class ThreadedBinaryTreeDemo {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(6);
        TreeNode node4 = new TreeNode(8);
        TreeNode node5 = new TreeNode(10);
        TreeNode node6 = new TreeNode(14);

        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);


        //测试中序线索化
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedNodes();
        //测试: 以10号节点测试
        TreeNode leftNode = node5.getLeft();
        TreeNode rightNode = node5.getRight();
        System.out.println("10号结点的前驱结点是 ="  + leftNode); //3
        System.out.println("10号结点的后继结点是="  + rightNode); //1

        // 测试遍历
        System.out.println("使用线索化的方式遍历 线索化二叉树");
        threadedBinaryTree.threadedNodeList(); // 8, 3, 10, 1, 14, 6


    }

}

到了这里,关于二叉树(binary tree)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Leetcode 1367. Linked List in Binary Tree (二叉树好题)

    Linked List in Binary Tree Medium Given a binary tree root and a linked list with head as the first node. Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False. In this context downward path means a path that starts at some node and goes downwards. Exampl

    2024年01月25日
    浏览(48)
  • 【算法】Distribute Coins in Binary Tree 在二叉树中分配硬币

    给定一个有 N 个结点的二叉树的根结点 root,树中的每个结点上都对应有 node.val 枚硬币,并且总共有 N 枚硬币。 在一次移动中,我们可以选择两个相邻的结点,然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点,或者从子结点移动到父结点。

    2024年02月16日
    浏览(41)
  • Java学数据结构(2)——树Tree & 二叉树binary tree & 二叉查找树 & AVL树 & 树的遍历

    1.树的出现:解决链表线性访问时间太慢,树的时间复杂度O(logN); 2.二叉树的定义,最多两个儿子节点; 3.二叉查找树,左小,右大,中居中;remove方法,两种,只有一个儿子节点,有两个儿子节点; 4.AVL树,在二叉查找树基础上加平衡条件,旋转方法,单旋转,双旋转;

    2024年02月10日
    浏览(49)
  • 二叉查找树(binary search tree)(难度7)

    C++数据结构与算法实现(目录) 答案在此:二叉查找树(binary search tree)(答案) 写在前面 部分内容参《算法导论》 基本接口实现 1 删除 删除值为value的第一个节点 删除叶子节点1 删除叶子节点1 (3)删除叶子节点1 删除有两个孩子的节点z 分成下面几个步骤进行: 1 找到

    2024年02月10日
    浏览(45)
  • 二叉搜索树(Binary_Search_Tree)

    二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值。 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值。 它的左右子树也分别为二叉搜索树。 如: a、从根开始

    2024年04月28日
    浏览(40)
  • 【C++】二叉搜索树Binary Search Tree

    二叉搜索树又被称为二叉排序树,顾名思义,当我们使用中序遍历时,会得到一个有序的序列。二叉搜索树有如下的性质: 1.若它的左子树不为空,则左子树上每个节点的值都小于根节点的值。 2.若它的右子树不为空,则右子树上每个节点的值都大于根节点的值。 3.左右子树

    2024年02月07日
    浏览(49)
  • 二叉搜索树(Binary Search Tree,BST)

    二叉搜索树(Binary Search Tree),也称二叉查找树或二叉排序树,是一种特殊的二叉树,它满足以下性质 对于二叉搜索树的每个节点 左子树中的所有节点的值都小于该节点的值 右子树中的所有节点的值都大于(或等于)该节点的值 对于二叉搜索树的任意节点,其左子树和右子

    2024年02月09日
    浏览(46)
  • 最优二叉搜索树(Optimal Binary Search Tree)_20230401

    前言 如果有序数组或有序表中的各个元素查找概率相等,那么采用二叉搜索树(BST)进行折半查找,性能最优。如果有序表中各个记录的查找概率不相等,情况又如何呢? 先看一个具体例子。已知有序表keys, 同时给出各个元素的查询频率,注意到各个元素的查询频率不相同。

    2024年02月12日
    浏览(51)
  • 【C++庖丁解牛】二叉搜索树(Binary Search Tree,BST)

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,

    2024年03月28日
    浏览(64)
  • 数据结构英文习题解析-第五章 二叉搜索树Binary Search Tree

    前言:最近快到FDS考试了,po重刷了一下学校的题目,自己整理了一些解析orz 因为po在自己找解析和学习的过程中非常痛苦,所以在此共享一下我的题目和自己写的解题思路,欢迎各位指出错误~全章节预计会陆续更新,可在专栏查看~ HW5 1.In a binary search tree, the keys on the same

    2024年04月09日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包