(6.2.1)--ch6-2二叉树的遍历.pdf

《(6.2.1)--ch6-2二叉树的遍历.pdf》由会员分享，可在线阅读，更多相关《(6.2.1)--ch6-2二叉树的遍历.pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 Data Structures and AlgorithmsBinary Tree TraversalData Structures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and Binary TreesTraversal：Each node in the binary tree is visited along a certain search path,so that each node is visited once and only once.The meaning of v

2、isit can be very broad,for example:print the information of nodes,etc.6.3 Binary Tree Traversal DLR DRL LDR RDL LRD RLDFrom left to rightFrom left to rightData Structures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and Binary Treesfirst-order traversal mid-order travers

3、allast-order traversalDLR：LDR：LRD：6.3 Binary Tree TraversalData Structures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and Binary TreesABCDEFGThe result of first-order traversal:ABDGCEFIf the binary tree is empty,no action will be taken;Otherwise:（1）D:Visit the root nod

4、e;（2）L:The left subtree in first-order;（3）R:The right subtree in first-order.first-order traversal algorithmA B D G C E F6.3 Binary Tree TraversalData Structures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and Binary Treesvoid PreOrder(BiTree root)if(root!=NULL)visit(ro

5、ot-data);PreOrder(root-lchild);PreOrder(root-rchild);printf(“%c”,root-data);first-order traversal algorithm6.3 Binary Tree TraversalData Structures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and Binary TreesThe result of mid-order traversal:If the binary tree is empty,

6、no action will be taken;Otherwise:（1）L:The left subtree in mid-order;（2）D:Visit the root node;（3）R:The right subtree in mid-order.mid-order traversal algorithm6.3 Binary Tree TraversalABCDEFGABDGCEFABD GCEFData Structures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and

7、Binary Treesvoid InOrder(BiTree root)if(root!=NULL)InOrder(root-lchild);visit(root-data);InOrder(root-rchild);printf(“%c”,root-data);mid-order traversal algorithm6.3 Binary Tree TraversalData Structures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and Binary TreesThe res

8、ult of mid-order traversal:If the binary tree is empty,no action will be taken;Otherwise:（1）L:The left subtree in last-order;（2）R:The right subtree in last-order;（3）D:Visit the root node.last-order traversal algorithm6.3 Binary Tree TraversalABCDEFGABDGCEFABDGCE FData Structures and Algorithms Data

9、Structures and Algorithms Trees and Binary TreesTrees and Binary Treesvoid PostOrder(BiTree root)if(root!=NULL)PostOrder(root-lchild);PostOrder(root-rchild);visit(root-data);printf(“%c”,root-data);last-order traversal algorithm6.3 Binary Tree TraversalData Structures and Algorithms Data Structures a

10、nd Algorithms Trees and Binary TreesTrees and Binary Trees6.3 Binary Tree TraversalPracticeABCDFGHEIJKPreOrder sequence:InOrder sequence:PostOrder sequence:EDA BIHCJFKGHED BAIFCJKGEHD IJBFGKACData Structures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and Binary Trees Thanks Thanks！