数据结构——二叉树-阿里云开发者社区

引言

理解二叉树的概念

结点的度：一个结点含有子树的个数称为该结点的度；如上图：A的度为6
树的度：一棵树中，所有结点度的最大值称为树的度；如上图：树的度为6
叶子结点或终端结点：度为 0 的结点称为叶结点；如上图：B、C、H、I…等节点为叶结点

双亲结点（父结点）：若一个结点含有子结点，则这个结点称为其子结点的父结点；如上图：A 是 B 的父结点
孩子结点（子结点）：一个结点含有的子树的根结点称为该结点的子结点；如上图：B 是 A 的孩子结点
根结点：一棵树中，没有双亲结点的结点；如上图：A
结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
树的高度或深度：树中结点的最大层次；如上图：树的高度为4
树的边：边就是树枝的意思，上图的直线就是树枝

一、二叉树的性质

性质一

若规定根节点的层数为1，则一颗非空二叉树的第 k 层上最多有【2^(k - 1)】个节点。

性质二

若规定根节点的层数为1，则深度为 k 的一颗非空二叉树的最大节点数 n 为【2^k - 1】
（等比数列求和 Sn）

性质三 (重要)

对任何一棵二叉树, 如果度为 0 的结点个数为 n0，度为2的分支结点个数为n2，则有公式：【 n0 = n2 + 1 】

（其中，度为0的节点也叫叶子节点）

推导过程：

假设一个二叉树有 n 个节点，那么这个二叉树有 n - 1 条边，那么度为 0 的节点个数为 n0，度为1的节点的个数为 n1，度为2的节点的个数为 n2.

则节点相等公式：n = n0 + n1 + n2 //式1

度为0的节点能产生：0条边

度为1的节点能产生：1条边

度为2的节点能产生：2条边

则边相等公式：n - 1 = 0 + n1 + 2*n2 //式2

由式1和式2，得：

n0 + n1 + n2 - 1 = 0 + n1 + 2*n2
=》 n0 + n1 + n2 = n1 + 2*n2 + 1
=》 n0 = n2 + 1

性质四

具有 n 个节点的满二叉树的深度 k 的值为：【log2(n+1) 】
具有 n 个节点的完全二叉树的深度 k 的值为：【log2(n+1) 向上取整】
（此时可以理解为在完全二叉树中没有将节点放满）

性质五

一个完全二叉树的父节点与子节点有如下关系：

以下性质基于的前提是：节点下标按顺序排列

若父节点下标为 i
那么左边孩子节点下标为   2*i + 1
右边孩子节点下标为       2*i + 2

若子节点下标为     i
那么父节点下标为   (i - 1) / 2
//根节点情况除外

二、与二叉树性质相关的计算题

题目一

某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ B ）

A 不存在这样的二叉树
B 200
C 198
D 199

n0 = n2 + 1 
   = 199 + 1
   = 200

题目二

下列数据结构中，不适合采用顺序存储结构的是（ A ）

A 非完全二叉树
B 堆
C 队列
D 栈

题目三

在具有 2n 个结点的完全二叉树中，叶子结点个数为（ A ）
A n
B n+1
C n-1
D n/2

题目四

一棵完全二叉树的节点数为 531 个，那么这棵树的高度为（ B ）
A 11
B 10
C 8
D 12

k = log2(n+1) 向上取整
=》 k = 9
=》 k = 9 + 1 = 10

题目五

一个具有 767 个节点的完全二叉树，其叶子节点个数为（ B ）
A 383
B 384
C 385
D 386

767 = n0 + n1 + n2
  = n0 + n2
  = n0 + n0 - 1
=》 n0 = 384

三、二叉树的遍历

二叉树的遍历：是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。

1. 前序遍历

前序遍历又称为先序遍历

根节点=》根的左子树=》根的右子树

逻辑：

① 从根节点出发，遇到某双亲节点，就直接打印

② 之后将所有的左子树都先走一遍，符合左子树就打印节点

③ 遇到空节点就返回，返回的过程，不作任何操作

④ 最后再走所有的右子树，右子树也遵照上述原则

