数据结构复习：二叉树的概念、性质与遍历实现

4. 树的表现形式

树型结构相对线性表来说比较复杂，有很多种表示方式：双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法等等；其中最常用的就是孩子兄弟表示法：

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

二、二叉树

上面我们了解了什么是树型结构，接下来看看什么是二叉树

2.1 二叉树的概念

二叉树是一种树型结构，但是二叉树中的每个结点最多有两个子结点，分别称为左结点和右结点

二叉树的特点：

• 二叉树不存在度大于 2 的结点
• 二叉树有左子树和右子树之分，所以次序是不能颠倒的，因此二叉树是一颗有序树

2.2 特殊的二叉树

上图演示的其实是一个最普通的二叉树，在二叉树的概念中有两种二叉树比较特殊，我们一起来看看吧

(1) 满二叉树

当一棵二叉树，如果每一层的结点都达到最大值，那么这棵树就是满二叉树：

从上图可以发现：该树的层数为 3，结点总数为 2^3-1=7，那么也就是说，如果一棵二叉树的层数为 K，结点总数为 2^K-1，那么它就是一棵满二叉树。

(2) 完全二叉树

假设一个二叉树的深度为 n，那么除了第 n 层，其他每一层的节点数都达到了最大个数，最后一层的结点按照从左到右的顺序，依次进行排列：

满二叉树是一个特殊的完全二叉树，并且完全二叉树是效率很高的数据结构~

2.3 二叉树的性质

根据下图我们来分析一下二叉树的性质

1. 若规定根结点的层数为 1，那么一棵非空二叉树的第 i 层最多有 2^(i-1) 个结点：例如上图的满二叉树，第 4 层有 2^(4-1)=8 个结点；

2. 若规定只有根结点的二叉树深度为 1，则深度为 K 的二叉树最大结点数是 2^K-1：例如上图的满二叉树，深度为 4，那么该树（刚好是满二叉树）的最大结点数就是 2^4-1=15 个结点；

3. 对任何一棵二叉树，如果其叶子结点个数为 n0，度为 2 的非叶子结点个数为 n0=n2+1：

从上图可以看到：叶子结点的个数为 5 个，度为 2 的非叶子结点的个数为 4 个（n0=n2+1）;

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

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

• 若 i>0，双亲序号：(i-1)/2；i=0，i 为根结点编号，无双亲结点；

• 若 2i+1<n，左孩子序号：2i+1，否则无左孩子；

• 若 2i+2<n，右孩子序号：2i+2，否则无右孩子；

以上就是二叉树最基本的性质啦

2.4 二叉树的创建

根据上图我们来创建一个二叉树：

public class Binary_Tree {
    static class TreeNode{
        public TreeNode left;//表示左孩子
        public TreeNode right;//表示右孩子
        char value;//表示存放数据的变量
        public TreeNode(char val) {//结点的构造方法
            this.value = val;
        }
    }
    public static TreeNode createTree(){
        //创建结点
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        //连接结点
        A.left=B; A.right=C;
        B.left=D; B.right=E;
        C.left=F; C.right=G;
        //返回根节点
        return A;
    }
    public static void main(String[] args) {
        TreeNode tree=createTree();//创建二叉树
    }
}

那么这样一棵二叉树就创建好了，接下来我们来看看该如何遍历这棵二叉树吧

2.5 二叉树的遍历

所谓遍历 (Traversal) 就是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。二叉树的遍历主要有三种方式：前序遍历、中序遍历、后序遍历，我们来看看这三种遍历方式是如何遍历的

(1) 前序遍历

前序遍历的顺序是：根节点--->左子树---->右子树的顺序进行遍历的，对于每棵子树也是按照这样的顺序进行遍历：

代码实现：

public static void preOrder(TreeNode root){
    //判断结点是否为空
    if(root==null)return ;
    System.out.print(root.value);//打印根节点的值
    //遍历左子树
    preOrder(root.left);
    //遍历右子树
    preOrder(root.right);
}
public static void main(String[] args) {
    TreeNode tree=createTree();//创建二叉树
    //前序遍历二叉树
    preOrder(tree);
}

运行结果：

具体的遍历过程在上述的图中已经讲过啦，这里就不在论述~

(2) 中序遍历

中序遍历的遍历顺序是：根的左子树--->根节点--->根的右子树。对于每棵子树也是按照这样的顺序进行遍历：

代码实现：

public static void inOrder(TreeNode root){
    //判断结点是否为空
    if(root==null)return ;
    //按照左子树--->根结点---->右子树的顺序进行遍历
    //遍历左子树
    inOrder(root.left);
    //打印根节点
    System.out.print(root.value);
    //遍历右子树
    inOrder(root.right);
}
public static void main(String[] args) {
    TreeNode tree=createTree();//创建二叉树
    //中序遍历二叉树
    inOrder(tree);
}

运行结果：

(3) 后序遍历

后序遍历的遍历顺序是：根的左子树--->根的右子树--->根节点。对于每棵子树也是按照这样的顺序进行遍历：

代码实现：

