“算法与数据结构”-树与二叉树da.ppt

《“算法与数据结构”-树与二叉树da.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二叉树的遍历在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对中的结点逐一进行某种处理，这就提出了遍历二叉树（traversingbinarytree）的问题，即按照某种搜索路径寻访树中的每一个结点，使得每个结点均被访问一次，而且仅被访问一次。二叉树是由3个基本单元组成：根节点（D）、左子树（L）和右子树（R）。因此若能一次遍历这三部分，则是遍历了整个二叉树。二叉树二叉树的遍历可得二叉树的如下几种次序的遍历：先左后右先右后左先序：DLRDRL中序：LDRRDL后序：LRDRLD一般情况采用先左后右的方法来遍历二叉树。二叉树先序遍历先序：DL

2、R中序遍历中序：LDR后序遍历后序：LRD先序遍历（DLR）先序遍历函数的遍历过程：若二叉树为空，则空操作；否则：1）先访问树T的根结点；2）先序遍历T的左子树；3）先序遍历T的右子树；二叉树ABFDGIEHCJ先序遍历1）A(AL)(AR)二叉树ABFDGIEHCJB(BL)(BR)C(CL)(CR)(NULL)(NULL)D(DL)(DR)E(EL)(ER)(NULL)(NULL)(NULL)ABCDEFGHIJ先序遍历算法（DLR）voidpreorder(bitree*root){bitree*p；p=rootif(T!=NULL){printf(

3、“%d”,p->data);preorder(p->lchild);preorder(p->rchild);}}二叉树先序遍历（DLR）则先序遍历的结果二叉树-+/*efb-acd-+a*b-cd/ef中序遍历（LDR）中序遍历函数的遍历过程：若二叉树为空，则空操作；否则：1）中序遍历T的左子树；2）访问T的根结点；3）中序遍历T的右子树；二叉树ABFDGIEHCJ中序遍历(TL)A(TR)二叉树ABFDGIEHCJTT1T11T12T121T2T21T22T212T221(T1L)B(T1R)(T11L)C(T11R)(NULL)(NULL)CCBB(T

4、12L)D(T12R)D(T121L)E(T121R)E(NULL)(NULL)E(NULL)DAAGHFJI中序遍历算法（LDR）voidinorder(bitree*root){bitree*p;p=root;if(p!=NULL){inorder(p->lchild);printf(“%d”,p->data);inorder(p->rchild);}}二叉树中序遍历（LDR）则中序遍历的结果：二叉树-+/*efb-acd后序遍历（LRD）后序遍历函数的遍历过程：若二叉树为空，则空操作；否则：1）后序遍历T的左子树；2）后序遍历T的右子树；3）访问T的

5、根结点；二叉树ABFDGIEHCJ后序遍历二叉树ABFDGIEHCJTT1T11T12T121T2T21T22T212T221(T1)(T2)A(T11)(T12)B(T111)(T112)C(NULL)(NULL)CC(T121)(T122)D(T1211)(T1212)E(NULL)(NULL)EE(NULL)DDBBHGJIFA后序遍历算法voidpostorder(bitree*root){bitree*p；p=rootif(p!=null){postorder(p->lchild);postorder(p->rchild);printf(“%d”

6、,p->data);}}二叉树则先序遍历的结果:二叉树-+/*efb-acd-+a*b-cd/ef则后序遍历的结果:则中序遍历的结果:a+b*c-d-e/fabcd-*+ef/-二叉树例已知某二叉树先序遍历的结果：abcdefghij，中序遍历的结果：cdbfeaihgj，此二叉树的结构？abcdefghijcdbfeaihgjabcdefgihj设计算法，按先序次序统计二叉树中叶子结点的个数voidCountLeaf(bitreeT,intcount){if(T){if((!T->lchild)&&(!T->rchild))count++;CountLe

7、af(T->lchild,count);CountLeaf(T->rchild,count);}}二叉树遍历算法的应用设计算法，按中序次序输出二叉树T中度为2的结点的值此问题的思考方法要求用中序遍历的思想来完成，但是和中序遍历不同的是要求仅输出度为2的结点的值，所以将中序遍历算法中的访问结点的操作改为条件输出结点的值即可。voidinorder(bitree*root){bitree*p=root;if(p!=NULL){inorder(p->lchild);if(p->lchild!=null&&p->rchild!=null)printf(“%d”,p

8、->data);inorder(p->rchild);}}二叉树遍