目录

前面我们讲的都是线性表结构,栈、队列等等。今天我们讲一种非线性表结构,树。树这种数据结构比线性表的数据结构要复杂得多,内容也比较多,首先我们先从树(Tree)开始讲起。
@

树(Tree)

树型结构是一种非线性结构,它的数据元素之间呈现分支、分层的特点。

1.树的定义

树(Tree)是由n(n≥0)个结点构成的有限集合T,当n=0时T称为空树;否则,在任一非空树T中:
(1)有且仅有一个特定的结点,它没有前驱结点,称其为根(Root)结点;
(2)剩下的结点可分为m(m≥0)个互不相交的子集T1,T2,…,Tm,其中每个子集本身又是一棵树,并称其为根的子树(Subtree)。

注意:树的定义具有递归性,即“树中还有树”。树的递归定义揭示出了树的固有特性

2.什么是树结构

什么是“树”?再好的定义,都没有图解来的直观。所以我在图中画了几棵“树”。你来看看,这些“树”都有什么特征?
在这里插入图片描述
你有没有发现,“树”这种数据结构真的很像我们现实生活中的“树”

3.为什么使用树结构

在有序数组中,可以快速找到特定的值,但是想在有序数组中插入一个新的数据项,就必须首先找出新数据项插入的位置,然后将比新数据项大的数据项向后移动一位,来给新的数据项腾出空间,删除同理,这样移动很费时。显而易见,如果要做很多的插入和删除操作和删除操作,就不该选用有序数组。另一方面,链表中可以快速添加和删除某个数据项,但是在链表中查找数据项可不容易,必须从头开始访问链表的每一个数据项,直到找到该数据项为止,这个过程很慢。 树这种数据结构,既能像链表那样快速的插入和删除,又能想有序数组那样快速查找

4.树的常用术语

结点——包含一个数据元素和若干指向其子树的分支
度——结点拥有的子树个数
树的度——该树中结点的最大度数
叶子——度为零的结点
分支结点(非终端结点)——度不为零的结点
孩子和双亲——结点的子树的根称为该结点的孩子,相应地,该结点称为孩子的双亲
兄弟——同一个双亲的孩子
祖先和子孙——从根到该结点所经分支上的所有结点。相应地,以某一结点为根的子树中的任一结点称为该结点的子孙。
结点的层次——结点的层次从根开始定义,根结点的层次为1,其孩子结点的层次为2,……
堂兄弟——双亲在同一层的结点
树的深度——树中结点的最大层次
有序树和无序树——如果将树中每个结点的各子树看成是从左到右有次序的(即位置不能互换),则称该树为有序树;否则称为无序树。
森林——m(m≥0)棵互不相交的树的有限集合

在这里插入图片描述
到这里,树就讲的差不多了,接下来讲讲二叉树(Binary Tree)

二叉树(Binary Tree)

树结构多种多样,不过我们最常用还是二叉树,我们平时最常用的树就是二叉树。二叉树的每个节点最多有两个子节点,分别是左子节点和右子节点。二叉树中,有两种比较特殊的树,分别是满二叉树和完全二叉树。满二叉树又是完全二叉树的一种特殊情况。

1.二叉树的定义和特点

二叉树的定义:
二叉树(Binary Tree)是n(n≥0)个结点的有限集合BT,它或者是空集,或者由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树组成 。
————————————
二叉树的特点:
每个结点至多有二棵子树(即不存在度大于2的结点);二叉树的子树有左、右之分,且其次序不能任意颠倒。

2.几种特殊形式的二叉树

1、满二叉树
定义:深度为k且有2k-1个结点的二叉树,称为满二叉树。
特点:每一层上的结点数都是最大结点数
2、完全二叉树
定义:
深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为完全二叉树
特点:
特点一 : 叶子结点只可能在层次最大的两层上出现;
特点二 : 对任一结点,若其右分支下子孙的最大层次为l,则其左分支下子孙的最大层次必为l 或l+1

建议看图对应文字综合理解

在这里插入图片描述
代码创建二叉树

首先,创建一个节点Node类

package demo5; /*  * 节(结)点类   */ public class Node {     //节点的权     int value;     //左儿子(左节点)     Node leftNode;     //右儿子(右节点)     Node rightNode;     //构造函数,初始化的时候就给二叉树赋上权值     public Node(int value) {         this.value=value;     }          //设置左儿子(左节点)     public void setLeftNode(Node leftNode) {         this.leftNode =