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

二叉树 二叉树的遍历 在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对中的结点逐一进行某种处理，这就提出了遍历二叉树（traversing binary tree）的问题，即按照某种有哪些信誉好的足球投注网站路径寻访树中的每一个结点，使得每个结点均被访问一次，而且仅被访问一次。 二叉树是由3个基本单元组成：根节点（D）、左子树（L）和右子树（R）。因此若能一次遍历这三部分，则是遍历了整个二叉树。 二叉树 二叉树的遍历 可得二叉树的如下几种次序的遍历： 先左后右 先右后左 先序： DLR DRL 中序： LDR RDL 后序： LRD RLD 一般情况采用先左后右的方法来遍历二叉树。 二叉树 先序遍历（DLR） 先序遍历函数的遍历过程： 若二叉树为空，则空操作；否则： 1）先访问树T的根结点； 2）先序遍历T的左子树； 3）先序遍历T的右子树； 二叉树 先序遍历 1） A (AL) (AR) 二叉树 先序遍历算法（DLR） void preorder(bitree *root) { bitree *p； p=root if(T!=NULL) { printf(“%d”,p-data); preorder(p-lchild); preorder(p-rchild); } } 二叉树 先序遍历（DLR） 则先序遍历的结果 二叉树 中序遍历（LDR） 中序遍历函数的遍历过程： 若二叉树为空，则空操作；否则： 1）中序遍历T的左子树； 2）访问T的根结点； 3）中序遍历T的右子树； 二叉树 中序遍历 ( TL ) A ( TR ) 二叉树 中序遍历算法（LDR） void inorder(bitree *root) { bitree *p; p=root; if(p!=NULL) { inorder(p-lchild); printf(“%d”,p-data); inorder(p-rchild); } } 二叉树 中序遍历（LDR） 则中序遍历的结果： 二叉树 后序遍历（LRD） 后序遍历函数的遍历过程： 若二叉树为空，则空操作；否则： 1）后序遍历T的左子树； 2）后序遍历T的右子树； 3）访问T的根结点； 二叉树 后序遍历 二叉树 后序遍历算法 void postorder(bitree *root) { bitree *p； p=root if(p!=null) {postorder(p-lchild); postorder(p-rchild); printf(“%d”,p-data); } } 二叉树 则先序遍历的结果: 二叉树 二叉树遍历算法的应用 设计算法，按先序次序统计二叉树中叶子结点的个数 void CountLeaf(bitree T,int count) { if(T) { if((!T-lchild)(!T-rchild)) count++; CountLeaf(T-lchild,count); CountLeaf(T-rchild,count); } } 二叉树遍历