树、二叉树 – 章鱼哥学习小课堂

第六章、树和二叉树

6.1、树

❗6.1.1、树的定义

1、定义

1、树是n个节点的有限集，显然，树的定义是一个递归的定义

2、如果n=0则称为空树

3、如果n>0则满足以下两个条件

4、有且仅有一个特定的称为根的节点

5、其余节点可分为m(m>=0)个互不相交的有限集，其中每一个集本身又是一棵树，称为根的子树。

2、树的其他表示方式

1、嵌套集合

2、凹入表示

3、广义表也阔以表示

6.1.2、树的基本术语

1、基本概念

1、有序树：树中节点的各子树从左到右有次序（最左边为第一个孩子）。然后一次按层来是有序的

2、无序树：树中节点的各子树无次序。

3、森林：是m(m>=0)互不相交的树的集合。

4、把根节点删除树就变成了森林。

5、一棵树是特殊的森林。

6、树一定是森林，森林不一定是树

2、树结构和线性结构的比较

6.2、二叉树

6.2.1、为什么要重点研究每结点最多只有两个”叉“的树？

1、二叉树结构最简单，规律性最强

2、可以证明，所有树都能转化为唯一对应的二叉树，不失一般性。

3、普通树（多叉树）若不转化为二叉树，则运算很难实现。

4、二叉树非常重要，许多对二叉操作算法简单，任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。

❗6.2.2、定义

1、二叉树是n（n>=0)个结点的有限集，它或者是空集（n=0)，或者由一个根节点及两颗互不相交的分别称作这个根的左子树和右子树。

6.2.3、特点

1、每个结点最多两个孩子（不能大于2个结点）

2、子树有左右之分，次序不能颠倒。

3、二叉树可以是空集合，根可以有空的左子树，或空的右子树。

6.2.4、注意

1、二叉树不是树的特殊情况，它们是两个概念。

2、二叉树分左子树和右子树，是有次序、有位置的。

3、树当结点只有一个时，就不区分左右的次序

4、这就是两个树之间最大的区别。

6.2.5、二叉树的五中形态

6.2.6、案例引入

1、数据压缩问题

1、这里哈夫曼树会涉及到

2、问题引入

2、利用二叉树求解表达式的值

6.2.7、树和二叉树的抽象数据类型定义

1、数据类型

❗6.2.8、二叉树的性质

1、性质一

1、性质如图

2、第i层层至少有1个节点

2、性质二

1、性质如下

2、第k层至少有k个节点

3、性质三

1、叶子节点：就是没有后继节点了

2、度：有几个分支的节点

3、就是求叶子节点有几个

4、叶子节点 = 度为x的结点树+1

5、总边数

①从上往下看，总边数=2个度的数量（就是有两个叶子结点）2+1个度的的数量（1个叶子节点）\1

②从下往上看，总边数 = 所有的结点-1

5、图示

4、满二叉树介绍

1、图示

2、满二叉树在同样深度的二叉树中节点个数最多

3、满二叉树在同样深度中子叶结点个数最多。

5、完全二叉树介绍

1、完全二叉树定义

2、满二叉树是完全二叉树，完全二叉树不一定是满二叉树。

3、完全二叉树是需要，连续，位置对应。从左到右。

4、完全二叉树和满二叉树的位置需要一一对应。否则就不是完全二叉树

5、完全二叉树特点

6、性质四

1、就是求n个节点的完全二叉树的深度

7、性质五

1、主要讲的是双亲结点编号与孩子结点编号之间的关系

2、这里的 i 是结点

3、就是知道一个结点的编号是多少，就知道这个编号的双亲、左孩子、右孩子结点的编号了

❗6.2.9、二叉树的存储结构

1、二叉树的顺序存储结构

1、用数组来实现

2、缺点：二叉树为了表示双亲关系，会存储空的节点。

3、最坏情况

①假设只有右单只

②如图

4、特点：节点间关系蕴含在存储位置中，浪费空间。比较适合满二叉树和完全二叉树。

5、例子

2、二叉树的链式存储结构

1、特点

2、存储结构定义

3、在n个节点的二叉链表中，有n+1个空指针域

4、证明：空指针数目=2n-(n-1)=n+1;

5、例子

6.2.10、三叉链表

❗6.2.11、遍历二叉树

1、遍历定义

1、顺着某个路径进行搜索访问二叉树中的每一个节点，每个节点被访问一次，而且仅被访问一次（又称为：周游）

2、一般不破坏新的结构

2、遍历目的

1、得到树中所有节点的一个线性排序

3、遍历的用途

1、树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切

4、遍历方法

1、重点研究前三种

2、算法步骤

3、先序遍历二叉树

（1）口诀：根左右

（2）例子

4、中序遍历二叉树

（1）口诀：左根右

（2）例子

5、后序遍历二叉树

（1）口诀：左右根

（2）例子

6、例子

