《算法论文(二叉树排序)》由会员分享，可在线阅读，更多相关《算法论文(二叉树排序)（9页珍藏版）》请在金锄头文库上搜索。
1、二叉树后序非递归遍历多核程序设计 摘要： 遍历二叉树是二叉树一种重要的运算，遍历的方法也有很多种，这里我主要采用的遍历方式是二叉树后序非递归遍历，在遍历的过程中先遍历左子树在遍历右子树，最后遍历根结点。与单核环境下串行的速度相比，在多核中并行运行程序所花费的时间有所缩减，速度也有所提高。所以在我完成的串行程序中添加了循环并行化指导语句，实现了程序的并行化。这样有利于提高二叉树后序非递归遍历的运行速度，达到让程序运行花费更短时间的目的。除此之外，还提高了CPU的利用率，缩短了循环所需要的时间。关键词多核，循环并行化，OpenMP，二叉树后序遍历，加速比。引言： OpenMP的规范由SGI发起，它
2、是一种面向共享内存以及分布式共享内存的多处理器多线程并行编程语言。OpenMP是一种共享内存并行的应用程序编程接口。所有的处理器都被连接到一个共享的内存单元上，处理器在访问内存的时候使用的是相同的内存编址空间。由于内存是共享的，因此，某一处理器写入内存的数据会立刻被其它处理器访问到。OpenMP的重要性在于，它能够为编写多线程程序提供一种简单的方法，而无需程序员进行复杂的线程创建、同步、负载平衡和销毁工作。循环并行化是使用OpenMP并行化程序的最重要部分。由于大量科学计算程序将很大一部分的的时间用在处理循环计算上，而对于循环并行化处理来说，这一部分的应用非常关键，因此循环并行化在OpenMP
3、应用程序中是一个相对独立且非常重要的组成部分。本文中通过实现二叉树非递归后序遍历的循环并行化，与并行之前的串行程序进行比较，分别求出串并行时间，并得出加速比。理论分析后序遍历是二叉树遍历的一种。后序遍历指在访问根结点、遍历左子树与遍历右子树三者中，首先遍历左子树，然后遍历右子树，最后遍历访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。后序遍历有递归算法和非递归算法两种。而在本文中我采用的是二叉树后序的非递归方法。后序遍历过程如下图所示：二实验运行环境及硬件系统：Windows7环境：visual studio 2008三.实验原理和方法1.串行算法的设计：（1
4、）二叉树后序遍历的思想： 从根节点开始，沿左子树一直走到没有左孩子的节点为止，并将所经节点的地址第一次进栈；当找到没有左孩子的节点时，此节点的左子树已访问完毕；从栈顶退出该节点，判断该节点是否为第一次进栈，如是，再将所经节点的地址第二次进栈，并沿该节点的右子树一直走到没有右孩子的节点为止，如否，则访问该节点；此时，该节点的左、右子树都已完全遍历，且令指针p = NULL;（2）建立二叉树typedef int datatype; /链式存储二叉树typedef struct node datatype data; struct node *lchild,*rchild;bitree;bitre
5、e *Qmaxsize,*root,*t;int n;bitree *buildtree() /建二叉树，函数返回指向根的指针datatype aN;bitree *s;n=0; root=NULL;int i; for(i=0;iN;i+) ai=rand(); /随机生成结点 for(i=0;idata=ai; s-lchild=NULL; s-rchild=NULL; n+; Qn=s; if(n=1) root=s; else if(s&Qn/2) if(n%2=0) Qn/2-lchild=s; else Qn/2-rchild=s; return root; /返回根指针 （3）构
6、造非递归后序遍历函数void fpostorder() /非递归函数bitree *amaxsize,*p; int flag,top;top=-1;flag=0; do while(t) top+;atop=t;t=t-lchild; /找到树的左孩子 p=NULL;flag=1; while(top!=-1&flag) t=atop; if(t-rchild=p) printf(%d ,t-data);top-;p=t; /输出标记结点 else t=t-rchild;flag=0; while(top!=-1); （4）建立主函数，实现遍历结果输出等过程，int _tmain()root
7、=buildtree(); printf(gen jie dian wei:); printf(%d ,root-data); /打印根结点 printf(n); t=root; printf(bian li jie guo wei:); printf(n); fpostorder(); printf(n); getchar();return 0;（5）在main函数中添加时间函数clock（）begin=(double)clock()/(double)CLK_TCK; end=(double)clock()/(double)CLK_TCK;int _tmain() double begin,
8、end;root=buildtree(); printf(gen jie dian wei:); printf(%d ,root-data); /打印根结点 printf(n); t=root; printf(bian li jie guo wei:); printf(n); begin=(double)clock()/(double)CLK_TCK; /开始计时 fpostorder(); printf(n); end=(double)clock()/(double)CLK_TCK; /结束计时printf(%f,end-begin);getchar();return 0;2.并行算法的设计
9、：并行原理：一些可同时执行的诸进程的集合，这些进程互相作用和协调动作从而达到给定问题的求解。使用消息传递并行程序设计是用户必须通过显式地发送和接收消息来实现处理机间的数据交换。在这种并行编程中，每个并行进程均有自己独立的地址空间，相互之间访问不能直接进行，必须通过显示地消息传递来实现。先设置环境变量，通过环境变量OMP_NUM_THREADS值控制运行的线程的数目，通过新的编译器选项 /openmp来支持OpenMP程序的编译和链接，在串行的for循环遍历的语句前加上并行指导语句#pragma omp paraller for使其并行化，就形成并行程序。串行代码中的遍历没有for循环，#pra
10、gma omp paraller for不能使while并行化，所以要把while变成for循环。创建二叉树时，用for(i=1;iN;i+)循环将所创建的二叉树的各个结点的地址存放在了指针数组Qi中，这个数组是按照完全二叉树的顺序存储结构存储各节点的地址，所以在遍历函数中完全可以用for(i=1;iN;i+)做为外循环控制结点的个数，然后使一个线程遍历1到N/2个结点，另一个线程遍历N/2+1到N-1个结点。每个结点的地址应该到Q里取，每个访问完的结点使其Qi=NULL并行算法如下：#include stdafx.h#include#include#include#include#inclu
11、de windows.h#include time.h#include iostream#define NULL 0#define maxsize 102400#define N 1000typedef int datatype; /链式存储二叉树typedef struct node datatype data; struct node *lchild,*rchild;bitree;bitree *Qmaxsize,*root,*t;int n;bitree *buildtree() /建二叉树，函数返回指向根的指针datatype aN;bitree *s;n=0; root=NULL;i
12、nt i; for(i=0;iN;i+) ai=rand(); /随机生成结点 for(i=0;idata=ai; s-lchild=NULL; s-rchild=NULL; n+; Qn=s; if(n=1) root=s; else if(s&Qn/2) if(n%2=0) Qn/2-lchild=s; else Qn/2-rchild=s; return root; /返回根指针 void fpostorder() /并行非递归bitree *amaxsize,*p; int flag,top,i;top=-1;flag=0; t=root; omp_set_num_threads(2); /并行执行的进程数#pragma omp parallel for /循环并行化指导语句 for(i=1;ilchild; p=NULL;flag=1; while(top!=-1&flag) t=atop; if(t-rchild=p) printf(%d ,t-data
