1.二叉树的遍历
先序遍历、中序遍历、后序遍历
2.层次遍历
利用队列实现
3.由遍历序列构成二叉树
先序、后序可以与众序确定二叉树
层序和中序或后序可以确定二叉树
4.线索二叉树
基本概念：遍历二叉树是以一定的规则将二叉树中的结点拍成一个线性序列，从而得到集中遍历序列，使得该序列中的每个结点（第一个和最后一个结点除外）都有一个直接前驱和直接后继
5.树的存储结构
双亲表示法
孩子表示法
孩子兄弟表示法
6.树、森林与二叉树的转换
树转换为二叉树的规则：
每个结点左指针指向它的第一个孩子，右指针指向它再树中的相邻兄弟
树转换成二叉树的画法：
在兄弟结点之间加一连线
对每个结点，只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉
以树根为轴心，顺时针旋转45度
森林转换成二叉树的画法
将森林中的每棵树转换成相应的二叉树
每根树的根也可视为兄弟关系，在每根树的根之间加一根连线
以第一棵树的根为轴心顺时针旋转45度
二叉树转换为森林的规则
若二叉树非空，则二叉树的根及其左子树为第一课树的二叉树形式，故将根的右链断开
二叉树根的右子树又可视为一个由除第一棵树外的森林转换后的二叉树
应用同样的方法，直到最后只剩一颗没有右子树的二叉树为止，最后再将每棵二叉树依次转换成树就得到了原森林
7.树和森林的遍历
先根遍历
后根遍历
先序遍历森林
中序遍历森林
网友评论