二叉树的特点
二叉树重点在于二,注意树的度
因为不是所有的树都是二叉树,而一种新的表示方式可以将树转化为二叉树来研究,孩子兄弟表示法(二叉链表示法)。
树的遍历有前序遍历,后序遍历,层序遍历
先研究二叉树的特点,有斜二叉树,满二叉树,完全二叉树(按照层序遍历位置与满二叉树一致,那么是完全二叉树)
由于二叉树的数学特点,可以完全二叉树直接从顺序表示法读出二叉树的逻辑结构。
二叉树的存储结构:顺序存储结构和链式存储结构
顺序存储结构:只有一个数据域。如果二叉树不是完全二叉树,那么先补全,数据域作为一个空节点,然后按照完全二叉树的方式进行存储。
缺点:当二叉树是右斜树的时候,需要的空节点太多,空间效率太低。所以二叉树一般采用链式存储结构
二叉树的链式存储结构:一个数据域,两个指针域,分别指向左右两个孩子。二叉链表