Chapter二叉树的遍历PPT课件

1、1第1页/共62页2第2页/共62页3第3页/共62页4第4页/共62页5第5页/共62页6第6页/共62页7深度优先遍历深度优先遍历第7页/共62页8前序序列的第一个元素前序序列的第一个元素必为二叉树的根节点必为二叉树的根节点第8页/共62页9第9页/共62页10中序序列的中序序列的根节点根节点恰为恰为左右子树的中序序列的左右子树的中序序列的分界分界点点第10页/共62页11第11页/共62页12后序序列的后序序列的最后最后一个元素一个元素必为二叉树的必为二叉树的根节点根节点第12页/共62页13第13页/共62页14第14页/共62页15第15页/共62页16第16页/共62页17第17页

2、/共62页18第18页/共62页19第19页/共62页20toptopT1BAtopT2AtopT3topET3topT4第20页/共62页21第21页/共62页22第22页/共62页23第23页/共62页24第24页/共62页25第25页/共62页26第26页/共62页27第27页/共62页28结论结论第28页/共62页29第29页/共62页30第30页/共62页31第31页/共62页32n n 第32页/共62页33第33页/共62页34第34页/共62页35第35页/共62页36第36页/共62页37第37页/共62页38第38页/共62页39第39页/共62页40时间复杂度时间复杂度(

3、n)(n)第40页/共62页41时间复杂度时间复杂度(n)(n)第41页/共62页42时间复杂度时间复杂度(n)(n)第42页/共62页43时间复杂度时间复杂度(n)(n)第43页/共62页44调用示例调用示例1234第44页/共62页45第45页/共62页46第46页/共62页47时间复杂度时间复杂度(n)(n)第47页/共62页48时间复杂度时间复杂度(n)(n)第48页/共62页49时间复杂度时间复杂度(n)(n)第49页/共62页50时间复杂度时间复杂度(n)(n)第50页/共62页51第51页/共62页52第52页/共62页53第53页/共62页54Preorder sequence

4、 is 4 3 1 2Inorder sequence is 1 3 2 4Postorder sequence is 1 2 3 4Level order sequence is 4 3 1 2Number of nodes = 4Height = 3Count of nodes is 41234第54页/共62页55二叉树遍历的非递归算法二叉树遍历的非递归算法 递归算法转换为等价的非递归算法，使用递归算法转换为等价的非递归算法，使用“栈栈” 以前序为例：根以前序为例：根- -左左- -右，左下降右，左下降 abcdev 思考：如果能在左下降的过程中，记录留待以后思考：如果能在左下降的过程中

5、，记录留待以后访问的右子树的根结点，以便在遍历完一个结点的左访问的右子树的根结点，以便在遍历完一个结点的左子树后能转移到这个结点的右子树，即可实现！子树后能转移到这个结点的右子树，即可实现！第55页/共62页56非递归前序遍历二叉树非递归前序遍历二叉树 主要思想：每遇到一个结点，先访问该结点，并主要思想：每遇到一个结点，先访问该结点，并把该结点的把该结点的非空非空右子结点压入栈中右子结点压入栈中，然后遍历其，然后遍历其左子树；当左子树为空时，从栈顶弹出待访问的左子树；当左子树为空时，从栈顶弹出待访问的结点，继续遍历。结点，继续遍历。abcde访问访问a进栈进栈c左进左进b访问访问b进栈进栈d左

6、进左进空空退栈退栈d访问访问d左进左进空空退栈退栈c访问访问c左进左进e访问访问e左进左进空空退栈退栈 c dc c 结束结束第56页/共62页57算法描述算法描述void PreOrder( BinTree T ) stack S; InitStack(&S); /递归工作栈递归工作栈 BinTreeNode * p = T; Push (&S, NULL); while ( p != NULL ) cout data rightChild != NULL ) Push ( &S, p-rightChild ); if ( p-leftChild != NULL )

7、p = p-leftChild; /进左子树进左子树 else Pop( &S, p ); 第57页/共62页58非递归中序遍历二叉树非递归中序遍历二叉树 主要思想：主要思想：每遇到一个每遇到一个非空非空结点就把它压入栈结点就把它压入栈，然后去遍历其左子树；遍历完左子树后，从栈中然后去遍历其左子树；遍历完左子树后，从栈中弹出并访问这个结点，然后再去访问该结点的右弹出并访问这个结点，然后再去访问该结点的右子树。子树。abcdebaa b入栈入栈ab退栈退栈访问访问dad入栈入栈ad退栈退栈访问访问a退栈退栈访问访问ecc e 入栈入栈ce e 退栈访问退栈访问c c 退栈访问退栈访问栈空

8、栈空第58页/共62页59非递归后序遍历二叉树非递归后序遍历二叉树 主要思想：每遇到一个非空结点，先把它压入栈，主要思想：每遇到一个非空结点，先把它压入栈，然后去遍历其左子树；遍历完其左子树后，应继然后去遍历其左子树；遍历完其左子树后，应继续遍历该结点的右子树；遍历完右子树之后，才续遍历该结点的右子树；遍历完右子树之后，才从栈中弹出并访问这个结点。从栈中弹出并访问这个结点。v后序遍历二叉树：左子树后序遍历二叉树：左子树-右子树右子树-当前节点当前节点v需要注意：访问某个结点之前，需要知道是否已经需要注意：访问某个结点之前，需要知道是否已经访问该结点的右子树，因此需要给结点加一个标志访问该结点的

9、右子树，因此需要给结点加一个标志位位tag， Left：表示已经进入该结点的左子树：表示已经进入该结点的左子树 Right：表示已经进入该结点的右子树：表示已经进入该结点的右子树第59页/共62页60后序遍历时使用的栈的结点定义后序遍历时使用的栈的结点定义typedef struct BinTreeNode *ptr; /结点指针结点指针 enum tag L, R ; /该结点退栈标记该结点退栈标记 StackNode; 根结点的根结点的 tag = L，表示从左子树退出，表示从左子树退出, 访问右子树。访问右子树。 tag = R, 表示表示从右子树退出从右子树退出, 访问根。访问根。第60页/共62页61void PostOrder ( BinTree T ) stack S; InitStack(&S); StackNode w; BinTreeNode * p = T; d