树和二叉树

本文最后更新于：2022年12月13日 晚上

树和二叉树

为什么需要树这种数据结构

  1. 数组存储方式的分析
    优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。
    缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低。

    数组存储方式的分析

  2. 链式存储方式的分析
    优点：在一定程度上对数组存储方式有优化（比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好）。
    缺点：在进行检索时，效率仍然较低，比如（检索某个值，需要从头节点开始遍历）。
    链表操作示意图

  3. 树存储方式的分析
    二叉排序能提高数据存储，读取的效率，比如利用二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。
    树存储方式的分析

树

树的概念

树(Tree)是n(n≧0)个结点的有限集。n=0时称为空树。在任意一颗非空树中：有且仅有一个特定的称为根的结点。当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、T3……、Tm，其中每个集合本身又是一棵树，并且称为根的子树。

树的术语

树的术语

（一）节点的度：一个节点含有的子树的个数称为该节点的度
（二）树的度：一棵树中，最大的节点的度称为树的度
（三）叶节点或终端节点：度为0的节点
（四）父亲节点或父节点：若一个节点含有子节点，则这个节点 称为其子节点的父节点
（五）孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点
（六）兄弟节点：具有相同父节点的节点互称为兄弟节点
（七）节点的层次：从根开始定义起，根为第一层， 根的子节点为第二层，以此类推
（八）树的高度或深度：树中节点的最大层次
（九）堂兄弟节点：父节点在同一层的节点互为堂兄弟节点
（十）节点的祖先：从根到该节点所经分支上的所有节点
（十一）子孙：以某节点为根的子树中任一节点都称为该节点的子孙
（十二）森林：由m(m>=0)棵互不相交的树的集合称为森林

二叉树

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（空二叉树）、或者由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

特点：

  • 二叉树中每个结点最多有两颗子树，度没有超过2的。
  • 左子树和右子树是有顺序的，不能颠倒。

二叉树的形态

（1）空二叉树树

（2）只有一个根结点

（3）根结点只有左子树

（4）根结点只有右子树

（5）根结点既有右子树又有右子树

特殊二叉树

  1. 斜树

    • 左斜树：所有结点都只有左子树的二叉树
    • 右斜树：所有结点都只有右子树的二叉树
      斜树

  2. 满二叉树

    在二叉树中，所有的分支结点都有左子树和右子树，并且所有的叶子都在同一层。该二叉树的所有叶子节点都在最后一层，并且结点总数为 $2^n - 1$ ，n为层数。
    满二叉树

  3. 完全二叉树

    • 叶子节点只能出现在最下两层。
    • 最下层的叶子一定集中在左部连续位置。
    • 倒数第二层，若有叶子结点，一定在右部连续位置。
    • 如果结点度为1，则该结点只有左孩子。
    • 同样结点的二叉树，完全二叉树的深度最小。
      完全二叉树

二叉树的遍历

前序遍历：先输出父节点，再遍历左子树和右子树
中序遍历：先遍历左子树，再输出父节点，再遍历右子树
后序遍历：先遍历左子树，再遍历右子树，最后输出父节点
小结：看输出父节点的顺序，就确定是前序，中序还是后序

二叉树遍历的实现思路

前序遍历

  • 先输出当前节点(初始的时候是root节点)
  • 如果左子节点不为空，则递归继续前序遍历
  • 如果右子节点不为空，则递归继续前序遍历

中序遍历

  • 如果当前节点的左子节点不为空，则递归中序遍历
  • 输出当前节点
  • 如果当前节点的右子节点不为空，则递归中序遍历

后序遍历

  • 如果当前节点的左子节点不为空，则递归后序遍历
  • 如果当能节点的右子节点不为空，则递归中序遍历
  • 输出当前节点

二叉树遍历的代码实现

首先定义树的结点类

class TreeNode {
    private int id;
    private String name;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

递归实现前、中、后序遍历，作为结点的方法

public void preOrder() {
    System.out.println(this);
    if (this.left != null) {
        this.left.preOrder();
    }
    if (this.right != null) {
        this.right.preOrder();
    }
}
public void infixOrder() {
    if (this.left != null) {
        this.left.infixOrder();
    }
    System.out.println(this);
    if (this.right != null) {
        this.right.infixOrder();
    }
}
public void postOrder() {
    if (this.left != null) {
        this.left.postOrder();
    }
    if (this.right != null) {
        this.right.postOrder();
    }
    System.out.println(this);
}

定义二叉树类

public class BinaryTree {
    // 定义根结点
    private TreeNode root;

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    public void preOrder() {
        this.root.preOrder();
    }

    public void infixOrder() {
        this.root.infixOrder();
    }

