树的基础知识.pptVIP

1 树 1.1 树 1.1 树 1.1 树 1.1 树 1.1 树 1.2 二叉树 1.2 二叉树 1.2 二叉树 1.2 二叉树 1.2 二叉树 1.2 二叉树 1.2 二叉树 1.2 二叉树 1.3 二叉树的遍历 1.3 二叉树的遍历 1.3 二叉树的遍历 1.3 二叉树的遍历 1.3 二叉树的遍历 1.3 二叉树的遍历 1.3 二叉树的遍历 1.4 线索二叉树 1.4 线索二叉树 1.4 线索二叉树 1.4 线索二叉树 1.4 线索二叉树 1.4 线索二叉树 1.5 树和森林 1.5 树和森林 1.5 树和森林 1.5 树和森林 1.5 树和森林 1.5 树和森林 1.5 树和森林 1.5 树和森林 1.5 树和森林 1.5 树和森林 1.5 树和森林 1.5 树和森林 1.5 树和森林 1.5 树和森林 1.5 树和森林 1.5 树和森林 1.5.1 树的存储结构 2、孩子链表表示法 数组元素类型定义： typedef struct { datatype info; struct node *firstchild; } arrelemnt; 定义数组： arrelemnt tree[MAXNUM]; 1.5.1 树的存储结构 示例： A 0 B 1 C 2 D 3 E 4 F ^ 5 G ^ 6 H ^ 7 I ^ 8 J ^ 9 K ^ 10 下标 info firstchild 1 2 3 ^ 4 5 7 6 ^ 8 ^ 9 ^ 10 ^ A B F E D C G I H J K 1.5.1 树的存储结构 3、孩子—兄弟链表表示法 在树中，每个结点除其信息域外，再增加两个分别指向该结点的第一个孩子结点的指针firstson和下一个兄弟结点的指针nextbrother。 结点类型定义： typedef struct node { datatype data; struct node *firstson，*nextbrother; } tnode; 1.5.1 树的存储结构 示例： A ^ B C D ^ H ^ I ^ ^ J ^ ^ E F ^ G ^ ^ K ^ ^ T 1.5.2 树(森林)与二叉树的转换 1、森林到二叉树的转换 如果森林用有序表T=(T1，T2，……，Tm)来表示，则将森林T转换为对应的二叉树BT的形式化描述如下： 如果m=0，则BT为空；否则依次作如下操作： （1）将T1的根作为BT的根； （2）将T1的子树森林转换为BT的左子树； （3）将(T2，T3，……，Tm)转换为BT的右子树。 1.5.2 树(森林)与二叉树的转换 示例： A B C D G F E I H J K N M L P O 1.5.2 树(森林)与二叉树的转换 A B C D G F E I H J K N M L P O 1.5.2 树(森林)与二叉树的转换 2、二叉树到森林的转换 将二叉树BT转换为森林T＝(T1，T2……Tm)的形式化描述如下： 如果若BT不空，则依次执行如下操作： （1）将BT的根转换为T1的根； （2）将BT的左子树转换为T1的子树森林； （3）将BT的右子树转换为（T2，……Tm）。 1.5.3 树(森林) 的遍历 1、先序遍历森林 先序遍历森林T=(T1，T2……Tm)的描述如下： 若T不空，则依次执行如下操作： （1）访问T1的根； （2）先序遍历T1的子树森林； （3）先序遍历森林（T2，T3……Tm）； 1.5.3 树(森林) 的遍历 1、先序遍历森林 算法如下： void preorder(Tnode *T) //先序遍历森林 { if (t!=NULL) { visite(T); //访问结点 preorder(T-firstson