数据结构07 二叉树

这篇文章开始总结 树和二叉树。

什么是树呢?

1、树的定义

(1)有且仅有一个特定的称为根(root) 的节点。

(2)当 n>1 时,其余节点可分为 m(m>0) 个互不相交的集合。其中每个集合本身又是一个棵树,并称为根的子树。

2、树的表示方法

最常见的是 树形表示法 和 广义表表示法,下面是树形表示法,如图所示。

上图的 广义表表示法为:(A(B(D,E),C(F,G)))   

3、常见的术语

  (1)父节点,孩子节点,兄弟节点。以上图为例,A是B和C的父节点,B和C是A的孩子节点,B和C之间互为兄弟节点。

  (2)节点的度和树的度。节点的度即节点有几个分支,比如节点A有两个分支B和C,那么节点A的度就是2,树的度即为一棵树中节点的最大度数,所以上图的树的度也是2。

  (3)有序树和无序树。如果将树中节点的子树看成是从左至右依次有序且不能交换,则称该树为有序树,否则称为无序树。

  (4)森林。在上图中,如果将根节点A拿掉,那么B子树和C子树合并就是森林了。

  (5)二叉树。二叉树是一种特殊的树。它的每个节点最多只有两棵子树。

4、二叉树的常见性质

  性质1:在二叉树的第 i 层上最多有 2i-1 个节点 (i>=1)

  性质2:深度为 k 的二叉树最多有 2k-1 个节点 (k>=1)

  性质3:满二叉树:一棵深度为 k 且有 2k-1 个节点的二叉树称为 满二叉树。

       完全二叉树:一棵深度为 k 的二叉树,其前 k-1 层是一棵满二叉树,而最下面一层(即第k层) 上的节点都集中在该层最左边的若干位置上。这样的二叉树称为 完全二叉树。

满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树。

下面是 满二叉树 和 完全二叉树 的图示:

5、二叉树的两种存储结构

5-1:顺序存储 

对于完全二叉树而言,可以使用顺序存储结构。但对于一般的二叉树而言,使用顺序存储结构会有两个缺点:一、如果不是完全二叉树,则必须将其转化为完全二叉树;二、增加了很多虚节点,浪费资源空间。

5-2:链式存储

链式存储是最常用的一种二叉树存储结构。每个节点设置三个域,分别是值域、左指针域和右指针域,用 data 表示值域,lchild 和 rchild 分别表示指向左子树、右子树的指针域。如下图: 

6、二叉树的常见操作

6-1:插入节点

思路:首先找到要插入节点的父节点,然后确定插入到父节点的左边还是右边,最后将节点插入。

6-2:查找节点

思路:运用递归查找。

6-3:计算树的深度

思路:分别递归左子树和右子树,取长度较大的那一个作为整个树的深度。

6-4:遍历之 先序遍历

思路:先访问根节点,然后遍历左子树,再遍历右子树

6-5:遍历之 中序遍历

思路:先遍历左子树,再访问根节点,最后遍历右子树

6-6:遍历之 后序遍历

思路:先遍历左子树,再遍历右子树,最后访问根节点

6-7:遍历之 按层遍历

思路:从上到下,从左到右遍历节点

7、二叉树的常见操作的代码实现

代码如下:

节点类Node.java 

public class Node {
    public int data; // 数据域
    public Node left; // 左孩子
    public Node right; // 右孩子
}

BinTree.java

import java.util.Scanner;

public class BinTree {
    // 按层遍历的存储空间长度
    public static int length;

    /**
     * 生成根节点
     */
    public static Node createRoot() {
        Node root = new Node();
        System.out.println("请输入根节点,以便生成树:");
        root.data = new Scanner(System.in).nextInt();
        System.out.println("根节点生成成功");
        return root;
    }

