数据结构二叉树遍历.doc

"数据结构二叉树遍历" 二叉树遍历是数据结构中的一种基本操作，它是指按照某种规则访问二叉树的每个结点，每个结点仅被访问一次。二叉树遍历的定义、类型、算法和应用都是数据结构学习的重要内容。 二叉树遍历的定义 二叉树遍历是指按照某种规则访问二叉树的每个结点，每个结点仅被访问一次。“访问”的含义十分广泛，包括对结点所作的各种操作与处理，如打印每个学生的学号、XX、成绩等信息，将每个学生的成绩由百分制记分改为五级制记分，统计优、良、中、及格和不及格各档次的人数等。 二叉树的基本单元 一棵二叉树由根结点、左子树、右子树三个基本单元组成，根结点处于一个分割左子树和右子树的位置。遍历二叉树的规则可以有 NLR、LNR、LRN 三种遍历和 NRL、RNL、RLN 三种逆遍历方式，但通常限定先左后右，仅讨论前三种遍历，分别称之为前序遍历、 中序遍历和后序遍历。 前序遍历 前序遍历是指最先访问根结点，然后访问左子树，最后访问右子树。基于二叉树的递归定义，可以得到前序遍历二叉树的递归定义： 1. 若二叉树为空，则空操作； 2. 访问根结点； 3. 前序遍历左子树； 4. 前序遍历右子树。 中序遍历 中序遍历是指根结点在访问左、右子树之间被访问。基于二叉树的递归定义，可以得到中序遍历二叉树的递归定义： 1. 若二叉树为空，则空操作； 2. 中序遍历左子树； 3. 访问根结点； 4. 中序遍历右子树。 后序遍历 后序遍历是指根结点在左、右子树访问之后被访问。基于二叉树的递归定义，可以得到后序遍历二叉树的递归定义： 1. 若二叉树为空，则空操作； 2. 后序遍历左子树； 3. 后序遍历右子树； 4. 访问根结点。 前序遍历算法 前序遍历的递归算法可以根据实际应用具体化为其他操作，如输出打印结点值、将每个学生的成绩由百分制记分改为五级制记分、统计优、良、中、及格和不及格各档次的人数等。假设二叉树以二叉链表存储，对结点的访问操作简化为输出打印结点值，可以得到前序遍历二叉树的递归算法： 算法 6.1void Preorder(Bitree T) { If (T) { Printf("%d", T->data); // 访问根结点 Preorder(T->Lchild); // 遍历左子树 Preorder(T->Rchild); // 遍历右子树 } return; } 二叉树遍历的应用 二叉树遍历有很多实际应用，如管理学生考试成绩、统计优、良、中、及格和不及格各档次的人数、打印每个学生的学号、XX、成绩等信息等。 二叉树遍历是数据结构中的一种基本操作，它有多种遍历方式和算法，广泛应用于实际生活中。