二叉树
二叉树是每个节点最多有两个子树的树结构,通常子树被称作"左子树"和"右子树",左子树和右子树同时也是二叉树,二叉树的子树有左右之分,并且次序不能任意颠倒.二叉树是递归定义的,
特殊二叉树:
斜树:
所有的结点都只有左子树(左斜树),或者只有右子树(右斜树)
满二叉树:
所有的分支结点都存在左子树和右子树,并且所有的叶子结点都在同一层上,这样就是满二叉树.就是完美圆满的意思,关键在于树的平衡.
特点为:
叶子只能出现在最下一层
非叶子节点度一定是
在同样深度的二叉树中,满二叉树的结点个数最多,叶子树最多
完全二叉树:
对一颗具有n个结点的二叉树按层序排号,如果编号为i的结点与同样深度的满二叉树编号为i结点在二叉树中位置完全相同,就是完全二叉树,满二叉树必须是完全二叉树,反过来不一定成立
特点:
叶子结点只能出现在最下一层(满二叉树继承而来)
最下层叶子结点一定集中在左部连续位置
倒数第二层,如有叶子结点,一定出现在右部连续位置
同样结点树的二叉树,完全二叉树的深度最小(满二叉树也是对的)

二叉树的遍历:
从树的根节点出发,按照某种次序依次访问二叉树中所有的结点,使得每个结点被访问仅且一次
前序遍历:
基本思想: 先访问根结点,再先序遍历左子树,最后再先序遍历右子树即根一左一右
中序遍历:
基本思想: 先中序遍历左子树,然后再访问根结点,最后再中序遍历右子树即左一根一右
后序遍历:
基本思想: 先后序遍历左子树,然后再后序遍历右子树,最后再访问根结点即左一右一根
二叉树的作用:
二叉排序树是一种比较有用的折衷方案
数组的搜索比较方便,可以直接用下标,但删除或者插入某些元素就比较麻烦
链表与之相反,删除和插入元素很快,但查找很慢
二叉排序树就既有链表的好处,也有数组的好处
在处理大批量的动态的数据是比较有用
用的最多的应该是平衡二叉树,有种特殊的平衡二叉树红黑树,查找,插入,删除的时间复杂度最坏为O(log n)
平衡二叉树/红黑树就是为了将查找的时间复杂度保证在O(logN)范围内
二叉树之所以重要,是因为它支持或拥有的操作,包括增删改查重要的操作,复杂度比完成同样功能的其他结构更低

二叉树
二叉树是每个节点最多有两个子树的树结构,通常子树被称作"左子树"和"右子树",左子树和右子树同时也是二叉树,二叉树的子树有左右之分,并且次序不能任意颠倒.二叉树是递归定义的,
特殊二叉树:
斜树:
所有的结点都只有左子树(左斜树),或者只有右子树(右斜树)
满二叉树:
所有的分支结点都存在左子树和右子树,并且所有的叶子结点都在同一层上,这样就是满二叉树.就是完美圆满的意思,关键在于树的平衡.
特点为:
叶子只能出现在最下一层
非叶子节点度一定是
在同样深度的二叉树中,满二叉树的结点个数最多,叶子树最多
完全二叉树:
对一颗具有n个结点的二叉树按层序排号,如果编号为i的结点与同样深度的满二叉树编号为i结点在二叉树中位置完全相同,就是完全二叉树,满二叉树必须是完全二叉树,反过来不一定成立
特点:
叶子结点只能出现在最下一层(满二叉树继承而来)
最下层叶子结点一定集中在左部连续位置
倒数第二层,如有叶子结点,一定出现在右部连续位置
同样结点树的二叉树,完全二叉树的深度最小(满二叉树也是对的)

二叉树的遍历:
从树的根节点出发,按照某种次序依次访问二叉树中所有的结点,使得每个结点被访问仅且一次
前序遍历:
基本思想: 先访问根结点,再先序遍历左子树,最后再先序遍历右子树即根一左一右
中序遍历:
基本思想: 先中序遍历左子树,然后再访问根结点,最后再中序遍历右子树即左一根一右
后序遍历:
基本思想: 先后序遍历左子树,然后再后序遍历右子树,最后再访问根结点即左一右一根
二叉树的作用:
二叉排序树是一种比较有用的折衷方案
数组的搜索比较方便,可以直接用下标,但删除或者插入某些元素就比较麻烦
链表与之相反,删除和插入元素很快,但查找很慢
二叉排序树就既有链表的好处,也有数组的好处
在处理大批量的动态的数据是比较有用
用的最多的应该是平衡二叉树,有种特殊的平衡二叉树红黑树,查找,插入,删除的时间复杂度最坏为O(log n)
平衡二叉树/红黑树就是为了将查找的时间复杂度保证在O(logN)范围内
二叉树之所以重要,是因为它支持或拥有的操作,包括增删改查重要的操作,复杂度比完成同样功能的其他结构更低