    /**
     * 插入节点
     *
     * @param root 二叉树的根节点
     * @return 返回二叉树的根节点
     * @throws Exception
     */
    public static Node insert(Node root) throws Exception {
        while (true) {
            System.out.println("请输入待插入节点的数据:");
            Node node = new Node();
            node.data = new Scanner(System.in).nextInt();

            // 获取父节点数据
            System.out.println("请输入它(待插入节点) 的父节点:");
            int parentNodeData = new Scanner(System.in).nextInt();

            // 确定插入方向
            System.out.println("请确定要插入到父节点的:1 左侧, 2 右侧");
            int direction = new Scanner(System.in).nextInt();

            // 插入节点
            root = insertNode(root, node, parentNodeData, direction);

            if (root == null) {
                System.out.println("未找到父节点,请重新输入!");
                continue;
            }
            System.out.println("插入成功,是否继续? 1继续,2退出");

            if (new Scanner(System.in).nextInt() == 1)
                continue;
            else
                break; // 退出循环
        }
        return root;
    }

    /**
     * 从insert()方法抽取出来的需要递归的部分
     *
     * @param root           二叉树的根节点
     * @param node           待插入节点
     * @param parentNodeData 待插入节点的父节点
     * @param direction      插入到左边还是右边
     * @return 返回二叉树的根节点
     * @throws Exception
     */
    public static Node insertNode(Node root, Node node, int parentNodeData, int direction) throws Exception {
        if (root == null)
            return null;

        // 找到父节点
        if (root.data == parentNodeData) {
            switch (direction) {
                case 1:
                    if (root.left != null)
                        throw new Exception("左节点已存在,不能插入!");
                    else
                        root.left = node;
                    break;
                case 2:
                    if (root.right != null)
                        throw new Exception("右节点已存在,不能插入!");
                    else
                        root.right = node;
                    break;
            }
        }

        // 向左子树查找父节点(递归)
        insertNode(root.left, node, parentNodeData, direction);
        // 向右子树查找父节点(递归)
        insertNode(root.right, node, parentNodeData, direction);

        return root;
    }

    /**
     * 查找节点
     */
    public static boolean getNode(Node root, int data) {
        if (root == null)
            return false;

        // 查找成功
        if (root.data == data)
            return true;

        // 递归查找
        boolean result1 = getNode(root.left, data);
        boolean result2 = getNode(root.right, data);
        return result1 || result2;
    }

    /**
     * 获取二叉树的深度
     * 思路:分别递归左子树和右子树,取长度较大的那一个作为整个树的深度
     *
     * @param root 二叉树的根节点
     * @return
     */
    public static int getLength(Node root) {
        if (root == null)
            return 0;
        int leftLength, rightLength;

        // 递归左子树的深度
        leftLength = getLength(root.left);
        // 递归右子树的深度
        rightLength = getLength(root.right);

        if (leftLength > rightLength)
            return leftLength + 1;
        else
            return rightLength + 1;
    }

    /**
     * 先序遍历
     * 思路:先访问根节点,然后遍历左子树,再遍历右子树
     *
     * @param root 根节点
     */
    public static void DLR(Node root) {
        if (root == null)
            return;

        // 输出节点的值
        System.out.print(root.data + " ");

        // 递归遍历左子树
        DLR(root.left);

        // 递归遍历右子树
        DLR(root.right);
    }

    /**
     * 中序遍历
     * 思路:先遍历左子树,再访问根节点,最后遍历右子树
     *
     * @param root 根节点
     */
    public static void LDR(Node root) {
        if (root == null)
            return;

        // 遍历左子树
        LDR(root.left);

        // 输出节点的值
        System.out.print(root.data + " ");

        // 遍历右子树
        LDR(root.right);
    }

    /**
     * 后序遍历
     * 思路:先遍历左子树,再遍历右子树,最后访问根节点
     *
     * @param root 根节点
     */
    public static void LRD(Node root) {
        if (root == null)
            return;

        // 遍历左子树
        LRD(root.left);

        // 遍历右子树
        LRD(root.right);

        // 输出节点的值
        System.out.print(root.data + " ");
    }

