数据结构——树

标签：遍历 no HeroNode public 二叉树 数据结构 节点

树结构的基础部分

引出————

我们都知道，数组、链表都可以存储数据，但是其存在缺点。对于数组来说，其优点是可以通过下标快速访问元素，但是若要检索某个具体值、或者插入值时，数组要整体移动，效率很低。下图给出了数组的插入过程，由于数组的空间不能动态变化，因此，需要创建新的数组，并插入和拷贝。

下面再来分析链表。链表的存储方式在数组上有所优化，在插入一个数值节点时，只需要将插入节点链接到链表中即可。但是，在进行数据检索时，效率仍较低，在检索时，需要从头开始遍历。链表中的插入操作和查找操作如下图所示。

               

鉴于上述数组、链表存在的缺点，引出了树存储方式。

树存储：树存储可以提高增删改查的效率，如 二叉排序树，既可以保证数据的检索速度，又可以保证数据的插入、删除、修改的速度。树结构如下图：

树的示意图及术语

下图给出树结构图。

树的常用术语如下：

1) 节点——一个一个小圆圈，即一个个对象，节点对象

2) 根节点——A，上面没有节点了

3) 父节点——如B是D的父节点

4) 子节点——如F是C的子节点

5) 叶子节点 (没有子节点的节点)——H E F G

6) 节点的权(节点值)

7) 路径(从 root 节点找到该节点的路线)

8) 层——处于同一层面的节点，归为一层

9) 子树

10) 树的高度(最大层数)——上图为4层

11) 森林 :多颗子树构成森林

二叉树的概念

二叉树：每个节点最多有2个子节点的树。二叉树的子节点分为左节点和右节点。常见二叉树如下图：

满二叉树：二叉树的所有叶子节点都在最后一层，节点总数=2^n - 1，n为层数。满二叉树如下图：

完全二叉树：所有叶子节点都在最后一层或者倒数第二层，且最后一层叶子节点左边连续，倒数第二层叶子节点右边连续，完全二叉树如下图：

二叉树——遍历

二叉树遍历分为前序、中序、后序遍历。

1) 前序遍历: 先输出父节点，再遍历左子树和右子树

2) 中序遍历: 先遍历左子树，再输出父节点，再遍历右子树

3) 后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点

4) 小结: 看输出父节点的顺序，就确定是前序，中序还是后序

实例：对下图进行三种顺序的遍历。

代码如下：

public class BinaryTreeDemo {
    public static void main(String[] args) {
        //创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建需要的节点
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "吴用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
        //说明：先手动创建二叉树，后续再用 递归 创建二叉树
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        binaryTree.setRoot(root);
        //测试
        System.out.println("前序遍历");
        binaryTree.preOrder();
        //测试
        System.out.println("中序遍历");
        binaryTree.infixOrder();

        //测试
        System.out.println("后序遍历");
        binaryTree.postOrder();
    }
}

