二叉树——初探

436 阅读3分钟

二叉树也是一种数据结构(废话)。妥妥的树形结构,没有听过树形结构?太晦涩?树一定都见过

主干分叉,分叉再分叉。。。。最后不分了,就开始长出叶子。这就是树。

二叉树结构横空出世。

区别就是,每次只能分两个子节点,所以叫二叉树。分多个,也是树,就不能称为二叉树了,小科普。
举个典型的例子,编程中,省、市、区县、街道的数据组成,分两个叉?一个省只有两个市?一个市只有两个区县?这就不属于二叉树的范畴了。

我们给二叉树加上数字标记位置

根节点从1开始,从上到下,从左到右来标记位置

二叉树只有这一种形态?

满二叉树、完全二叉树、不完全二叉树

好像不满?但他也是二叉树,叫 完全二叉树

  • 每一层都是从左到右,相邻节点是连续的
  • 并且最后一层以上的所有层,均是满的,为完全二叉树,如下图
  • 满二叉树也是完全二叉树!

什么是不完全二叉树?

  • 同一层从左到右出现缺失,不连续
  • 或者最后一层以上的所有层,也有缺失

找规律

深度、层、高度、度

补充一个小概念:度?某个节点的度,就是该节点拥有子节点的数量。上图,节点[1]的度=2, 节点[2]的度=2,节点[8]、节点[9]到节点[15]的度为0.

我们从上图可以发现

  • 在第i层上,有 2^{i-1} 个节点
  • 最大深度为k时,整个二叉树最多有 2k-1 个节点
  • 终端节点数 = 度为2的节点数+1;(终端节点就是叶子节点,度为0的节点)
  • 有n个节点完全二叉树,深度 = \log_2n+ 1
  • 有n个节点的完全二叉树,从根节点开始标号,标号i从1开始,如上面的完全二叉树,那么
    • i>1,i节点的双亲节点为i/2;
    • 如果i=1,那么序号为i的结点为根节点,无双亲结点
    • 如果2i<=n,那么序号为i的结点的左孩子结点序号为2i
    • 如果2i>n,那么序号为i的结点无左孩子
    • 如果2i+1<=n,那么序号为i的结点右孩子序号为2i+1
    • 如果2i+1>n,那么序号为i的结点无右孩子

二叉树的遍历

有这么一个二叉树

我们有几种方式来遍历呢?

前序遍历

规则: 若二叉树为空,则空操作返回; 否则先访问根结点,然后前序遍历左子树,再前序遍历右子树

A -> B -> D -> G -> H -> C -> E -> I -> F

中序遍历

规则: 若二叉树为空,则空操作返回; 否则从根结点开始(注意并不是先访问根结点), 中序遍历根结点的左⼦树,然后是访问根结点,最后中序遍历右子树.

G->D->H->B->A->E->I->C->F

后序遍历

规则: 若二叉树为空,则空操作返回; 否则从左到右先叶子后结点的⽅式遍历左右⼦树,最后访问根结点

G->H->D->B->I->E->F->C->A

层序遍历

从上到下,从左到右 A B C D E F G H I