2. 中序遍历

根的左子树=》根节点=》根的右子树
• 1

逻辑：

① 从根节点出发，遇到某双亲节点，先不打印

② 之后将所有的左子树都先走一遍，符合左子树先不打印

③ 遇到空节点就返回，返回的过程中，若遇到某双亲节点，就直接打印

④ 最后再走所有的右子树，右子树也遵照上述原则

3. 后序遍历

根的左子树=》根的右子树=》根节点
• 1

逻辑：

① 从根节点出发，遇到某双亲节点，先不打印

② 之后将所有的左子树都先走一遍，符合左子树先不打印

③ 接着，走当前双亲节点的右子树，如果走完某个分支的右子树，回到双亲节点，再打印

总结三种遍历方式的特点

三种方式的搜寻路线是一样的，然而在面对某个节点的时候，我们需要判断当前节点的身份，再依照不同的规则进行打印。

也就是说：三种方式路线相同，但打印的先后顺序不同。

其中前序最好理解，按照路线走，遇到双亲节点就打印。

比方说，我现在给定一个二叉树，不管三种遍历方式是怎么打印的，那么它的搜寻路线实际上就是按下图框框的序号执行的

4. 层序遍历

层序遍历的思想较为简单，逻辑就是从上到下，从左到右打印。

本篇博客后面会实现层序遍历的代码。

四、与二叉树遍历相关的题目

题目一

某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为( A )
A. ABDHECFG
B. ABCDEFGH
C. HDBEAFCG
D. HDEBFGCA

题目二

二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG.则二叉树根结点为( A )
A. E
B. F
C. G
D. H

题目三

设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为( D )
A. adbce
B. decab
C. debac
D. abcde

题目四

某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出(同一层从左到右)的序列为( A )
A. FEDCBA
B. CBAFED
C. DEFCBA
D. ABCDEF

五、二叉树的基本操作——代码实现

1. 利用穷举的方式初始化一个二叉树

2. 前序、中序、后序遍历

3. 求二叉树中所有节点的个数

4. 求二叉树中叶子节点的个数

5. 求二叉树某一层节点的个数

6. 层序遍历

7. 判断一棵树是不是完全二叉树

8. 获取二叉树的高度

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

创建两个类，一个类是 TreeNode，表示二叉树某个节点的信息

