二叉树总结_Java_移动技术网

二叉树

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

一、树结构：
树形结构是一种非线性结构，不同于线性表，它是一层次的嵌套结构，因为其内外层结构相似，所以经常使用递归表示。其元素之间为一对多的关系，数状图是一种典型的树形结构。
在这里插入图片描述
如上图所示，就是一棵树，方向由上往下延伸
每一个圆圈叫做结点，最上面的结点（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;
    }