数据结构基本知识叉树遍历.pptVIP

第5章第2节 1.树的定义及性质 树(tree)是n(n?0)个结点的有限集T，其中： 有且仅有一个特定的结点，称为树的根(root) 当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。 3.二叉树的存储结构 顺序存储结构 按满二叉树的结点层次编号，依次存放二叉树中的数据元素 4.树与二叉树转换 5.2 二叉树的遍历 遍历——按一定规律走遍树的各个结点，且使每一结点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列。 常用方法 先序遍历：先访问根结点,然后分别先序遍历左子树、先序遍历右子树。 中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树。 后序遍历：先后序遍历左、后序遍历右子树，然后访问根结点 例：对如下二叉树进行前序遍历的结果为 例：对如下二叉树进行中序遍历的结果为 例：对如下二叉树进行后序遍历的结果为 例1：已知一棵二叉树的先序序列为CEDBA，中序序列为DEBAC，试构造该二叉树。 基本思想： 在先序序列中找根，在中序序列中分左右。 例2：已知一棵二叉树的后序序列为DABEC，中序序列为DEBAC，试构造该二叉树。 基本思想： 在后序序列中找根，在中序序列中分左右。 4. 树和森林的遍历 树的遍历 先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树 后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点 按层次遍历：先访问第一层上的结点，然后依次遍历第二层，……第n层的结点 4. 树和森林的遍历 森林的遍历 先根（序）遍历： 先访问第一颗树的根结点 先根遍历第一颗树中根结点的子树森林 先根遍历除去第一颗树之后剩余树构成的森林 后根（序）遍历 后跟遍历第一颗树的根结点的子树森林 访问第一颗树的根结点 后跟遍历除去第一颗树之后剩余树构成的森林 2.二叉树先序遍历的非递归算法 A B C D E F G p i P-A (1) 访问：A A B C D E F G p i P-A P-B (2) 访问：AB A B C D E F G p i P-A P-B P-C (3) 访问：ABC A B C D E F G p i P-A P-B (4) 访问：ABC A B C D E F G i P-A P-D P-E 访问：ABCDE p (7) p=NULL A B C D E F G i P-A (5) 访问：ABC p=NULL A B C D E F G i P-A P-D (6) 访问：ABCD A B C D E F G i P-A P-D 访问：ABCDE p (8) A B C D E F G i P-A P-F 访问：ABCDEGF p (12) A B C D E F G i P-A P-D P-G 访问：ABCDEG p (9) A B C D E F G i P-A 访问：ABCDEG p (11) A B C D E F G i P-A P-D 访问：ABCDEG p (10) A B C D E F G i P-A 访问：ABCDEGF p (13) A B C D E F G i 访问： ABCDEGF p=NULL (14) 2.二叉树先序遍历的非递归算法 (2)中序遍历的非递归算法 令p指向根结点。 若p不为空，将p压入栈中。 若p为空，转4。 将p所指结点的左孩子压入栈，转2。 从栈中弹出栈顶结点，访问所弹出结点，令p指向所弹出结点的右孩子；转2。 2.二叉树中序遍历的非递归算法 A B C D E F G p i P-A (1) A B C D E F G p i P-A P-B (2) A B C D E F G p i P-A P-B P-C (3) p=NULL A B C D E F G i P-A P-B 访问：C (4) p A B C D E F G i P-A 访问：C B (5) A B C D E F G i P-A P-D 访问：C B p (6) A B C D E F G i P-A P-D P-E 访问：C B p (7) A B C D E F G i P-A P-D 访问：C B E p (8) A B C D E F G i P-A P-D P-G 访问：C B E P=NULL (9) A B C D E F G i P-A 访问：C B E G D p (11) A B C D E F G i P-A P-F 访问：C B E G D p (12) A B C D E F G i P-A P-D 访问：C B E G p (10) A B C D E F G i P-A