    /**
     * 按层遍历
     * 思路:从上到下,从左到右遍历节点
     *
     * @param root 根节点
     */
    public static void traversalLevel(Node root) {
        if (root == null)
            return;

        int head = 0;
        int tail = 0;

        // 申请保存空间
        Node[] nodeList = new Node[length];

        // 将当前二叉树保存到数组中
        nodeList[tail] = root;

        // 计算tail的位置
        tail = (tail + 1) % length; // 除留余数法

        while (head != tail) {
            Node tempNode = nodeList[head];

            // 计算head的位置
            head = (head + 1) % length;

            // 输出节点的值
            System.out.print(tempNode.data + " ");

            // 如果左子树不为空,则将左子树保存到数组的tail位置
            if (tempNode.left != null) {
                nodeList[tail] = tempNode.left;
                // 重新计算tail的位置
                tail = (tail + 1) % length;
            }

            // 如果右子树不为空,则将右子树保存到数组的tail位置
            if (tempNode.right != null) {
                nodeList[tail] = tempNode.right;
                // 重新计算tail的位置
                tail = (tail + 1) % length;
            }
        }
    }
}

BinTreeTest.java

public class BinTreeTest {
    public static void main(String[] args) throws Exception {
        System.out.println("*******链式存储的二叉树*******");
        // 创建根节点
        Node root = BinTree.createRoot();

        // 1、插入节点
        System.out.println("********插入节点*******");
        BinTree.insert(root);

        // 2、查找节点
        System.out.print("查找data为2的节点是否存在:");
        boolean result = BinTree.getNode(root, 2);
        System.out.println(result);

        // 3、获取二叉树的深度
        System.out.println("当前二叉树的深度为:" + BinTree.getLength(root));

        // 4、先序遍历
        System.out.print("先序遍历:");
        BinTree.DLR(root);
        System.out.println("");

        // 5、中序遍历
        System.out.print("中序遍历:");
        BinTree.LDR(root);
        System.out.println("");

        // 6、后序遍历
        System.out.print("后序遍历:");
        BinTree.LRD(root);
        System.out.println("");

        // 7、按层遍历
        System.out.print("按层遍历:");
        BinTree.length = 100;
        BinTree.traversalLevel(root);
        System.out.println("");
    }
}

运行结果:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏俞其荣的博客

HashSet内部原理解析Header源码解析Footer

2825
来自专栏拭心的安卓进阶之路

Java 集合深入理解(7):ArrayList

今天心情有点美丽,学学 ArrayList 放松下吧! 什么是 ArrayList ? ? ArrayList 是 Java 集合框架中 List接口 的一个实...

2277
来自专栏java系列博客

Iterator在ArrayList中的源码实现

1712
来自专栏前端说吧

JS - 二叉树算法实现与遍历 (更新中...)

3748
来自专栏wannshan(javaer,RPC)

关于 java.util.ConcurrentModificationException jdk源码分析

先看怎么发生 List<Integer> list=new ArrayList<>(); for(int i=0;i<10;i++){ list.add...

2973
来自专栏LeetCode

LeetCode 102 & 103 &107 & 637. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie,...

990
来自专栏好好学java的技术栈

“365算法每日学计划”:06打卡-单向循环链表

单向循环链表是单链表的另一种形式,其结构特点是链表中最后一个结点的指针不再是结束标记,而是指向整个链表的第一个结点,从而使单链表形成一个环。

631
来自专栏java技术学习之道

Java进阶--深入理解ArrayList实现原理

1193
来自专栏ACM算法日常

二叉搜索树(BST)- HDU 3791

二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sor...

1201
来自专栏武培轩的专栏

ArrayList源码解析(JDK1.8)

1 package java.util; 2 3 import sun.misc.SharedSecrets; 4 5 imp...

2985

扫码关注云+社区

领取腾讯云代金券