    public void postOrder() {
        this.root.postOrder();
    }
}

测试方法

public void preOrder() {
    System.out.println(this);
    if (this.left != null) {
        this.left.preOrder();
    }
    if (this.right != null) {
        this.right.preOrder();
    }
}
public void infixOrder() {
    if (this.left != null) {
        this.left.infixOrder();
    }
    System.out.println(this);
    if (this.right != null) {
        this.right.infixOrder();
    }
}
public void postOrder() {
    if (this.left != null) {
        this.left.postOrder();
    }
    if (this.right != null) {
        this.right.postOrder();
    }
    System.out.println(this);
}

预期结果

前序遍历
TreeNode{id=1, name='Yorick'}
TreeNode{id=2, name='Merry'}
TreeNode{id=4, name='Tom'}
TreeNode{id=3, name='Jack'}
TreeNode{id=5, name='Lily'}
中序遍历
TreeNode{id=4, name='Tom'}
TreeNode{id=2, name='Merry'}
TreeNode{id=1, name='Yorick'}
TreeNode{id=3, name='Jack'}
TreeNode{id=5, name='Lily'}
后序遍历
TreeNode{id=4, name='Tom'}
TreeNode{id=2, name='Merry'}
TreeNode{id=5, name='Lily'}
TreeNode{id=3, name='Jack'}
TreeNode{id=1, name='Yorick'}

二叉树的查找

前序中序后序查找思路

前序查找

  • 先判断当前结点的值是否等于要查找的
  • 如果是相等，则返回当前结点
  • 如果不等，则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
  • 如果左递归前序查找，找到结点，则返回，否继续判断当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找，

中序查找

  • 判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
  • 如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点，否则继续进行右递归的中序查找
  • 如果右递归中序查找，找到就返回，否则返回null

后序查找

  • 判断当前结点的左子节点是否为空，如果不为空，则递归后序查找
  • 如果找到，就返回，如果没有找到，就判断当前结点的右子节点是否为空，如果不为空，则右递归进行后序查找，如果找到，就返回
  • 如果不等就和当前结点进行比较，如果是则返回，否则返回null

前序中序后序查找代码实现

public TreeNode preOrderSearch(int id) {
    if (this.id == id) {
        return this;
    }
    TreeNode res = null;
    // 向左查找
    if (this.left != null) {
        res = this.left.preOrderSearch(id);
    }
    if (res != null) {
        return res;
    }
    // 向右查找
    if (this.right != null) {
        res = this.right.preOrderSearch(id);
    }
    return res;
}

public TreeNode infixOrderSearch(int id) {
    TreeNode res = null;
    if (this.left != null) {
        res = this.left.infixOrderSearch(id);
    }
    if (res != null) {
        return res;
    }
    if (this.id == id) {
        return this;
    }
    if (this.right != null) {
        res = this.right.infixOrderSearch(id);
    }
    return res;
}

public TreeNode postOrderSearch(int id) {
    TreeNode res = null;
    if (this.left != null) {
        res = this.left.postOrderSearch(id);
    }
    if (res != null) {
        return res;
    }
    if (this.right != null) {
        res = this.right.postOrderSearch(id);
    }
    if (res != null) {
        return res;
    }
    if (this.id == id) {
        res = this;
    }
    return res;
}

二叉树删除结点

要求

  • 如果删除的节点是叶子节点，则删除该节点
  • 如果删除的节点是非叶子节点，则删除该子树

二叉树删除结点思路

  1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点。
  2. 如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将this.left = null;并且返回(结束递归删除)
  3. 如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this.right=null;并且返回(结束递归删除)
  4. 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
  5. 如果第4步也没有删除结点，则应当向右子树进行递归删除。
  6. 如果树是空树，即只有一个root结点，则等价将二叉树置空

二叉树删除结点代码实现

结点类方法

public void delNode(int id) {
    if (this.left != null && this.left.id == id) {
        this.left = null;
        return;
    }
    if (this.right != null && this.right.id == id) {
        this.right = null;
        return;
    }
    if (this.left != null) {
        this.left.delNode(id);
    }
    if (this.right != null) {
        this.right.delNode(id);
    }
}

二叉树类方法

public void delNode(int id) {
    if (root==null){
        System.out.println("树为空");
        return;
    }
    // 根节点且符合删除的情况
    if (root.getId() == id) {
        root = null;
        return;
    }
    root.delNode(id);
}

顺序存储二叉树

顺序存储二叉树的特点：

