二叉树也是一种数据结构(废话)。妥妥的树形结构,没有听过树形结构?太晦涩?树一定都见过
主干分叉,分叉再分叉。。。。最后不分了,就开始长出叶子。这就是树。 二叉树结构横空出世。区别就是,每次只能分两个子节点,所以叫二叉树。分多个,也是树,就不能称为二叉树了,小科普。
举个典型的例子,编程中,省、市、区县、街道的数据组成,分两个叉?一个省只有两个市?一个市只有两个区县?这就不属于二叉树的范畴了。
我们给二叉树加上数字标记位置
根节点从1开始,从上到下,从左到右来标记位置
二叉树只有这一种形态?
满二叉树、完全二叉树、不完全二叉树
好像不满?但他也是二叉树,叫 完全二叉树- 每一层都是从左到右,相邻节点是连续的
- 并且最后一层以上的所有层,均是满的,为完全二叉树,如下图
- 满二叉树也是完全二叉树!
- 同一层从左到右出现缺失,不连续
- 或者最后一层以上的所有层,也有缺失
找规律
深度、层、高度、度
补充一个小概念:度?某个节点的度,就是该节点拥有子节点的数量。上图,节点[1]的度=2, 节点[2]的度=2,节点[8]、节点[9]到节点[15]的度为0.我们从上图可以发现
- 在第i层上,有 个节点
- 最大深度为k时,整个二叉树最多有 2k-1 个节点
- 终端节点数 = 度为2的节点数+1;(终端节点就是叶子节点,度为0的节点)
- 有n个节点完全二叉树,深度 =
- 有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