5、根据遍历序列确定二叉树

1、例题：知道前序、中序遍历顺序，求二叉树。

2、例题：知道中序，后序，求二叉树。

6、遍历算法的实现—先序遍历

1、图解

2、伪代码

3、运行的过程

7、遍历算法的实现—中序遍历

1、图解

2、伪代码

8、遍历算法的实现—后序遍历

1、图解

2、伪代码

9、java代码实现前序、中序、后序遍历二叉树（递归）

package Tree_;

public class Test {

//    进行测试
    public static void main(String[] args) {
        //定义二叉树
//        1.创建二叉树节点
        Node nodeA = new Node("A");
        Node nodeB = new Node("B");
        Node nodeD = new Node("D");
        Node nodeE = new Node("E");
        Node nodeH = new Node("H");
        Node nodeL = new Node("L");
        Node nodeM = new Node("M");
        Node nodeJ = new Node("J");
        Node nodeI = new Node("I");

//        2.确定二叉树位置
        nodeA.left = nodeB;
        nodeA.right=nodeD;
        nodeB.left =nodeE;
        nodeE.right=nodeL;
        nodeD.left=nodeH;
        nodeD.right=nodeJ;
        nodeH.left=nodeM;
        nodeH.right = nodeI;

//        开始执行
        preOrder1(nodeA);
        System.out.println("前序执行完毕");
        midOrder1(nodeA);
        System.out.println("中序执行完毕");
        postOrder1(nodeA);
    }

    //前序遍历
    public static void preOrder1(Node root){
        if(root==null){
            return ;
        }
        System.out.print(root.value+"-->");
        preOrder1(root.left);
        preOrder1(root.right);
    }

    //中序遍历
    public static void midOrder1(Node root){
        if(root==null){
            return ;
        }

        midOrder1(root.left);
        System.out.print(root.value+"-->");
        midOrder1(root.right);
    }

    //后序遍历
    public static void postOrder1(Node root){
        if(root==null){
            return ;
        }

        postOrder1(root.left);
        postOrder1(root.right);
        System.out.print(root.value+"-->");
    }

    //节点的结构
    public static class Node{
        public String value;
        public Node left;
        public Node right;

        public Node(String value){
            this.value=value;
        }
    }

}

10、遍历算法的分析

11、二叉树遍历（非递归）

1、遍历二叉树—中序思路

（1）会遇到左根右，根不能输出，需要保存。保存用到栈，先进后出，后进先出。

（2）java代码实现

/**
 * 非递归遍历二叉树
 */
public class Test2 {

    public static void main(String[] args) {
        //定义二叉树
//        1.创建二叉树节点
        Node nodeA = new Node("A");
        Node nodeB = new Node("B");
        Node nodeD = new Node("D");
        Node nodeE = new Node("E");
        Node nodeH = new Node("H");
        Node nodeL = new Node("L");
        Node nodeM = new Node("M");
        Node nodeJ = new Node("J");
        Node nodeI = new Node("I");

//        2.确定二叉树位置
        nodeA.left = nodeB;
        nodeA.right=nodeD;
        nodeB.left =nodeE;
        nodeE.right=nodeL;
        nodeD.left=nodeH;
        nodeD.right=nodeJ;
        nodeH.left=nodeM;
        nodeH.right = nodeI;

        //开始测试
        preOrder2(nodeA);
        System.out.println();
        midOrder2(nodeA);
        System.out.println();
        postOrder2(nodeA);
    }
    //前序遍历
    public static void preOrder2(Node root){
        if(root==null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            Node node = stack.pop();
            System.out.print(node.value+"-->");
            if (node.right!=null){
                stack.push(node.right);
            }
            if(node.left !=null){
                stack.push(node.left);
            }
        }
    }

    //中序遍历
    public static void midOrder2(Node root){
        if(root==null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        Node cur = root;//临时节点存储
        while (!stack.isEmpty() || cur!=null){
            while (cur!=null){
                stack.push(cur);//是根左右，如果左边下面还有子树，就把该节点存入到栈中
                cur = cur.left;//去找左边下面的子树
            }
            Node node =stack.pop();//把取出的节点存到node中
            System.out.print(node.value+"-->");
            if(node.right!=null){
                cur = node.right;//吧取出的右节点做个标记
            }
        }
    }

    //后序遍历
    public static void postOrder2(Node root){
        if(root==null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        Stack<Node> stac2 = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            Node node = stack.pop();
            stac2.push(node);
            if(node.left !=null){
                stack.push(node.left);
            }
            if (node.right!=null){
                stack.push(node.right);
            }
        }
        while (!stac2.isEmpty()){

            System.out.print(stac2.pop().value+"-->");
        }

    }

    //定义数据结构

    //节点的结构
    public static class Node{
        public String value;
        public Node left;
        public Node right;

        public Node(String value){
            this.value=value;
        }
    }

}

12、二叉树遍历（层次遍历）

1、概念：对一个二叉树，从根节点开始，按从上到下、从左到右的顺序访问每一个节点。

2、思路

（1）利用队列，先进先出

（2）出队的同时，将孩子结点入队

（3）如图

3、java代码实现

package Tree_;

import java.util.LinkedList;
import java.util.Queue;

public class BfsTest {

