遍历二叉树(数据结构)

数据结构——遍历二叉树主讲人：修小草点击播放即将开始主要内容：connectivism遍历二叉树问题遍历二叉树的方法复杂度分析习题与总结connectivism

按照某条搜索路径访问树中的每一个结点，使得每个结点均被访问一次，且仅被访问一次。遍历二叉树问题：

遍历对线性结构很容易解决；

遍历对二叉树则略微复杂。遍历二叉树问题connectivism遍历二叉树问题connectivism二叉树遍历的基本方法：从二叉树的定义知，一棵二叉树由三部分组成：根结点、左子树和右子树。若规定D，L，R分别代表“访问根结点”、“遍历根结点的左子树”和“遍历根结点的右子树”，根据遍历算法对访问根结点处理的位置，遍历整个二叉树就有6种方案：

DLR、LDR、LRDDRL、RDL、RLD遍历二叉树的方法connectivism后（根）序遍历中（根）序遍历先（根）序遍历基本方法3遍历二叉树的方法connectivismFirst先序遍历二叉树

先序遍历的操作定义为：

若二叉树为空，则空操作；否则1、访问根结点；2、先序遍历左子树；3、先序遍历右子树。根、左、右遍历二叉树的方法connectivismFirst先序遍历二叉树遍历二叉树的方法

voidPreOrder(BiTreeNode*t,voidVisit(DataTypeitem))/*先序遍历二叉树t，访问操作为Visit()函数*/

{if(t!=NULL){Visit(t->data); PreOrder(t->leftChild,Visit); PreOrder(t->rightChild,Visit);}}connectivismFirst先序遍历二叉树遍历二叉树的方法先序序列：-+a*b–cd/ef前缀表示（波兰式）前缀表示（波兰式）connectivismSecond中序遍历二叉树

中序遍历的操作定义为：若二叉树为空，则空操作；否则1、中序遍历左子树；2、访问根节点；3、中序遍历右子树。左、根、右遍历二叉树的方法connectivism遍历二叉树的方法Second中序遍历二叉树voidInOrder(BiTreeNode*t,voidVisit(DataTypeitem))/*中序遍历二叉树t*/{if(t!=NULL) {InOrder(t->leftChild,Visit); Visit(t->data); InOrder(t->rightChild,Visit); }}connectivism遍历二叉树的方法中序序列：a+b*c–d–e/f中缀表示Second中序遍历二叉树connectivismThird后序遍历二叉树

后序遍历的操作定义为：若二叉树为空，则空操作；否则1、后序遍历左子树；2、后序遍历右子树；3、访问根节点。左、右、根遍历二叉树的方法connectivismThird后序遍历二叉树遍历二叉树的方法voidPostOrder(BiTreeNode*t,voidVisit(DataTypeitem))/*后序遍历二叉树t*/{if(t!=NULL) {PostOrder(t->leftChild,Visit); PostOrder(t->rightChild,Visit); Visit(t->data); }}connectivism遍历二叉树的方法后序序列：abcd–*

+ef/-后缀表示（逆波兰式）Third后序遍历二叉树connectivismFour层序遍历二叉树层序遍历的要求是：按二叉树的层序次序（即从根结点层至叶结点层），同一层中按先左子树再右子树的次序遍历二叉树。层序遍历的特点：在所有未被访问结点的集合中，排列在已访问结点集合中最前面结点的左子树的根结点将最先被访问，然后是该结点的右子树的根结点。这样，如果把已访问的结点放在一个队列中，那么，所有未被访问结点的访问次序就可以由存放在队列中的已访问结点的出队列次序决定。因此可以借助队列实现二叉树的层序遍历。遍历二叉树的方法connectivism时间复杂度

遍历二叉树算法的基本思想是访问结点，无论是哪一种方法，对含有n个结点的二叉树，其时间复杂度均为O(n)。空间复杂度

遍历二叉树算法所需要的辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n，则空间复杂度也为O(n)。复杂度分析connectivism习题已知一棵二叉树的先序遍历序列为：abdgcefh，中序遍历序列为：dgbaechf，画出该二叉树，并写出其后序遍历序列。后序序列：gdbehfcaconnectivism中序遍历二叉树后序遍历