另一个类是 Tree，表示基于对整个二叉树进行操作

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class Tree {
    //初始化一个二叉树
    public TreeNode initialTree(){
        TreeNode A = new TreeNode(1);
        TreeNode B = new TreeNode(2);
        TreeNode C = new TreeNode(3);
        TreeNode D = new TreeNode(4);
        TreeNode E = new TreeNode(5);
        TreeNode F = new TreeNode(6);
        TreeNode G = new TreeNode(7);
        TreeNode H = new TreeNode(8);
        TreeNode I = new TreeNode(9);
        A.left = B;
        A.right = C;
        //B.left = D;
        B.right = E;
        //C.left = F;
        //C.right = G;
        return A;
    }
    //前序遍历
    //递归代码
    public void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //通过栈实现的非递归代码
    public void preorder2(TreeNode root){
        if(root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                System.out.print(cur.val+" ");
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }
    //中序遍历
    public void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    public void inOrder2(TreeNode root){
        if(root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.print(top.val + " ");
            cur = top.right;
        }
    }
    //后序遍历
    public void postOder(TreeNode root){
        if(root == null){
            return;
        }
        postOder(root.left);
        postOder(root.right);
        System.out.print(root.val+" ");
    }
    public void postOrder2(TreeNode root){
        if(root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode sign = null;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right == null || top.right == sign){
                stack.pop();
                System.out.print(top.val + " ");
                sign = top;
            }else{
                cur = top.right;
            }
        }
    }
    //求二叉树中所有的节点个数
    public int count;
    public int size(TreeNode root){
        if(root == null) return 0;
        count++;
        size(root.left);
        size(root.right);
        return count;
    }
    //求二叉树中叶子节点的个数
    public int leafCount;
    public int getLeafNodeCount(TreeNode root){
        if(root == null) return 0;
        if(root.left == null && root.right == null){
            leafCount++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return leafCount;
    }
    //求k层的节点个数
    public int levelCount;
    public int getKLevelNodeCount(TreeNode root, int k){
        if(root == null || k<= 0) return 0;
        if(k == 1){
            return ++levelCount;
        }
        getKLevelNodeCount(root.left,k-1);
        getKLevelNodeCount(root.right, k-1);
        return levelCount;
    }
    //层序遍历
    public void levelOrder(TreeNode root){
        if(root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            root = queue.poll();
            System.out.print(root.val + " ");
            if(root.left != null){
                queue.offer(root.left);
            }
            if(root.right != null){
                queue.offer(root.right);
            }
        }
    }
    //判断一棵树是不是完全二叉树
    //方法1 //错误的解法
    public boolean isCompleteTree1(TreeNode root){
        if(root == null) return true;
        boolean ret1 = isCompleteTree1(root.left);
        boolean ret2 = isCompleteTree1(root.right);
        if(root.left == null && root.right != null){
            return false;
        }
        return ret1 && ret2;
    }
    //方法2
    //通过队列实现的代码
    public boolean isCompleteTree2(TreeNode root){
        if(root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(true){
            TreeNode top = queue.poll();
            if(top != null){
                queue.offer(top.left);
                queue.offer(top.right);
            }else{
                break;
            }
        }
        while(!queue.isEmpty()){
            if(queue.peek() != null){
                return false;
            }else{
                queue.poll();
            }
        }
        return true;
    }
    //获取二叉树的高度
    public int getHeight(TreeNode root){
        if(root == null) return 0;
        int lHeight = getHeight(root.left);
        int rHeight = getHeight(root.right);
        return Math.max(lHeight,rHeight) + 1;
    }
    //检测值为 val 的元素是否存在
    //如果存在，返回该 val 的节点，如果不存在，返回 null
    public TreeNode find(TreeNode root, int findVal){
        if(root == null) return null;
        if(root.val == findVal) return root;
        TreeNode leftNode = find(root.left, findVal);
        //下面 if 不能用 leftNode.val == findVal 进行判断，
        //因为这会造成：在还没有遍历完二叉树的全部元素时，就已经造成了空指针异常
        if(leftNode != null){
            return leftNode;
        }
        TreeNode rightNode = find(root.right, findVal);
        if(rightNode != null){
            return rightNode;
        }
        return null;
    }
}

创建一个类 Test，对二叉树进行测试

public class Test {
    public static void main(String[] args) {
        Tree tree = new Tree();
        TreeNode root = tree.initialTree();
        System.out.println("----------------前序遍历----------------");
        tree.preOrder(root);
        System.out.println();
        System.out.println("----------------中序遍历----------------");
        tree.inOrder(root);
        System.out.println();
        System.out.println("----------------后序遍历----------------");
        tree.postOrder2(root);
        System.out.println();
        System.out.println();
        System.out.println("----------------二叉树中所有节点的个数----------------");
        System.out.println(tree.size(root));
        System.out.println("----------------二叉树中叶子节点的个数----------------");
        System.out.println(tree.getLeafNodeCount(root));
        System.out.println("----------------二叉树某一层节点的个数----------------");
        System.out.println(tree.getKLevelNodeCount(root, 2));
        System.out.println("----------------层序遍历----------------");
        tree.levelOrder(root);
        System.out.println();
        System.out.println("---------------- 判断一棵树是不是完全二叉树----------------");
        System.out.println(tree.isCompleteTree2(root));
        System.out.println("----------------获取二叉树的高度----------------");
        System.out.println(tree.getHeight(root));
        System.out.println("----------------检测值为 val 的元素是否存在----------------");
        try{
            TreeNode node = tree.find(root,5);
            System.out.println(node.val);
        }catch (NullPointerException error){
            error.printStackTrace();
            System.out.println("您所找的元素在二叉树中没有对应的节点");
        }
    }
}

输出结果：

数据结构——二叉树

引言