//定义一个二叉树
class BinaryTree {
    private HeroNode root;//根节点
    public void setRoot(HeroNode root) {
        this.root = root;
    }
    //前序遍历
    public void preOrder() {
        if(this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
    //中序遍历
    public void infixOrder() {
        if(this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
    //后序遍历
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
}

//先创建HeroNode节点
class HeroNode {
    private int no;
    private String name;
    private HeroNode left;//左节点 默认null
    private HeroNode right;//右节点 默认null

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

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

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", 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);
    }
}

运行结果：

二叉树——添加节点

在前述二叉树上添加5号节点如下图：

只需创建5号节点，并将其挂在3号节点左边即可，代码调整实现如下：

遍历结果：

二叉树——查找节点

要求使用前序查找、中序查找、后序查找完成对前述节点5节点的查找。思路如下：

代码实现如下：

public class BinaryTreeDemo {
    public static void main(String[] args) {
        //创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建需要的节点
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "吴用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
        HeroNode node5 = new HeroNode(5, "关胜");
        //说明：先手动创建二叉树，后续再用 递归 创建二叉树
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
        binaryTree.setRoot(root);
       
        //前序查找
        //前序遍历的次数：
        System.out.println("前序查找~");
        HeroNode resNode = binaryTree.preOrderSearch(5);
        if (resNode != null) {
            System.out.printf("找到了，信息为 no = %d name = %s", resNode.getNo(), resNode.getName());
        } else {
            System.out.printf("没有找到 no = %d 的英雄", 5);
        }


        //中序查找
        //中序遍历的次数：
        System.out.println("中序查找~");
        resNode = binaryTree.infixOrderSearch(5);
        if (resNode != null) {
            System.out.printf("找到了，信息为 no = %d name = %s", resNode.getNo(), resNode.getName());
        } else {
            System.out.printf("没有找到 no = %d 的英雄", 5);
        }

        //后序查找
        //后序遍历的次数：
        System.out.println("后序查找~");
        resNode = binaryTree.postOrderSearch(5);
        if (resNode != null) {
            System.out.printf("找到了，信息为 no = %d name = %s", resNode.getNo(), resNode.getName());
        } else {
            System.out.printf("没有找到 no = %d 的英雄", 5);
        }
    }
}

//定义一个二叉树
class BinaryTree {
    private HeroNode root;//根节点

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

  
   //前序查找
    public HeroNode preOrderSearch(int no) {

        if (root != null) {
            return root.preOrderSearch(no);
        } else {
            return null;
        }
    }

    //中序查找
    public HeroNode infixOrderSearch(int no) {
        if (root != null) {
            return root.infixOrderSearch(no);
        } else {
            return null;
        }
    }

    //后序查找
    public HeroNode postOrderSearch(int no) {
        if (root != null) {
            return root.postOrderSearch(no);
        } else {
            return null;
        }
    }
}

//先创建HeroNode节点
class HeroNode {
    private int no;
    private String name;
    private HeroNode left;//左节点 默认null
    private HeroNode right;//右节点 默认null

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

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

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

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


    //前序遍历查找节点
    public HeroNode preOrderSearch(int no) {
        System.out.println("进入前序查找！");//用来累计比较次数
        //比较当前节点
        if (this.no == no) {
            return this;
        }
        //判断左节点，不为空，则递归查找
        HeroNode resNode = null;//结果节点初始化
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);//用左子节点调递归
        }
        if (resNode != null) {//说明左子节点上找到了
            return resNode;
        }
        //判断右节点 递归
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);//用右子节点调递归
        }
        return resNode;//全部遍历完了，返回
    }

    //中序遍历查找
    public HeroNode infixOrderSearch(int no) {
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }

        System.out.println("进入中序查找！");//用来累计比较次数

        if (this.no == no) {
            return this;
        }
        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }
        return resNode;
    }

    //后序遍历查找
    public HeroNode postOrderSearch(int no) {
        HeroNode resNode = null;
        //左节点递归
        if (this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //右节点递归
        if (this.right != null) {
            resNode = this.right.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }

        System.out.println("进入后序查找！");//用来累计比较次数
        //左右都没找到no，判断 当前节点
        if (this.no == no) {
            return this;
        }
        return resNode;
    }

}

通过上述代码分析，可以看到各种查找方式的比较次数。

前序查找的结果：进行了4次比较。

中序查找的结果：进行了3次比较。

后序查找的结果：进行了2次比较。

可以看到，后序查找的次数最少。

二叉树——删除节点

删除节点的规则：

1) 如果删除的节点是叶子节点，则删除该节点

2) 如果删除的节点是非叶子节点，则删除该子树.

删除节点的思路如下：首先要对二叉树进行判断，如果只有一个根节点，则直接将二叉树置空。接着，在进行删除时，要判断当前节点的子节点是否是需要删除的节点，接着，从左节点开始判断，若是则将当前节点的左节点置空，并结束递归，否则，判断右节点，若是则将当前节点的右节点置空，并结束递归，若前述左右节点都不是要删除的节点，则先向左子树进行递归删除，若仍不是，则向右子树进行递归删除。

测试删除5节点，代码如下：

​
        //测试 删除
        System.out.println("\n删除前，前序遍历");
        binaryTree.preOrder();//1 2 3 5 4
        binaryTree.delNode(5);
        System.out.println("删除后，前序遍历");
        binaryTree.preOrder();//1 2 3 4


BinaryTree类里的删除方法：
    //删除节点
    public void delNode(int no) {
        if(root != null) {
            //如果只有一个root节点，则立即判断root是不是要删除的节点
            if(root.getNo() == no) {
                root = null;
            } else {
                //递归删除
                root.delNode(no);
            }
        } else {
            System.out.println("空树无法删除");
        }
    }

