数据结构(C++版)第5章_树和二叉树_1018.ppt

广度优先周游二叉树 template class T void BiTreeT::LeverOrder(BiNodeT *root) { LinkQueueBiNodeT * aQueue; BiNodeT* pointer=root; if(pointer) aQueue.EnQueue(pointer); 首先创建一个空队列；判断根节点是否为空，如果不空，根节点入队 while(!aQueue.Empty()) { pointer=aQueue.Front()-next-data; //取队列首结点 BiNodeT* q=aQueue.DeQueue(); coutpointer-dataendl; //Visit(pointer-value());//访问当前结点 if(pointer-lchild) //左子树进队列 aQueue.EnQueue(pointer-lchild); if(pointer-rchild) //右子树进队列 aQueue.EnQueue(pointer-rchild); }//end while } 队首出队（P），输出队首的值，将P的所有孩子（非0）入队 重复第二步的工作，直到队空 二叉树算法设计练习 遍历二叉树是二叉树各种操作的基础，遍历算法中对每个结点的访问操作可以是多种形式及多个操作，根据遍历算法的框架，适当修改访问操作的内容，可以派生出很多关于二叉树的应用算法。 void InOrder (BiNodeT *root) { if (root==NULL) return; else { InOrder(root-lchild); coutroot-data; InOrder(root-rchild); } } 二叉树算法设计练习 设计算法求二叉树的结点个数。 void Count(BiNode *root) //n为全局量并已初始化为0 { if (root) { Count(root-lchild); n+ +; Count(root-rchild); } } 统计叶子节点的数目 增加一个数据成员，leafcount, 初值为0 对树进行遍历。 如果一个节点是叶子，则将leafcount+1； 可以在前序、中序或后序的遍历过程中进行计算。 算法分析 从根节点出发 判断根节点是否是叶子节点，如果是，则叶子数+1 否则，在左子树中遍历，并统计叶子节点的数目，在右子树中进行遍历，并统计叶子节点的数目 templatetypename T inline void BiTreeT:: countleaf(BiTreeNodeT * root){ if (root) { if (root-lchild==0 root-rchild==0) leafcount=leafcount+1; else { countleaf(root-lchild); countleaf(root-rchild); } } return; } 左右子树的交换 将每个节点的左、右子树进行交换 可以在遍历过程中进行交换。 算法分析 从根出发开始操作 如果要操作的节点是叶子或是空值，则不进行任何操作； 如果要操作的节点不是叶子节点，则交换左右儿子 对左子树进行处理 对右子树进行处理 左右子树进行交换 templatetypename T void BinarytreeT::jiaohuan(binarytreenodeT * root){ binarytreenodeT * temp; if (root==0) return ; else { if (root-lchild==0 root-rchild==0) return ; else{ temp=root-rchild; root-rchild=root-lchild; root-lchild=temp; jiaohuan(root-lchild); jiaohuan(root-rchild); } } } * * * * * * * * * 层序遍历 二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。 5.1 二叉树的逻辑结构 层序遍历序列：A B C D E F G A B C D