栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Java二叉树

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Java二叉树

文章目录
  • 树
    • 二叉树
      • 二叉树的性质
      • 常见的二叉树
      • 满二叉树
      • 完全二叉树
      • 二分搜索树
    • 二叉树的遍历
      • 前序遍历
      • 小结

树

树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看 起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

  • 有一个特殊的节点,称为根节点,根节点没有前驱节点
  • 除根节点外,其余节点被分成M(M > 0)个互不相交的集合,每棵子树的根节点有且只有一个前驱,可以有0个或多个后继
  • 树是递归定义的

出现树这种结构,基本上就是高效的查找与搜索的语义

树的基本概念

  1. 子树不相交

  2. 除了根节点没有父节点以外,每个节点有且只有一个父节点

  3. 树中边的个数x(两个节点连成一条边),和树中节点的个数n的关系,x = n - 1

  4. 树和节点的度

    树的度:该树中最大的节点的度,就是树的度

    节点的度:该节点包含子树的个数,就称为节点的度,该节点有1个子树该节点的度就为1,有两个子树就为2

  5. 叶子节点,度为0的节点就是叶子节点,非叶子节点,度不为0的节点

  6. 根节点:没有父节点的节点,树中有且只有一个树节点

  7. 节点的层次:从根节点开始数,根节点为第一层,根节点的子树就为第二层,根节点子树的子树就位第三层,依此类推

  8. 树的高度:当前树中节点层次最大的即为树的高度

二叉树

树的每个节点最多有两个子树,不存在度大于2的节点,这样的树称为二叉树

二叉树的子树有左右之分,其子树的次序不能颠倒,因此二叉树是有序树

这两颗树并不相等,是两个完全不同的树

二叉树的性质
  1. 在深度为k的的二叉树中最多存在2^k -1 个节点
  2. 在第k层中,该层最多有2^(k - 1)个节点
  3. 因为二叉树都满足节点个数n和边长x ,具有 x = n - 1 ,因此在二叉树中,度为2的节点和度为0的节点有以下关系,度为2的节点个数为n2,度为0的节点个数为n0
  4. n0 = n2 + 1 ------> 推导 二叉树中结点满足 n0+n1+n2 = n ,边长满足n1 + 2n2 = n -1
常见的二叉树 满二叉树

满二叉树:在该二叉树中,每一层的节点个数都是该层的最大值

完全二叉树

完全二叉树:完全二叉树的结点编号,和对应的满二叉树相应位置的结点编号一致

完全二叉树只能是最后一层是不满的,并且结点都是靠左排列

在完全二叉树中,若存在度为1的节点,这个节点必然只有左子树没有右子树,且这个结点在二叉树中只能存在一个,否则就不是完全二叉树

关于完全二叉树的编号问题

1.若根节点从1开始编号

任意一个节点x,既存在子树也有父节点,则该节点的父节点编号为 “x/2”,左子树的节点编号为"2x",右子树的编号为"2x+1";

2.若根节点从0开始编号

任意一个节点x,既存在子树也有父节点,则该节点的父节点编号为"(x-1)/2",左子树的节点编号为"2x+1",右子树的节点编号为"2x+2";

二分搜索树

二分搜索树(BST):节点值之间有大小关系

左子树节点值 < 根节点值 < 右子树节点值

若在BST中查找一个元素,就是二分查找,若比根节点小就在左树中查找,若比根节点大就在右树中查找,若相等,说明找到了

二叉树的遍历

二叉树的遍历,是二叉树的基础操作,所有二叉树的问题的解决思路基本都是遍历问题的衍生

遍历的概念:按照一定的顺序访问这个集合的所有元素,做到不重复,不遗漏

对于二叉树来说,一共有四种遍历方式,分别是:”前序遍历、中序遍历、后序遍历和层序遍历",前序、中序、后序遍历称为深度优先遍历(dfs),层序遍历称为广度优先遍历()

前序遍历

前序遍历:先访问根节点,再递归访问左子树,之后再递归访问右子树

根左右的访问顺序

中序遍历:先递归访问左子树,然后访问根节点,之后递归访问右子树

左根右的访问顺序

后序遍历:先递归访问左子树,再递归访问右子树,最后访问根节点

左右根的访问顺序

层序遍历:从上至下,一层层先左后右遍历

上面的二叉树的各种遍历结果为

前序遍历:ABDEC

先访问根节点A,直接输出根节点A,因为是先递归访问左子树,所以向左走,走到B直接输出,然后B还有左子树继续向左走,走到D也是直接输出D,之后因为D的左子树为空,就访问B的右子树E,E的左右子树都为空,所以输出E,此时A的左子树已经全部访问,就到访问A的右子树C,C的左右子树都为空,输出C,所以是ABDEC

中序遍历:DBEAC

先访问根节点A,此时不能输出要第二次访问到才能输出,向左走走到B,同理继续向左走走到D,D也继续向左走,左树为空返回,再次访问到D,此时就可以输出D,访问完D又回到了根节点B,B是第二次访问,也可以输出,然后访问B的右子树E,接着访问E的左子树,E的左子树为空,第二次访问E输出E,E的右子树为空,此时A的左子树访问完毕,返回到A此时第二次访问A输出A,接着访问A的右子树C,C的左右子树为空,输出C

后序遍历:DEBCA

先访问根节点A,此时不能输出要第三次访问到才能输出,向左走走到B,B有左右子树一样不能输出继续向左访问,走到D,D向左访问为空回到D此时第二次访问到,之后再向右访问也是空再回到D,此时第三次访问到D输出D,之后回到B节点此时第二次访问到B节点不输出,向右访问走到E,E和D同理左右子树都为空,第三次访问到E输出E,之后再返回访问到B,此时第三次访问到输出B,这时A的左子树已经访问完毕,返回到A,第二次访问到A不输出,向右访问C,C的左右子树为空输出C,随后返回访问A,A第三次访问输出A

层序遍历:ABCDE

直接从上至下,从左到右依次访问

此二叉树的各种结果为

前序遍历:A B D E G H C F

中序遍历:D B G H E A C F

后序遍历:D H G E B F C A

层序遍历:A B C D E F G H

小结

1.前序遍历的第一个节点一定是根节点

2.中序遍历左子树在根节点的左侧,如B节点的左子树D在B的左侧,E在B的右侧,而E这个节点只有左子树所以G在E的左侧,而右侧为空,任何一个结点都满足

3.后序遍历的最后一个节点一定是根节点

后序遍历的结果一转置,reverse就变成了ACFBEGHD,变成了"根右左"访问顺序

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/963964.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号