        public static void main(String[] args) {
        //定义二叉树
//        1.创建二叉树节点
        Node nodeA = new Node("A");
        Node nodeB = new Node("B");
        Node nodeD = new Node("D");
        Node nodeE = new Node("E");
        Node nodeH = new Node("H");
        Node nodeL = new Node("L");
        Node nodeM = new Node("M");
        Node nodeJ = new Node("J");
        Node nodeI = new Node("I");

//        2.确定二叉树位置
        nodeA.left = nodeB;
        nodeA.right=nodeD;
        nodeB.left =nodeE;
        nodeE.right=nodeL;
        nodeD.left=nodeH;
        nodeD.right=nodeJ;
        nodeH.left=nodeM;
        nodeH.right = nodeI;

        //开始测试
        bfs(nodeA);
    }

    //层次遍历
    public static void bfs(Node root){
        if(root==null){
            return;
        }
        Queue<Node > queue = new LinkedList();
        queue.add(root);
        while (!queue.isEmpty()){
            Node node = queue.poll();//把队列中的元素放入
            System.out.print(node.value+"-->");
            if(node.left!=null){
                queue.add(node.left);
            }
            if(node.right!=null){
                queue.add(node.right);
            }
        }

    }

    //节点的结构
    public static class Node{
        public String value;
        public Node left;
        public Node right;

        public Node(String value){
            this.value=value;
        }
    }
}

13、二叉树遍历算法（二叉树的建立）

1、思路

2、因为以上先序序列有两种二叉树，所以需要补充空节点，来确定二叉树唯一性

（1）可以用空格、或者#字符

（2）例子

3、java代码实现

14、二叉树遍历算法—复制二叉树

1、思路

2、java代码实现

15、二叉树遍历算法的应用—计算二叉树深度

1、思路

2、java代码实现

（1）代码简化，其余部分和二叉树节点总数一致，以下展示重点代码

    public int Depth(Node root){
        if(root==null){
            return 0;
        }else {
            int m = preOrder1(root.left);
            int n = preOrder1(root.right);
            if(m>n){
                return (m+1);
            }else {
                return (n+1);
            }
        }

    }

16、二叉树遍历算法应用—计算二叉树节点总数

1、思路

2、java代码实现

package Tree_;

/**
 * 计算二叉树节点总数
 */
public class Test3 {
    public static void main(String[] args) {

                //定义二叉树
//        1.创建二叉树节点
        Node nodeA = new Node("A");
        Node nodeB = new Node("B");
        Node nodeD = new Node("D");
        Node nodeE = new Node("E");
        Node nodeH = new Node("H");
        Node nodeL = new Node("L");
        Node nodeM = new Node("M");
        Node nodeJ = new Node("J");
        Node nodeI = new Node("I");

//        2.确定二叉树位置
        nodeA.left = nodeB;
        nodeA.right=nodeD;
        nodeB.left =nodeE;
        nodeE.right=nodeL;
        nodeD.left=nodeH;
        nodeD.right=nodeJ;
        nodeH.left=nodeM;
        nodeH.right = nodeI;

//        开始执行
        Test3 test3 = new Test3();
        System.out.println(test3.preOrder1(nodeA));
    }

        //前序遍历
    public int preOrder1(Node root){
        if(root==null){
            return 0;
        }else {
            return preOrder1(root.left) +preOrder1(root.right)+1;
        }

    }
    //节点的结构
    public static class Node{
        public String value;
        public Node left;
        public Node right;

        public Node(String value){
            this.value=value;
        }
    }
}

17、二叉树遍历算法应用—计算二叉树叶子节点

1、思路

2、java代码

    //计算二叉树叶子节点
    public int leafCount(Node root){
            if(root==null){
                return 0;
            }
            if(root.left==null && root.right==null){
                return 1;
            }else {
                return leafCount(root.left)+leafCount(root.right);
            }

    }

6.3、线索二叉树

6.3.1、为什么研究二叉树

1、问题：二叉链表作为二叉树的存储结构，非常方便找到某个节点的左右节点，但是不能找到二叉树的前驱后继。

2、解决办法

（1）通过遍历寻找—浪费时间

（2）增加前驱和后继的指针—加大存储负担

6.3.2、线索二叉树概念

1、概念

2、例子

3、为了区分指针是指向孩子节点还是指向前驱后继

4、线索二叉树节点结构

（1）java代码实现

    public static class Node{
        public String value;
        public Node left;
        public Node right;
        int ltag;
        int rtag;
        public Node(String value){
            this.value=value;
        }
    }