HeroNode类里的删除方法：
    //递归删除节点
    //规定：如果删除的是叶子节点，就删除该节点
    //     如果删除的是非叶子节点，则 删除该子树
    public void delNode(int no) {
        //空树在BinaryTree类里处理

        //思路：单向二叉树，先判断当前节点的子节点是否是需要删除的节点；
        // 若当前节点的左子节点不为空且要删，则 this.left = null,并返回，结束递归
        // 若当前节点的右子节点不为空且要删，则 this.right = null,并返回，结束递归
        //若上述2步没有删除节点，则向左递归删除节点
        //若上述步骤没有删除节点，则向右递归删除节点
        if(this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
        if(this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        //左子树递归删除
        if(this.left != null) {
            this.left.delNode(no);
        }
        //右子树递归删除
        if(this.right != null) {
            this.right.delNode(no);
        }
    }

​

上述代码的运行结果：

若要删除3节点，则会直接将3节点的子树删除，剩下1、2节点。

顺序存储二叉树

顺序存储二叉树的概念

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，如下图。

对顺序存储二叉树的要求：要求对上图，以数组方式存放：arr{1,2,3,4,5,6,7}，在遍历数组arr时，仍可以前序、中序、后序遍历。

顺序存储二叉树的特点：

1) 顺序二叉树通常只考虑完全二叉树

2) 第 n 个元素的左子节点为 2 * n + 1

3) 第 n 个元素的右子节点为 2 * n + 2

4) 第 n 个元素的父节点为 (n-1) / 2

5) n : 表示二叉树中的第几个元素(按 0

根据2）、3）、4）的规律，就可以分别采用前序、中序、后序遍历完成对顺序存储二叉树的遍历。

顺序存储二叉树的遍历

下面代码给出对数组{1,2,3,4,5,6,7}进行前序遍历的代码；

public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
        arrBinaryTree.preOrder();//从根节点开始 1 2 4 5 3 6 7
    }
}

//编写 ArrBinaryTree类，实现顺序存储二叉树的遍历
class ArrBinaryTree {
    private int[] arr;//存储数据（二叉树节点）

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

    //方法，完成顺序存储二叉树的 前序遍历
    /**
     *
     * @param index  表示数组下标 n
     */
    public void preOrder(int index) {
        //如果数组为空，或者arr.length=0 就不遍历了
        if(arr == null || arr.length == 0) {
            System.out.println("数组为空，不能按照二叉树前序遍历");
        }
        //输出当前这个元素
        System.out.println(arr[index]);
        //向左递归遍历
        if(index * 2 + 1 < arr.length) {
            preOrder(index * 2 + 1);//向左递归
        }
        if(index * 2 + 2 < arr.length) {
            preOrder(index * 2 + 2);
        }
    }
    //重载preOrder方法
    public void preOrder() {
        this.preOrder(0);//表示从数组第一个元素 即树的根节点 开始遍历
    }
}

前序遍历结果为：1 2 4 5 3 6 7

顺序存储二叉树的应用

顺序存储二叉树一个很重要的应用：堆排序！在文章 排序算法——堆排序数据结构与算法——堆排序-CSDN博客中进行详讲。

线索化二叉树

线索二叉树基本介绍

对数列{1,3,6,8,10,14}构建一颗二叉树如下，可以看到，中序遍历二叉树结果为{8,3,10,1,14,6}，但是节点6，8，10，14的左指针、右指针没有完全利用上，若希望充分利用，则需要使用线索化二叉树。

线索化二叉树的特点如下：

1) n 个结点的二叉链表中含有 n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）

2) 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树。

3) 一个结点的前一个结点，称为前驱结点

4) 一个结点的后一个结点，称为后继结点。

线索二叉树的实现

对前述二叉树进行中序线索化。根据中序遍历结果：{8,3,10,1,14,6}，可以得到每个节点的前驱节点和后继节点，因此给出分析图如下：

进行线索化二叉树后，节点Node的左指针left和右指针right，分别都有两种情况：

1) left 指向的是左子树，也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的 就是前驱节点.

2) right 指向的是右子树，也可能是指向后继节点，比如 ① 节点 right 指向的是右子树，而⑩ 节点的 right 指向 的是后继节点.

