欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

二叉树总结

程序员文章站 2024-01-18 08:32:40
二叉树近期开始接触 二叉树 相关知识,特此根据现有知识对栈和队列做以小结,以下博客仅作为个人学习过程的小结,如能对各位博友有所帮助不胜荣幸。本篇博客将简单介绍相关知识,以及其注意事项有哪些,只做本人小结,后期随学习深入再做补充修改。一、树结构:树形结构是一种非线性结构,不同于线性表,它是一层次的嵌套结构,因为其内外层结构相似,所以经常使用递归表示。其元素之间为一对多的关系,数状图是一种典型的树形结构。如上图所示,就是一棵树,方向由上往下延伸每一个圆圈叫做结点,最上面的结点(A)称为根结点,一个...

二叉树

近期开始接触 二叉树 相关知识,特此根据现有知识对栈和队列做以小结,以下博客仅作为个人学习过程的小结,如能对各位博友有所帮助不胜荣幸。
本篇博客将简单介绍相关知识,以及其注意事项有哪些,只做本人小结,后期随学习深入再做补充修改。

一、树结构:
树形结构是一种非线性结构,不同于线性表,它是一层次的嵌套结构,因为其内外层结构相似,所以经常使用递归表示。其元素之间为一对多的关系,数状图是一种典型的树形结构。
二叉树总结
如上图所示,就是一棵树,方向由上往下延伸
每一个圆圈叫做结点,最上面的结点(A)称为根结点,一个数可以简单的理解为又根和其子树不断递归形成的。

  • 相关概念
  • 结点(Node):表示树中的数据元素,上图中有10个结点,即A~J
  • 结点的度(Degree of Node):表示该结点所拥有子树的个数,上图中A的度为3
  • 树的度(Degree of Tree):表示一个树中各结点度的最大值,上图中以A为根的树度为3
  • 叶子结点(Leaf Node):表示度为0的结点,上图中有6个叶子结点,即E~J
  • 非叶子结点:表示度不为0(即不是叶子结点)的结点,上图中有4个。即A~D
  • 孩子(Child):表示一个结点子树的根结点,上图中A的孩子有3个,即B、C、D
  • 双亲(Parent):表示一个结点上层的结点,上图中B、C、D双亲为A
  • 根结点(Root):表示一棵树没有双亲结点的结点
  • 结点的层(Level of Node):根结点的层次规定为1,其余结点的层次等于其双亲结点的层次加1,上图A的层为1,B为2,E为3…以此类推
  • 树的高度(Depth of Tree):一个数中个结点层的最大值,上图中以A为根的树高度为3

二、二叉树:

  • 概念:二叉树中所有结点的度不大于2,即其内每个结点的左右孩子最多只能有一个,或者没有。
    二叉树有左右之分,是有序树
    其只有五种形态:
    二叉树总结

  • 完全二叉树和满二叉树
    满二叉树:一个二叉树,每一层的节点数都达到了最大值,这个二叉树称为满二叉树。层数为k的满二叉树,结点个数为(2^k)-1 。
    完全二叉树:一棵深度为k有n个结点的二叉树,对树中的节点从上到下从左到右依次编号,如果其编号为i的节点与满二叉树中编号为 i 的节点在二叉树中的位置相同,则这棵树称为完全二叉树。

  • 二叉树的性质:
    一个层数为k的二叉树,其第k层最多有2 ^(k-1)个结点
    一个层数为k的二叉树,该树最多有(2 ^ k)- 1 个结点
    对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0=n2+1
    具有n个结点的完全二叉树,其高度为log2(n+1)向上取整
    对于一个具有n个节点的完全二叉树,如果按照 从上到下,从左到右的顺序对节点从0开始编号,则对于序号为i的节点:

  • 若i > 0,双亲节点的序号:(i - 1) / 2;若i = 0,则其为根节点,无双亲节点

  • 若2i+1 < n,左孩子序号:2i+1,否则无左孩子

  • 若2i+2 < n,右孩子序号:2i+2,否则无右孩子

  • 二叉树的存储:
    二叉树分为顺序存储和类似链表的链式存储
    二叉树的链式存储是通过一个一个的引用,形如链表
    其有两种表示方法,孩子法和双亲法,孩子法内部有两个引用,即左孩子和右孩子
    双亲表示法除左孩子和右孩子外还有根节点的引用

