有关风水的网站建设栏目/设计一个公司网站多少钱

图（中）
一.树之习题选讲（Tree Traversals Again）
非递归的中序遍历
在这道题目中，我们可以学到树的前序遍历，中序遍历，以及后序遍历。
此图的中序遍历

递归的思路是，找出根结点，然后递归的求左子树，递归的求右子树。
我们主要讲用非递归的方法：我们先把根结点1入栈，然后将其子结点2入栈，再将2子节点3入栈，3没有子结点了，然后出栈，回到了2，然后出栈，将4入栈，然后出栈，出栈，将5入栈，将6入栈，然后出栈，出栈。
不难发现，其实我们push的顺序就是先序遍历，pop的顺序为中序遍历。
看看这个例子，假设pre为先序，in为中序，post为后序。
6
push 1
push 2
push 3
pop
pop
push 4
pop
pop
push 5
push 6
pop
pop
push的顺序为先序那么，pre 1 2 3 4 5 6
pop的顺序为中序那么，in 3 2 4 1 6 5
那么我们该如何找出后序呢，其实不难。
我们首先找出根结点，由先序pre得根结点为 1，那么在中序in 中，根结点1把in序列分成左右两半，那么左边就是根结点1的左子树，右边就是根结点1的右子树，那么我们很容易知道后序post的最后一个元素为 1，也就是 pre 1，然后我们可以知道pre的前三个元素存的是什么，后两个元素是什么，根据上述一样的方法可以求出，在先序pre中，左半边的根结点一定是2，然后左子结点为3，右子结点为4，不能求出pre 3 4 2 1，同理，求出右半边，得pre 3 4 2 6 5 1。其实递归就行了。

void slove(int preL,int inL,int postL,int n)//preL为先序最左边的数，inL为中序最左边的数，postL为后序最左边的数，n为长度
{if(n==0)//为零直接返回{return ;}if(n==1){post[postL]=pre[preL];return;}int root=pre[preL];//根结点为先序第一个post[postL+n-1]=root;//把根结点赋给后序最后一个位置for(i=0;i<n;i++){if(in[inL+i]==root)//找出中序中根结点的位置break;}int L=i;int R=n-L-i;slove(PreL+1,inL,postL,L);//递归左子树slove(preL+L+1,inL+L+1,postL+L,R);//递归右子树
}

二.树之习题选讲（完全二叉树搜索树Complete Binary Search Tree）
什么是二叉搜索树？
就是在树中根结点大于左边的子结点，小于右边的子结点。
什么是完全二叉树？
就是我们从上到下从左至右给一个二叉树编号，一个数都不少。不能中间空隔着一个数。
然后我们的完全二叉搜索树就是两者的性质融合起来。
那么我们是用数组还是链表来表示这棵完全二叉搜索树呢？
我们需要的操作是填入数字（也就是某种遍历）和层序输出。在这道题目中，因为考虑到是完全二叉树，所以树不会向左或者向右倾斜，因此，数组更好一些，而且数组层序遍历更为方便。而链表要考虑入队操作相对复杂一些，而且指针比较危险。因此无论从安全性和方便性，在此道题目中，数组显得更为优秀。
核心算法：由于我们知道序列的大小，而且搜索树的左边小于右边，因此，我们可以将序列从小到大排序，然后根据完全二叉树的性质，我们知道序列的大小，就可以求出左子树的结点数，和右子树的结点树，然后我们将排序后的树分成来两半，中间的那个数其实就是我们的根结点所对应的值了，同样的，我们通过递归的方法来求出其左半边和右半边。其实我们很容易发现，这其实是一种典型先序遍历的应用。

void solve(int ALeft,int ARight,int TRoot)//ALeft代表A数组的最左边，ARight代表A数组的最右边，TRoot代表当前根结点的值
{//初始为slove(0,N-1,0)n=ARight-ALeft+1;if(n==0)//当遍历完时，退出{return ;}int L=GetLeftLength(n);//计算左子树结点个数T[TRoot]=A[ALeft+L];int LeftTRoot=Troot+2+1;int RightTRoot=LeftTRoot+1;slove(ALeft,ALeft+L+1,LeftTRoot);//递归左子树slove(ALeft+L+1,ARight,RightTRoot);//递归右子树
}