在进行线索化时，需要添加一个属性pre，pre节点总是保留前一个节点，这是实现线索化的基础。在线索化时，先线索化左子树，在线索化当前节点，最后线索化右子树；并且要创建变量leftType和rightType，用来记录左右指针的类型（0表示子树，1表示前驱、后继节点）。中序线索化代码如下：

public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        //测试线索化
        HeroNode root = new HeroNode(1, "tom");
        HeroNode node2 = new HeroNode(3, "jack");
        HeroNode node3 = new HeroNode(6, "smith");
        HeroNode node4 = new HeroNode(8, "marry");
        HeroNode node5 = new HeroNode(10, "king");
        HeroNode node6 = new HeroNode(14, "dim");

        //二叉树 后续递归创建
        //现在先手动创建
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        //测试线索化
        ThreadBinaryTree threadBinaryTree = new ThreadBinaryTree();
        threadBinaryTree.setRoot(root);
        threadBinaryTree.threadNodes();
        //用10节点测试
        HeroNode leftNode = node5.getLeft();
        System.out.println("10号节点的前驱节点"+ leftNode);
        HeroNode rightNode = node5.getRight();
        System.out.println("10号节点的后继节点"+ rightNode);
    }
}

//定义一个线索化二叉树
class ThreadBinaryTree {
    private HeroNode root;//根节点

    //为了实现线索化，需要创建 指向当前节点的前驱节点的指针
    //在递归进行线索化时，pre总是保留前一个节点
    private HeroNode pre = null;


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

   

    //编写对二叉树进行中序线索化的方法

    /**
     * @param node 就是当前需要线索化的节点
     */
    public void threadNodes(HeroNode node) {
        //判断 如果node==null 不能线索化
        if (node == null) {
            return;
        }
        //中序线索化
        //(一)先线索化左子树
        threadNodes(node.getLeft());
        //(二)线索化当前节点
        //处理当前节点的前驱节点
        //以8节点理解，
        //8节点的.left=null,8节点的.leftType=1
        if (node.getLeft() == null) {
            //让当前节点的左指针指向前驱节点
            node.setLeft(pre);
            //修改当前节点的左指针的类型
            node.setLeftType(1);//指向前驱节点
        }

        //处理后继节点
        if (pre != null && pre.getRight() == null) {
            //让当前节点的右指针指向前驱节点
            pre.setRight(node);
            //修改当前节点的右指针的类型
            pre.setRightType(1);
        }
        //!!!!!!每处理一个节点后，让当前节点是下一个节点的前驱节点
        pre = node;
        //(三)线索化右子树
        threadNodes(node.getRight());
    }
    //重载线索化方法
    public void threadNodes() {
        this.threadNodes(root);
    }
}


//创建HeroNode
//先创建HeroNode节点
class HeroNode {
    private int no;
    private String name;
    private HeroNode left;//左节点 默认null
    private HeroNode right;//右节点 默认null

    //说明：若 leftType==0 表示指向左子树，若leftType==1 表示指向前驱节点
    //     若 rightType==0 表示指向右子树，若rightType==1 表示指向后继节点
    private int leftType;
    private int rightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

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

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

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

}

结果：

遍历线索二叉树

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

代码如下：

main:     
   //使用线索化方式 遍历 线索化二叉树
        threadBinaryTree.threadedList();//8，3，10，1，6，14

ThreadedBinaryTree类
    //遍历中序线索化的二叉树
    public void threadedList() {
        //临时变量，存储当前遍历的节点.从root开始
        HeroNode node = root;
        while (node != null) {
            //循环的找到leftType==1的节点，第一个找到8节点
            //随着循环遍历，会变化
            while (node.getLeftType() == 0) {
                node = node.getLeft();
            }
            //打印当前节点
            System.out.println(node);
            //如果当前节点的右指针指向后继节点，就一直输出
            while (node.getRightType() == 1) {
                //获取到当前节点的后继节点
                node = node.getRight();
                System.out.println(node);
            }
            //替换遍历的节点
            node = node.getRight();
        }
    }

结果：

可以看到遍历结果与中序遍历结果相吻合。

总结

上述就是树结构的基本内容，包括了树的基本概念、术语，以及二叉树的相关操作：遍历、添加节点、查找节点、删除节点，以及顺序存储二叉树、线索化二叉树的基本知识。

标签：遍历,no,HeroNode,public,二叉树,数据结构,节点
From： https://blog.csdn.net/weixin_43713707/article/details/137436095