二叉树结点间最小距离解题报告.docVIP

二叉树结点间最小距离解题报告 概述 定义二叉树两个结点间的最小距离为这两个结点的最近公共祖先结点分别到这两个结点的路径长度之和，设计一种方法，找出给定二叉树中任意两个结点之间的最小距离 思想 计算两个结点的最小距离是二叉树运算的基本算法。其算法有很多种，关键是要找到最近的公共祖先结点，然后计算分别到两个结点之间的距离，将距离相加即为所求。如果使用三叉树，即每个结点中再设一个变量指向其父结点，此题将变得很简单，或者穿线二叉树也能使此题得到解决。如果不增设其它变量，可以用以下方法实现也较为容易：采用后续周游二叉树的方法求出根结点到每个待求结点的路径。将其分别存入队列中，然后分别出队，直到两个队列首的元素不相同，则上一个元素即为两者的最近公共祖先，然后求得距离。 算法 我采取的是一种基于递归的算法。基本思想是：设待求的结点为p和q，公共祖先有如下的性质：公共祖先本身及其左右子树中必含有p、q。于是从头结点开始依次访问它本身，左子树，右子树。其中含有p或q就让标记check加1。当访问结束后发现标记为2，则说明当前结点以下同时包含p和q，即当前结点是公共祖先。由于访问左右子树采取的是递归算法，因此可以求得最近公共结点。在有哪些信誉好的足球投注网站过程中同时记录该结点到p或q的距离（该结点及其左右子树不含有p或q、该结点本身为p或q距离为0）当当前结点被判断为最近公共结点时返回距离之和即为所求。p（q）只存在于结点，左子树，右子树中的一个中，因此不用考虑在有哪些信誉好的足球投注网站中到底是搜p还是搜q，只要搜到p，p就不可能在其他地方出现 采用递归的思想，使程序比较简洁易懂。 编程实现 int Distance(BinaryTreeNode* root,BinaryTreeNode* p,BinaryTreeNode* q,int len) { /*函数名称：int Distance(BinaryTreeNode* root,BinaryTreeNode* p,BinaryTreeNode* q,int len) 函数功能描述：友函数，返回p，q两个结点的最小距离 函数调用之前的预备条件：树存在 返回值：整型变量，记录p，q两个结点的距离 函数的输入参数：二叉树结点指针root，p，q，整型的引用len代表该结点到p或q的距离 函数的输出参数：整型变量 */ int len1,len2,length,check; //len1,len2：记录该结点到p或q的距离 //length：记录p，q的最小距离 //check：标记该结点与p，q的关系。 //check=2说明该结点与p，q均有关系（有关系定义为：其结点及左子树，右子树含有p或q） //check=1说明该结点与p或q有关系。check=0说明没关系 check=0; //初始化 if (p==q) //p==q return 0; //距离为0 if (root==NULL) //当前结点为空 { len=0; //标记为0 return 0; //距离为0 } if (root==p||root==q) //root为p或q check++; //check标记 length=Distance(root-leftchild(),p,q,len1);//递归有哪些信誉好的足球投注网站左子树 if (length!=0) //找到所求的祖先结点 return length; //立刻返回 if (len10) //左子树中找到p或q check++; //check标记 length=Distance(root-rightchild(),p,q,len2);//递归有哪些信誉好的足球投注网站右子树 if (length!=0) //找到所求的祖先结点 return length; //立刻返回 if (len20) //右子树中找到p或q check++; //check标记 if (check==2) //该结点为所求的祖先结点 return len1+len2; //返回两距离之和 if (check==1) //该结点和p或q中的一个有关系 { len=len1+len2+1; //距离加1 return 0; } len=0; //没关系,距离为0 return 0; } 时空分析：由于每个结点最多访问一次，时间复杂度为O(n)，空间上不用开辟两个线性表去存储路径，代价也很