最短路径

二叉树的遍历，Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。通常可以在任何图中使用，包括有向图、带赋权边的图。

floyd-warshall算法

介绍

单独一条边的路径也不一定是最佳路径。 从任意一条单边路径开始。所有两点之间的距离是边的权的和，(如果两点之间没有边相连, 则为无穷大）。 从第一个顶点开始，依次将每个顶点作为媒介 k，然后对于每一对顶点 u 和 v ，查看其是否存在一条经过 k 的，距离比已知路径更短的路径，如果存在则更新它。

算法分析

用邻接矩阵map[][]存储有向图，用dist[i][j]表示i到j的最短路径。设G的顶点为V={1,2,3…n}，对于任意一对顶点i,j属于V，假设i到j有路径且中间节点皆属于集合{1,2,3…k}，P是其中的一条最小权值路径。就是i到j的最短路径P所通过的中间顶点最大不超过k。

实现

#根据最短路径矩阵，输出两点之间对应的路线  
def getRoutes(a,path,start,end): #最短路径矩阵  
    rts = [] #存放路线  
    rts.append(start)  
    i = start-1  
    while path[i][end-1] != -1:  
        rts.append(path[i][end-1]+1)  
        i = path[i][end-1]  
    rts.append(end)  
    dst=a[start-1][end-1]
    return rts,dst

#求最短路径Floyd:地图tmp,lenn为点数，得到i->j(从i点到j的最短路径)的地图A,
def Floyd(map_s,lenn):  
    A = map_s  
    #存放到某点必须经过的路径点,生成lenn的二维数组，开始全部为-1，代表不能通过
    path = [[-1 for i in range(lenn)] for j in range(lenn)]
    for k in xrange(lenn):      #不断试图往两点i,j之间添加新的点k，更新最短距离
        for i in xrange(lenn):  
            for j in xrange(lenn):  
                if A[i][j] > A[i][k] + A[k][j]:  
                    A[i][j] = A[i][k] + A[k][j]  
                    path[i][j] = k       
    return A,path       #返回A二维数组是每个点到其它点的最短路径, path是最短路径的路径，-1表示不通       

def main():
	#将各个点变成
	INF=10000
	map1 = [ 
	[0   ,2   ,10  ,5   ,3   ,INF  ],   
    [INF ,0   ,12  ,INF ,INF ,10   ],  
    [INF ,INF ,0   ,INF ,7   ,INF  ],  
    [2   ,INF ,INF ,0   ,2   ,INF  ],  
    [4   ,INF ,INF ,1   ,0   ,INF  ],  
    [10   ,INF ,1   ,INF ,2   ,0   ]
	]  
	map2,path = Floyd(map1,6)  
	print 'path:%s'%(path)
	print 'A:%s'%(map2) 
	rts,dst = getRoutes(map2,path,6,2)  
	print rts
	print dst
main()

二叉树

已知先序和中序

求后序c++

#include <iostream>    
#include <fstream>    
#include <string>    
using namespace std;
struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char  elem;
};

void BinaryTreeFromOrderings(char* inorder, char* preorder, int length)
{
    if (length == 0)
    {
        //cout<<"invalid length";  
        return;
    }
    TreeNode* node = new TreeNode;//Noice that [new] should be written out.  
    node->elem = *preorder;
    int rootIndex = 0;
    for (; rootIndex < length; rootIndex++)
    {
        if (inorder[rootIndex] == *preorder)
            break;
    }
    //Left  
    BinaryTreeFromOrderings(inorder, preorder + 1, rootIndex);
    //Right  
    BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));
    cout << node->elem;
    return;
}

int main(int argc, char* argv[])
{
    printf("You know the preorder and the middle order, can you find out the post order!\n");
    char* pr = "f09e54c1bad2x38mvyg7wzlsuhkijnop";
    char* mid = "905e4c1fax328mdyvg7wbsuhklijznop";
    int len = strlen(mid);
    BinaryTreeFromOrderings(mid, pr, len);
    printf("\n");
    return 0;
}

已知中序、后序遍历

求前序

#include <iostream>  
#include <fstream>  
#include <string>  

struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char  elem;
};


TreeNode* BinaryTreeFromOrderings(char* inorder, char* aftorder, int length)
{
    if (length == 0)
    {
        return NULL;
    }
    TreeNode* node = new TreeNode;//Noice that [new] should be written out.  
    node->elem = *(aftorder + length - 1);
    std::cout << node->elem ;
    int rootIndex = 0;
    for (; rootIndex < length; rootIndex++)//a variation of the loop  
    {
        if (inorder[rootIndex] == *(aftorder + length - 1))
            break;
    }
    node->left = BinaryTreeFromOrderings(inorder, aftorder, rootIndex);
    node->right = BinaryTreeFromOrderings(inorder + rootIndex + 1, aftorder + rootIndex, length - (rootIndex + 1));

    return node;
}

int main(int argc, char** argv)
{
    char* mid = "AEFDHZMG";
    char* fin = "ADEFGHMZ";
    int  len = strlen(fin);
    BinaryTreeFromOrderings(fin, mid, len);
    printf("\n");
    return 0;
}

已知先序和后序

求中序，答案不唯一