特别注意，A数组是已经排好序的数组，T数组为答案数组。
三.最短路问题
最短路问题的抽象
在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径。
这条路径就是两点之间的最短路径（Shortest Path）
第一个顶点为源点（source）
最后一个顶点为终点（Destination）
问题分类
单源最短路径问题：从某个固定圆点出发，求其到所有其他顶点的最短路径
无权图
有权图
多源最短路径问题：求任意两顶点间的最短路径。
无权图的单源最短路问题
按照递增的顺序找出各个顶点的最短路
核心算法：我们定义两个数组，一个叫dist[]数组，存的是起点到某个终点的最短距离，一个叫path[]数组，存的是经过该顶点的上一个顶点的位置，我们的图用的是邻接表，我们将path[]，dist[]两个数组先全部初始化为-1，这样方便我们查询，然后将起点的dist[]数组的值改为0，很简单，因为起点到起点的距离不就是零嘛，然后我们通过查询邻接点到起点的距离，用一个判断队列是否为空的循环包裹起来，访问起点的第一个邻接点，将距离存在dist[]数组中，又因为起点是该点的上一个顶点，也就是经过的点，然后将该点的下标存在path[]，将第一个邻接点存入队列中，继续访问第二邻接点，当访问完之后，我们出队一个元素，按照以上的方法，如此循环，就能求得完整的dist数组和path数组，当我们查询的时候，问到哪儿的最短路，就去找该下标所对应的path值，然后往回找，同时将经过的dist值累加起来，直到path的值为-1，然后停止，该累加的值，就是起点到该点的最短路径。说起来可能很模糊，举个例子吧！

void Unweighted(Vertex S){Emqueue(S,Q);while(!IsEmpty(Q)){V=Dequeue(Q);for(i=V->next;V!=NULL;V=V->next){if（dist[i]==-1){dist[i]=dist[V+1];path[i]=V;Enqueue(i,Q);}}}
}

四.有权图的单元最短路算法
Dijkstra算法：
令S={源点S+已经确定了最短路径的顶点Vi}
对任一未收录的顶点V，定义dist[V]为S到V的最短路径长度，但该路径仅经过S中的顶点。即路径{S->(Vi属于S）->V}的最小长度。
若路径是按照递增得到顺序生成的，则
真正的最短路必须只经过S中的顶点；
每次从未收录的顶点中选一个dist最小的收录（贪心）；
增加一个V进入S，可能影响另外一个W的dist值；
dist[W]=min(dist[W],dist[V]+<V,W>的权重)
核心思想：我们还有一个数组名为collected[]数组，意思是表示收录与为收录，先将每个顶点dist值设为无穷大，path值为-1，collected值为0，表示还没有开始搜索。然后我们选一个源点，将其dist值改为0，因为自己到自己的值总是0,然后将与源点的所以邻接点，将dist[]改为对应的权重，path值就为源点下标，这是初始化。然后我们用一个循环，从未收录的顶点中找出一个dist值最小的顶点，找到之后，就将其collected值变为1，表示已经收录了，然后我们对于这个顶点的邻接点进行以下操作：
用一个if条件来判断是否被收录了，没有被收入则执行以下：将上一个点的dist值加权重与自己本身的dist值进行比较，去两者中的最小值，不断更新。如此循环即可。
核心代码：

void Dijkstra(Vertex s){while(1){v=minUncollected(s);//minUncollected函数是求s的邻接点中dist的最小值的下标if(v==NULL){//如果这样的点不存在，则直接break掉。break; }collected[V]=1;//表示已经被录入for(w=v->next;w!=NULL;w=w->next){//循环其邻接点，找寻最短路径if(collected[w]==0){if(dist[v]+E<v,w><dist[w]]){//找到最短路，更新dist[w]=dist[v]+E<v,w>;path[w]=v;}}}}
}

五.多源最短路算法
当我们学过单源最短路算法以后，其实可以很容易的知道多源最短路怎么求了。
方法一：直接将单源最短路算法调用V遍。
T=O(VVV+EV),时间复杂度高
方法二：Floyd算法
T=O(VV*V)，既然方法二比方法一要好，那么我们就来看看方法二的算法原理吧！
Floyd算法：
D(K)[i][j]=路径{i–>{l<=k}–>j}的最小长度；
D(0),D(1),…D(V-1)[i][j]即给出了i到j的真正最短距离。
最初的D(-1)是什么？：其实就把定义为邻接矩阵就行了，如果两者没有边，就把它定义为无穷大。
当D(k-1)已经完成，递推到D(k)时：
或者k属于最短路径{i–>{l<=k}–>j},则D(k)==D(k-1)
或者k属于最短路径{i–>{l<=k}–>j},则该路径必定由两条最短路径组成：D(k)[i][j]=D(k-1)[i][k]+D(k-1)[k][j]
核心算法：初始化，用一个二维数组也就是邻接矩阵记录该全边的权值path[i][j]为-1，然后用三层循环进行搜索出，每当i->k->j的路径小于i->j的值的时候，更新值，然后记录一下K就行了。
核心代码：

void Floyd(){//初始化for(int i=0;i<n;i++){for(int j=0;j<n;j++){D[i][j]=G[i][j];path[i][j]=-1;}}for(int k=0;k<n;++){for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(D[i][k]+D[k][j]<D[i][j]){//不断更新D[i][j]=D[i][k]+D[k][j];path[i][j]=K;}}}}
}