(6.3.1)--ch6-3二叉树的应用.pdf

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

1、 Data Structures and AlgorithmsApplication of Binary TreesData Structures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and Binary TreesApplication of traversal algorithm1）Output binary tree nodes2）Output binary tree leaf nodes3）Count the number of leaf nodes 4）Calculate

2、the height of binary tree5）Output the path from leaf node to root node6）Print binary tree by tree6.3 Binary Tree TraversalData Structures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and Binary TreesApplication of traversal algorithmABCDEFCDA BFE3)count the number of lea

3、f nodes12LeafCountData Structures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and Binary Treesint LeafCount=0;void LeafNum(BiTree root)if(root!=NULL)LeafCount+;LeafNum(root-lchild);LeafNum(root-rchild);Method 1:Set LeafCount as a global variable,and initialize to 0.if(r

4、oot-lchild=NULL&root-rchild=NULL)3)Application of traversal algorithmData Structures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and Binary TreesApplication of traversal algorithmABCDEF3)count the number of leaf nodesIf its an empty tree,return 0If there are no left and

5、 right children,return 1Otherwise,it is the sum of the number of leaf nodes of the left and right subtreesData Structures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and Binary Treesint leaf(BiTree root)int LeafCount;if(root=NULL)LeafCount=0;else if(root-lchild=NULL)&(r

6、oot-rchild=NULL)LeafCount=1;else LeafCount=leaf(root-lchild)+leaf(root-rchild);return LeafCount;Method 2:use function return valueApplication of traversal algorithm3)Data Structures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and Binary TreesOther applicationsApplicatio

7、n of traversal algorithm3)1）count the number of nodes thats degree is 1.2）count the number of nodes thats degree is 2.3）the value of nodes that are equal to x in binary tree.(root-lchild=NULL&root-rchild!=NULL)|(root-lchild!=NULL&root-rchild=NULL)root-lchild!=NULL&root-rchild!=NULLroot-data=xData St

8、ructures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and Binary TreesApplication of traversal algorithm1）Output binary tree nodes2）Output binary tree leaf nodes3）Count the number of leaf nodes 4）Calculate the height of binary tree5）Output the path from leaf node to root

9、 node6）Print binary tree by tree6.3 Binary Tree TraversalData Structures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and Binary Trees4)Application of traversal algorithmLet the function represent the height of the binary tree bt,then recursion is defined as follows:If b

10、t not empty,the root node level is 1,and the child node level is the parent node level value plus 1.ABCDEFlayers1 2 3 4C2D3A1B2F4E3Data Structures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and Binary Treesint depth=0;void PreTreeDepth(BiTree root,int h)if(root!=NULL)i

11、f(hdepth)depth=h;PreTreeDepth(root-lchild,h+1);PreTreeDepth(root-rchild,h+1);4)Application of traversal algorithmData Structures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and Binary Trees4)Application of traversal algorithmLet the function represent the height of the

12、binary tree bt,then recursion is defined as follows:pIf bt is empty,the height is 0;pIf bt is not empty,its height should be the maximum value of its left and right subtree height plus 1.left sub-treerightsub-tree bthlhrhigh=max(hl,hr)+1Data Structures and Algorithms Data Structures and Algorithms T

13、rees and Binary TreesTrees and Binary Treesint PostTreeDepth(BiTree root)int hl,hr,max;if(root!=NULL)hl=PostTreeDepth(root-lchild);hr=PostTreeDepth(root-rchild);max=hlhr?hl:hr;return max+1;else return 0;Can I do it in first-order or mid-order traversal?NO4)Application of traversal algorithmData Structures and Algorithms Data Structures and Algorithms Trees and Binary TreesTrees and Binary Trees Thanks Thanks！