数据结构–二叉树

• 🍁 个人主页：爱编程的Tom
• 💫 本篇博文收录专栏：Java专栏
• 👉 目前其它专栏：c系列小游戏     c语言系列–万物的开始_  等等             
• 🎉 欢迎 👍点赞✍评论⭐收藏💖三连支持一下博主🤞
• 🧨现在的沉淀就是对未来的铺垫🎨 

目录

前言

1.树的基本理论知识

2.树的表示形式

3.二叉树 

3.1 二叉树是什么 

3.2 两种特殊二叉树

3.3 二叉树相关性质 

3.4 二叉树的存储 

3.5 二叉树的基本操作 

前言

本篇博客将讲述二叉树这个神奇的数据结构，领略其中的逻辑和思维，并学会加以运用！

1.树的基本理论知识

结点的度：一个结点含有子树的个数称为该结点的度； 如上图：A的度为6

树的度：一棵树中，所有结点度的最大值称为树的度； 如上图：树的度为6

叶子结点或终端结点：度为0的结点称为叶结点； 如上图：B、C、H、I…等节点为叶结点

双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点

孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点

根结点：一棵树中，没有双亲结点的结点；如上图：A

结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推

树的高度或深度：树中结点的最大层次； 如上图：树的高度为4 树的以下概念只需了解，在看书时只要知道是什么意思即可：

非终端结点或分支结点：度不为0的结点； 如上图：D、E、F、G…等节点为分支结点

兄弟结点：具有相同父结点的结点互称为兄弟结点； 如上图：B、C是兄弟结点

堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点

结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先

子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙

森林：由m（m>=0）棵互不相交的树组成的集合称为森林  

2.树的表示形式

树的表示形式有很多种：如双亲表示法， 孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。 

class Node {
    int value; // 树中存储的数据
    Node firstChild; // 第一个孩子引用
    Node nextBrother; // 下一个兄弟引用
}

图示结果如下：

这里重点学习二叉树的相关知识！！！ 

3.二叉树 

3.1 二叉树是什么 

一棵二叉树是结点的一个有限集合，

该集合：为空或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。 

从上图可以看出：

1. 二叉树不存在度大于2的结点

2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树  

其它类型的二叉树如下图所示：

3.2 两种特殊二叉树

1. 满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是2^k-1 ，则它就是满二叉树。

2. 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n 个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 

这里给出两种特殊树的图示： 

3.3 二叉树相关性质 

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1)(i>0)个结点

2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是2^k-1 (k>=0)

3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1

4. 具有n个结点的完全二叉树的深度k为log2(n+1) 上取整

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i 的结点有：

• 若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
• 若2i+1，左孩子序号：2i+1，否则无左孩子
• 若2i+2，右孩子序号：2i+2，否则无右孩子  

3.4 二叉树的存储 

二叉树的存储结构分为：顺序存储和类似于链表的链式存储。

这里重点先了解链式存储，二叉树的链式存储是通过一个一个的节点引用起来的。

常见的表示方式有二叉和三叉表示方式，具体如下： 

// 孩子表示法
class Node {
    int val; // 数据域
    Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
    Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
}
 
// 孩子双亲表示法
class Node {
    int val; // 数据域
    Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
    Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
    Node parent;    // 当前节点的根节点
}

3.5 二叉树的基本操作 

要对二叉树有基本操作，我们得先创建一棵二叉树，这里提供一种适合初学者快速学习二叉树的创建方式。

public class BinaryTree{
    public static class BTNode{
        BTNode left;
        BTNode right;
        int value;
        
        BTNode(int value){
            this.value = value;
       }
   }
    
    private BTNode root;
public void createBinaryTree(){
        BTNode node1 = new BTNode(1);
        BTNode node1 = new BTNode(2);
        BTNode node1 = new BTNode(3);
        BTNode node1 = new BTNode(4);
        BTNode node1 = new BTNode(5);
        BTNode node1 = new BTNode(6);
        
        root = node1;
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node5.right = node6;
   }
}

二叉树真正的创建方式也在此提供：

//二叉树的创建和遍历
    class TreeNode {
    public char val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(char val) {
        this.val = val;
    }
}

public class Main {

    public static int i = 0;

    private static TreeNode  createTree(String str) {
        TreeNode root = null;
        char ch = str.charAt(i);
        if (ch != '#') {
            root = new TreeNode(ch);
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        } else {
            i++;
        }
        return root;

    }
    public static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            TreeNode root = createTree(str);
            inOrder(root);
        }
    }
}

有了二叉树之后，我们来看具体的操作有哪些：

// 获取树中节点的个数
int size(Node root);
 
// 获取叶子节点的个数
int getLeafNodeCount(Node root);
 
// 子问题思路-求叶子结点个数
 
// 获取第K层节点的个数
int getKLevelNodeCount(Node root,int k);
 
// 获取二叉树的高度
int getHeight(Node root);
 
// 检测值为value的元素是否存在
Node find(Node root, int val);
 
//层序遍历
void levelOrder(Node root);
 
// 判断一棵树是不是完全二叉树
boolean isCompleteTree(Node root);

这里方便大家深入了解二叉树基本操作的原理，实现了上述操作供大家参考：

 public int size(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int tmp = size2(root.left) + size2(root.right) + 1;
        return tmp;
    }
public int leafSize;

    public int getLeafNodeCount2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount2(root.left)
                + getLeafNodeCount2(root.right);
    }
 public int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getKLevelNodeCount(root.right, k - 1) + getKLevelNodeCount(root.left, k - 1);
    }

    // 获取二叉树的高度
    //子问题求解
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        //return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
        return Math.max(leftHeight, rightHeight) + 1;
    }

    // 检测值为value的元素是否存在
    public TreeNode find(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        TreeNode leftVal = find(root.left, val);
        if (leftVal != null) {
            return leftVal;
        }
        TreeNode rightVal = find(root.right, val);
        if (rightVal != null) {
            return rightVal;
        }
        return null;
    }
//层序遍历，利用队列思想
    public void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur  = queue.poll();
            System.out.print(cur.val+" ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
 // 判断一棵树是不是完全二叉树
   public boolean isCompleteTree(TreeNode root) {
       if (root == null) {
           return true;
       }
       Queue queue = new LinkedList();
       queue.offer(root);
       while (!queue.isEmpty()) {
           TreeNode cur = queue.poll();
           if (cur != null) {
               queue.offer(cur.left);
               queue.offer(cur.right);
           } else {
               break;
           }
       }
       while (!queue.isEmpty()) {
           TreeNode cur = queue.poll();
           if (cur != null) {
               return false;
           }
       }
       return true;
   }

在了解完二叉树的基本知识点之后，建议可以去做一些OJ练习题来强化自己对于二叉树这部分知识的掌握。相信二叉树的知识一定可以掌握，对于后续继续学习数据结构也会有极大的提升！