家族谱。有时候碰到的问题 ，不是线性结构，是树形结构处理的。
一、二叉树
这种树的每个结点最多只有2个孩子结点。
满二叉树: 非叶子结点，都有左右孩子，并且所有的叶子结点 在同一水平线上。
完全二叉树: 符合按照编号，从左右到的编号。 满二叉树更严格一些。
二、存储
链表很好理解了。那数组呢？
按顺序从左到右的编号，进行存储。如果有丢失的 左 或者 右孩子结点，也要保留空的位置。二叉堆，一种特殊的完全二叉树，适合用数组存储。
三、查找
二分查找树:左子树上的所有的结点都小于根结点，右子树都大于根结点。
二叉树的自平衡:红黑树
四、遍历
深度优先遍历:前、中、后 以根为第一顺序。
广度优先遍历:层序遍历
前序遍历:根 左 右
中序遍历:左 根 右
后序遍历:左 右 根
递归和栈 都有回溯。
五、二叉堆
5.1一种完全二叉树
最大堆: 根 都>=左右
最小堆: 根 都<=左右
5.2二叉堆的自由调整
起初三个节点:
image.png
依次插入5个节点:7,6,5,4,3
image.png
红黑树 就是一种平衡二叉树。调整 变色、左旋、右旋。
网友评论