孩子法——

class Node{
    int val;
    Node left;
    Node right;
}

双亲法——

class Node{
    int val;
    Node root;
    Node left;
    Node right;
}
  • 二叉树的遍历
    下面介绍三种遍历方法:
    前序遍历:从树的根结点开始算起,按照根结点——根的左子树——根的右子树依次遍历
    中序遍历:从树的根结点的左子树开始算起,按照根的左子树——根结点——根的右子树依次遍历
    后序遍历:从树的根结点的左子树开始算起,按照根的左子树——根的右子树——根结点依次遍历

二叉树总结
对于上图的此二叉树,三种遍历结果分别为:
前序遍历:ABDHIECFG
中序遍历:HDIBEAFCG
后序遍历:HIDEBFGCA

代码表示:

public class Tree {
    // 前序遍历
    public void preOrderTraversal(Node root){
        System.out.print(root);
        if(root.left != null){
            preOrderTraversal(root.left);
        }
        if(root.right != null){
            preOrderTraversal(root.right);
        }
    }
    // 中序遍历
    public void inOrderTraversal(Node root){
        if(root.left != null){
            inOrderTraversal(root.left);
        }
        System.out.print(root);
        if(root.right != null){
            inOrderTraversal(root.right);
        }
    }
    // 后序遍历
    public void postOrderTraversal(Node root){
        if(root.left != null){
            postOrderTraversal(root.left);
        }
        if(root.right != null){
            postOrderTraversal(root.right);
        }
        System.out.print(root);
    }
}

求根结点方法:

// 遍历思路-求结点个数
        static int size = 0;
        void getSize1(Node root){
            size++;
            if(root.left != null){
                getSize1(root.left);
            }
            if(root.right != null){
                getSize1(root.right);
            }
        }
        // 子问题思路-求结点个数
        int getSize2(Node root){
            if(root == null){
            return 0;
        }else{
            int rootSize = 1;
            int rootLeftSize = getSize2(root.left);
            int rootRightSize = getSize2(root.right);
            return rootSize+rootLeftSize+rootRightSize;
        }
    }

求叶子结点方法

// 遍历思路-求叶子结点个数
    public static int leafSize = 0;
    void getLeafSize1(Node root){
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null){
            leafSize++;
        }
        if(root.left != null){
            getSize1(root.left);
        }
        if(root.right != null){
            getSize1(root.right);
        }
    }
    // 子问题思路-求叶子结点个数
    int getLeafSize2(Node root){
        if(root == null){
            return 0;
        } else {
            if (root.left == null && root.right == null) {
                return 1;
            } else {
                int leftLeaf = getLeafSize2(root.left);
                int rightLeaf = getLeafSize2(root.right);
                return leftLeaf + rightLeaf;
            }
        }
    }

求第k层结点的个数

// 子问题思路-求第 k 层结点个数
    int getKLevelSize(Node root,int k){
        if(root == null) {
            return 0;
        }
        if(k == 1){
            return 1;
        }else{
            int kLeftLevel = getKLevelSize(root.left,k-1);
            int kRightLevel = getKLevelSize(root.right,k-1);
            return kLeftLevel+kRightLevel;
        }
    }
  • 二叉树的层数遍历
    层序遍历是从第一层的根结点开始,然后从左到右依次遍历每个结点,全部遍历完后再遍历第三层,依次类推,自上到下,自左到右,直到全部遍历完。

二叉树总结

// 层序遍历
    void levelOrderTraversal(Node root){
        if(root == null){
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            Node node = queue.remove();
            System.out.print(node);
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
        }
    }
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(Node root){
        if(root == null){
            return true;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node node = queue.remove();
            if (node == null) {
                return false;
            }
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return true;
    }

以上即是本博客对 二叉树 的总结,随着后续学习的深入还会同步的对内容进行补充和修改,如能帮助到各位博友将不胜荣幸,敬请斧正

本文地址:https://blog.csdn.net/m0_46233999/article/details/109547197

上一篇: java进阶

下一篇: