PHP

二叉树的概念

勇康博客网
预计阅读时长 10 分钟
位置: 首页 PHP 正文

本文撇开一些非常苦涩、难以理解的概念来讲讲二叉树,仅入门观看(或复习)....

首先,我们来讲讲什么是树:

  • 树是一种非线性数据结构,相对于线性的数据结构(链表、数组)而言,树的平均运行时间更短(往往与树相关的排序时间复杂度都不会高)


但是在编程的世界中,我们一般把树“倒”过来看,这样容易我们分析:

image.png

一般的树是有很多很多个分支的,分支下又有很多很多个分支,如果在程序中研究这个会非常麻烦。因为本来树就是非线性的,而我们计算机的内存是线性存储的,太过复杂的话我们无法设计出来的。

因此,我们先来研究简单又经常用的---> 二叉树


1 树的一些概念

我就拿上面的图来进行画来讲解了:

image.png

二叉树的意思就是说:每个节点不能多于有两个儿子,上面的图就是一颗二叉树。

  • 一棵树至少会有一个节点(根节点)

  • 树由节点组成,而节点的定义就是:一个数据、两个指针(如果有节点就指向节点、没有节点就指向null)

2 静态创建二叉树

上面说了,树是由若干个节点组成,节点连接起来就成了树,而节点由一个数据、两个指针组成

因此,创建树实际上就是创建节点,然后连接节点

首先,使用java类定义节点:

public class TreeNode {

    // 左节点(儿子)
    private TreeNode lefTreeNode;
    
    // 右节点(儿子)
    private TreeNode rightNode;
    
    // 数据
    private int value;
    

}

下面我们就拿这个二叉树为例来构建吧:

image.png

为了方便构建,我就给了它一个带参数的构造方法和set、get方法了:

    public TreeNode(int value) {

        this.value = value;
    }

那么我们现在就创建了5个节点:

    public static void main(String[] args) {

        //根节点-->10
        TreeNode treeNode1 = new TreeNode(10);

        //左孩子-->9
        TreeNode treeNode2 = new TreeNode(9);

        //右孩子-->20
        TreeNode treeNode3 = new TreeNode(20);
        
        //20的左孩子-->15
        TreeNode treeNode4 = new TreeNode(15);
        
        //20的右孩子-->35
        TreeNode treeNode5 = new TreeNode(35)        
      
    }

它们目前的状态是这样子的:

image.png

于是下面我们去把它连起来:

    //根节点的左右孩子
    treeNode1.setLefTreeNode(treeNode2);
    treeNode1.setRightNode(treeNode3);

    //20节点的左右孩子
    treeNode3.setLefTreeNode(treeNode4);
    treeNode3.setRightNode(treeNode5);

连接完之后,那么我们的树就创建完成了。

image.png

关于二叉树遍历请参考:PHP实现二叉树的遍历

本文来自投稿,不代表本站立场,如若转载,请注明出处:
-- 展开阅读全文 --
头像
PHP生命周期所经历的5个阶段
« 上一篇 2022-02-08
PHP实现二叉树的遍历
下一篇 » 2022-02-08
取消
微信二维码
微信二维码
支付宝二维码

发表评论

暂无评论,2105人围观

作者信息

勇康博客网
承接企业、个人,仿站、定制。域名,主机一键代发
TA的最新作品

热门文章

2
3

动态快讯

标签列表

目录[+]