public static void PostOrder(TreeNode root){
    //判断结点是否为空
    if(root==null)return;
    //按照左子树-->右子树-->根节点的顺序进行遍历
    //遍历左子树
    PostOrder(root.left);
    //遍历右子树
    PostOrder(root.right);
    //打印根结点
    System.out.print(root.value);
}
public static void main(String[] args) {
    TreeNode tree=createTree();//创建二叉树
    //后序遍历二叉树
    PostOrder(tree);
}

运行结果：

(4) 三种遍历方式的特点

从表格中不难看出通过前序遍历、后续遍历，我们能快速的知道根节点是谁，那么则可以得出结论：

前序遍历和后序遍历的结果能够确定根是谁，而中序遍历的根节点位置是在中间，说明根节点 (A) 的左边就是根结点的左子树元素 (DBE)，根结点 (A) 的右边就是根结点的右子树元素 (FCG)；

2.6 二叉树的基本操作

以下介绍的是使用二叉树的过程中一些常见的操作

1. 获取树中结点的个数

public static int size(TreeNode root){
    //判断结点是否为空
    if(root==null)return 0;
    //如果结点不为空，那么 usedsize++
    //遍历左子树
    int left=size(root.left);//记录左子树的结点个数
    //遍历右子树
    int right=size(root.right);//记录右子树的结点个数
    return left+right+1;//返回左子树结点个数和右子树结点个数 +1（加上当前结点）
}
public static void main(String[] args) {
    TreeNode tree=createTree();//创建二叉树
    System.out.println(size(tree));
}

运行结果：

2. 获得叶子结点个数

public static int getLeafTreeNodeCount(TreeNode root){
    //判断结点是否为空
    if(root==null)return 0;
    //判断当前结点是否为叶子结点
    if(root.left==null&&root.right==null){
        return 1;//是就返回 1
    }
    //不是就当前结点左子树的叶子结点个数和右子树的叶子结点个数
    return getLeafTreeNodeCount(root.left)+getLeafTreeNodeCount(root.right);
}
public static void main(String[] args) {
    TreeNode tree=createTree();//创建二叉树
    System.out.println(getLeafTreeNodeCount(tree));
}

运行结果：

3. 获得第 k 层结点的个数

public static int getKLevelTreeNodeCount(TreeNode root,int k){
    //判断结点是否为空或者 k 是否小于 1
    if(root==null||k<1)return 0;
    //如果 k=1，表示是要查找的层次，返回 1
    if(k==1)return 1;
    //递归左右子树，直到 k==1，递归到了要查找的层次
    //就返回左子树的 k 层次的节点数 + 右子树的 K 层次的节点数==k 层次总的节点数
    return getKLevelTreeNodeCount(root.left,k-1)+getKLevelTreeNodeCount(root.right,k-1);
}
public static void main(String[] args) {
    TreeNode tree=createTree();//创建二叉树
    System.out.println(getKLevelTreeNodeCount(tree,2));
}

运行结果：

4. 获取二叉树的高度

public static int getHeight(TreeNode root){
    //判断该结点是否为空
    if(root==null)return 0;
    //如果不为空，递归左子树和右子树，返回左子树和右子树的深度的最大值加上当前结点（深度 1）
    return Math.max(getHeight(root.left),getHeight(root.right))+1;
}
public static void main(String[] args) {
    TreeNode tree=createTree();//创建二叉树
    System.out.println(getHeight(tree));
}

运行结果：

5. 检测值为 val 的元素是否存在

public static TreeNode findvalue(TreeNode root,char val){
    //判断结点是否为空
    if(root==null)return null;
    //判断当前结点的值是否等于 val
    if(root.value==val)return root;
    //如果当前结点的值不是 val，就去左子树中找
    TreeNode leftNode=findvalue(root.left,val);
    //如果左子树找到了就返回
    if(leftNode!=null)return leftNode;
    //如果左子树找不到就去右子树中找
    TreeNode rightNode=findvalue(root.right,val);
    //如果右子树找到了就返回
    if(rightNode!=null)return rightNode;
    //找不到返回 null
    return null;
}
public static void main(String[] args) {
    TreeNode tree=createTree();//创建二叉树
    System.out.println(findvalue(tree,'C').value);
}

运行结果：

6. 层序遍历

画图分析：

这里实现层序遍历需要借助队列来实现，如果对队列不熟悉的话可以看一下上一期博客：栈和队列

代码实现层序遍历：

public static void levelOrder(TreeNode root){
    if(root==null)return ;
    //创建队列
    Queue<TreeNode> queue=new LinkedList<>();
    //将根结点放入队列中
    queue.offer(root);
    while(!queue.isEmpty()){
        //如果队列为空说明遍历完了
        TreeNode cur=queue.poll();//弹出元素
        System.out.print(cur.value);
        //将弹出结点的孩子结点放入队列
        if(cur.left!=null){
            queue.offer(cur.left);
        }
        if(cur.right!=null){
            queue.offer(cur.right);
        }
    }
}
public static void main(String[] args) {
    TreeNode tree=createTree();//创建二叉树
    levelOrder(tree);
}

运行结果：

以上就是二叉树的一些基本操作啦~