数据结构_ 树和叉树.pptVIP

A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^ ^ 三叉链表图示 B A C D E F G 三叉链表 lchild data 结点结构 parent rchild 6.4 二叉树的遍历和线索 6.4.1 二叉树的遍历 定义：所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。 这里所提的“访问”的含义很广，可以是查询、修改、输出某元素的值，以及对元素作某种运算等等。但要求这种访问不破坏它原来的数据结构。遍历一个线性结构很简单，只须从开始结点出发，顺序扫描每个结点即可。但对二叉树这样的非线性结构，每个结点可能有两个后继结点，因此需要寻找一种规律来系统访问树中的各结点。 如何访问二叉树的每个结点且 每个结点仅被访问一次？ 由二叉树的定义是递归的，它是由三个基本单元组成，即根结点、左子树和右子树。因此，遍历一棵非空二叉树的问题可以分解为三个子问题：访问根结点、遍历左子树、遍历右子树，只要依次遍历这三部分，就可以遍历整个二叉树。 由于实际问题一般都是要求左子树较右子树先遍历，分别称为先序遍历、中序遍历和后序遍历。 令L，R，D分别代表二叉树的左子树、右子树、根结点，则有DLR、LDR、LRD三种遍历规则。 递归实现方法 若二叉树非空，则： 1. 访问根结点 2. 先序遍历左子树 3. 先序遍历右子树 B A D C D L R A D L R D L R B D C D L R 得到的序列为：A B D C 先序遍历二叉树 Status PreOrderTraverse( BiTree T ) {//采用二叉链表存贮二叉树 if (T) { //若二叉树不为空 Visit(T-data)； //访问根结点  PreOrderTraverse(T-lchild); //先序遍历T的左子树 PreOrderTraverse(T-rchild); //先序遍历T的右子树} //PreOrderTraverse 先序遍历二叉树算法实现 若二叉树非空，则： 1. 中序遍历左子树 2. 访问根结点 3. 中序遍历右子树 B A D C L D R B L D R L D R A D C L D R 得到的序列为： B D A C 中序遍历二叉树 若二叉树非空，则： 1. 后序遍历左子树 2. 访问根结点 3. 后序遍历右子树 B A D C L R D L R D L R D A D C L R D B 得到的序列为： D B C A 后序遍历二叉树 void leaf( BiTree T ) { //采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶子结点个数，本算法在先序遍历二叉树的过程中，统计叶子结点的个数，初始化n=0 if( T ) { if( T-lchild==NULLT-rchild==NULL) n+=1; //若T所指结点为叶子结点则计数 leaf(T-lchild); leaf(T-rchild); } //if } //leaf 例 编写求二叉树的叶子结点个数的算法 输入：二叉树的先序序列 结果：二叉树的二叉链表 问题：遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是否可利用遍历，建立二叉链表的所有结点并完成相应结点的链接？ 基本思想：输入在空子树处添加字符￠的二叉树的按先序遍历的顺序，建立二叉链表的所有结点并完成相应结点链接。 B A D C E F ￠ ￠ ￠ ￠ ￠ ￠ ￠ 在空子树处添加￠的二叉树的先序序列： A B D ￠ F ￠ ￠ E ￠ ￠ C ￠ ￠ 例 建立二叉链表 Status CreateBiTree( BiTree T ) { //输入(在空子树处添加字符￠的二叉树的)先序序列(设元素均为字符)