数据结构-树与二叉树剖析.ppt

二、森林与二叉树的转换 6.4 树和森林 3．二叉树到树或森林 方法： (1)? 若二叉树中某结点是其双亲结点的左孩子，则该结点的右孩子，右孩子的右孩子……都与该结点的双亲结点连线；(2) 去掉右孩子与原双亲结点的连线，若是转换成森林，还要将与根相连的右孩子连线去掉。 森林与二叉树之间的对应关系是惟一的，称二者的变换为自然对应。 6.4 树和森林 二、森林与二叉树的转换 通常：树和森林 二叉树 (运算)。 1.树有两种遍历方法 (1)先序遍历 a.若树非空，则先访问根结点； b.按从左到右的顺序先序遍历根结点的每一根子树。 先序遍历等价于对应二叉树的先序遍历。 (2) 后序遍历 a.若树非空，则先按从左到右的顺序后序遍历根结点的每一棵子树； b.访问根结点。 后序遍历等价于对应二叉树的中序遍历。 三、树与森林的遍历 6.4 树和森林 （a）树 (b)对应二叉树 对(a)的先序遍历序列为：GHIJ； 对(b)的先序遍历序列为：GHIJ，二者相同。 对(a)的后序遍历序列为：HJIG； 对(b)的中序遍历序列为：HJIG，二者相同。 6.4 树和森林 三、树与森林的遍历 所谓遍历就是按某指定规则访问数据结构中的所有结点，且每个结点只访问一次。 各种数据结构包括线性表也有遍历运算。这里“访问”的含义很广，可以对结点作各种处理，如输出结点信息、求结点个数等。 对于线性结构，遍历的运算比较简单。而对二叉树这种非线性结构，每个结点都可能有两棵子树，需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。 一、遍历二叉树 6.3 遍历二叉树和线索二叉树 1．遍历规则 二叉树是由三个基本单元组成：根结点、左子树和右子树。所谓遍历规则是指在遍历时是先访问根结点还是先访问子树，是先访问左子树还是先访问右子树。不同的遍历规则会产生不同的遍历结果。 以D、L、R表示访问根结点、左子树、右子树,有6种遍历方式：DLR、LDR、LRD、DRL、RDL、RLD 一般规定，在二叉树遍历中，按先访问左子树，后访问右子树的顺序进行遍历。 一、遍历二叉树 6.3 遍历二叉树和线索二叉树 有四种遍历： 先(根)序遍历(DLR) 1 2 4 8 9 5 10 11 3 6 12 7 中(根)序遍历(LDR) 8 4 9 2 10 5 11 1 12 6 3 7 后(根)序遍历(LRD) 8 9 4 10 11 5 2 12 6 7 3 1 层次遍历：先从上到下，再从左到右的顺序遍历 1 2 3 4 5 6 7 8 9 10 11 12 一、遍历二叉树 6.3 遍历二叉树和线索二叉树 2.遍历算法的基本思想 由二叉树是递归定义得出遍历二叉树也要采用递归算法遍历整个二叉树。 3.遍历算法 (1)先(根)序遍历(前序遍历) 基本思想：若二叉树非空，则按以下顺序遍历，否则结束。 a.访问根结点； b.先序遍历左子树； c.先序遍历右子树。 算法： void preorder(BiTNode *root) { if(root!=NULL) { visit(root-data); preorder(root-lchild); preorder(root-rchild); } } 一、遍历二叉树 6.3 遍历二叉树和线索二叉树 (2)中(根)序遍历 基本思想：若二叉树非空，则按以下顺序遍历，否则结束。 a.中序遍历左子树； b.访问根结点； c.中序遍历右子树。 算法： void inorder(BiTNode *root) { if(root!=NULL) { inorder(root-lchild); visit(root-data); inorder(root-rchild); } } 一、遍历二叉树 6.3 遍历二叉树和线索二叉树 (3)后(根)序遍历 基本思想：若二叉树非空，则按以下顺序遍历，否则结束。 a.后序遍历左子树； b.后序遍历右子树； c.访问根结点。 算法： void postorder(BiTNode *root) { if(root!=NULL) { postorder(root-lchild); p