  • 顺序二叉树通常只考虑完全二叉树
  • 第 n 个元素的左子节点为2*n+1
  • 第 n 个元素的右子节点为2*n+2
  • 第 n 个元素的父节点为(n-1)/2

n 表示二叉树中的第几个元素(按 0 开始编号)

顺序存储二叉树代码实现

public class ArrBinaryTree {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7,};
        ArrBinaryTree binaryTree = new ArrBinaryTree(arr);
        System.out.print("前序遍历 ");
        binaryTree.preOrder(0);
        System.out.println();
        System.out.print("中序遍历 ");
        binaryTree.infixOrder(0);
        System.out.println();
        System.out.print("后序遍历 ");
        binaryTree.postOrder(0);
        System.out.println();
    }

    private final int[] arr; // 存储结点的数组

    public ArrBinaryTree(int[] arr) {
        this.arr = arr;
    }

    // 顺序存储二叉树的前序遍历
    public void preOrder(int n) {
        if (isEmpty())
            return;
        System.out.print(arr[n] + " ");
        if ((n * 2 + 1) < arr.length) {
            preOrder(n * 2 + 1);
        }
        if ((n * 2 + 2) < arr.length) {
            preOrder(n * 2 + 2);
        }
    }
    // 顺序存储二叉树的中序遍历
    public void infixOrder(int n) {
        if (isEmpty())
            return;
        if ((n * 2 + 1) < arr.length) {
            infixOrder(n * 2 + 1);
        }
        System.out.print(arr[n] + " ");
        if ((n * 2 + 2) < arr.length) {
            infixOrder(n * 2 + 2);
        }
    }
    // 顺序存储二叉树的后序遍历
    public void postOrder(int n) {
        if (isEmpty())
            return;
        if ((n * 2 + 1) < arr.length) {
            postOrder(n * 2 + 1);
        }
        if ((n * 2 + 2) < arr.length) {
            postOrder(n * 2 + 2);
        }
        System.out.print(arr[n] + " ");
    }

    public boolean isEmpty() {
        if (arr == null || arr.length == 0) {
            System.out.println("树为空");
            return true;
        }
        return false;
    }
}

顺序存储二叉树应用场景

堆排序

线索化二叉树

线索化二叉树基本概念

  1. n 个结点的二叉链表中含有n+1公式2n-(n-1)=n+1个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为”线索”）。
  2. 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树
    (Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
  3. 一个结点的前一个结点，称为前驱结点
  4. 一个结点的后一个结点，称为后继结点

当线索化二叉树后，Node节点的属性left和right，有如下情况：

  • left指向的是左子树，也可能是指向的前驱节点。
  • right指向的是右子树，也可能是指向的后驱节点。

线索化二叉树代码实现

package com.yur.tree;

public class ThreadedBinaryTree extends BinaryTree {
    public static void main(String[] args) {
        ThreadedBinaryTree tree = new ThreadedBinaryTree();
        ThreadedTreeNode root = new ThreadedTreeNode(1, "Yorick");
        tree.setRoot(root);
        ThreadedTreeNode node2 = new ThreadedTreeNode(2, "Merry");
        ThreadedTreeNode node3 = new ThreadedTreeNode(3, "Jack");
        ThreadedTreeNode node4 = new ThreadedTreeNode(4, "Tom");
        ThreadedTreeNode node5 = new ThreadedTreeNode(5, "Lily");
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node3.right = node5;
        tree.threadedNodes(root);
        System.out.println(node4.right);
        System.out.println(node2.right);
        System.out.println(node5.left);
        System.out.println(node3.left);
        System.out.println("线索化中序遍历");
        // 线索化遍历（中序）
        tree.threadedList();
    }

    private ThreadedTreeNode pre;

    // 中序线索化
    public void threadedNodes(ThreadedTreeNode node) {
        if (node == null) {
            return;
        }
        // 处理左子树
        threadedNodes((ThreadedTreeNode) node.left);
        // 处理node
        if (node.left == null) {
            node.left = pre;
            node.leftType = 1;
        }
        if (pre != null && pre.right == null) {
            pre.right = node;
            pre.rightType = 1;
        }
        pre = node;
        // 处理右子树
        threadedNodes((ThreadedTreeNode) node.right);
    }

}

class ThreadedTreeNode extends TreeNode {

    // 规定结点的指针类型，默认为 0 代表指向子树，为 1 代表指向前驱或后驱结点
    public int leftType = 0;
    public int rightType = 0;

    public ThreadedTreeNode(int id, String name) {
        super(id, name);
    }
}

遍历线索化二叉树

说明：对前面的中序线索化的二叉树，进行遍历
分析：因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。遍历的次序应当和中序遍历保持一致。

// 线索化遍历（中序）
public void threadedList() {
    ThreadedTreeNode node = (ThreadedTreeNode) getRoot();
    while (node != null) {
        // 向左找的第一个被线索化处理过的结点
        while (node.leftType == 0) {
            node = (ThreadedTreeNode) node.left;
        }
        System.out.println(node);
        //如果当前结点的右指针指向的是后继结点,就一直输出
        while (node.rightType == 1) {
            node = (ThreadedTreeNode) node.right;
            System.out.println(node);
        }
        node = (ThreadedTreeNode) node.right;
    }
}
DataStructure
#Java #树 #Tree
树和二叉树
http://yorick.love/2022/07/21/数据结构/数据结构_树和二叉树/
作者
Yorick
发布于
2022年7月21日
许可协议