给出 n 个点的一棵树,多次询问两点之间的最短距离。注意:边是双向的。 输入格式:
时间: 2024-06-03 19:07:12 浏览: 17
第一行包含整数 n,表示树的节点数。 接下来 n-1 行,每行包含三个整数 a, b, w,表示节点 a 和节点 b 之间有一条边,边权为 w。 接下来一行包含整数 q,表示询问次数。 接下来 q 行,每行包含两个整数 u, v,表示询问节点 u 和节点 v 之间的最短距离。 输出格式: 对于每个询问,输出一行表示询问的答案。
相关问题
编写一个代码:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表
/* 代码示例 */ struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
}; TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree==NULL)
return NULL; TreeNode* pLastNodeInList = NULL;
ConvertNode(pRootOfTree,&pLastNodeInList); //pLastNodeInList指向双向链表的尾结点
//我们需要返回头结点
TreeNode* pHeadOfList = pLastNodeInList;
while(pHeadOfList!=NULL && pHeadOfList->left!=NULL)
pHeadOfList = pHeadOfList->left; return pHeadOfList;
} void ConvertNode(TreeNode* pNode, TreeNode** pLastNodeInList)
{
if(pNode==NULL)
return; TreeNode* pCurrent = pNode; //处理左子树
if(pCurrent->left!=NULL)
ConvertNode(pCurrent->left,pLastNodeInList); //处理当前结点
pCurrent->left = *pLastNodeInList;
if(*pLastNodeInList!=NULL)
(*pLastNodeInList)->right = pCurrent; *pLastNodeInList = pCurrent; //处理右子树
if(pCurrent->right!=NULL)
ConvertNode(pCurrent->right,pLastNodeInList);
}
用c语言编写一个完整的代码:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表
#include <stdio.h>
#include <stdlib.h>/* 二叉搜索树结点定义 */
typedef struct BSTNode
{
int data;
struct BSTNode *lchild, *rchild;
} BSTNode;/* 双向链表结点定义 */
typedef struct DLLNode
{
int data;
struct DLLNode *prior, *next;
} DLLNode;/* 二叉搜索树与双向链表转换函数 */
DLLNode* BSTToDLL(BSTNode *root)
{
DLLNode *pFirst = NULL, *pLast = NULL;
if (root != NULL)
{
/* 将左子树转换为双向链表 */
if (root->lchild != NULL)
{
pFirst = BSTToDLL(root->lchild);
/* 左子树双向链表的最后一个结点为根结点 */
pLast = pFirst->prior;
/* 根结点指向左子树双向链表最后一个结点 */
root->lchild = pLast;
/* 左子树双向链表最后一个结点指向根结点 */
pLast->next = root;
}
else
{
/* 根结点为双向链表的第一个结点 */
pFirst = root;
}
/* 根结点指向其右子树 */
if (root->rchild != NULL)
{
/* 将右子树转换为双向链表 */
DLLNode *pRight = BSTToDLL(root->rchild);
/* 根结点指向右子树双向链表的第一个结点 */
root->rchild = pRight;
/* 右子树双向链表的第一个结点指向根结点 */
pRight->prior = root;
/* 双向链表的最后一个结点为右子树双向链表的最后一个结点 */
pLast = pRight->prior;
}
else
{
/* 根结点为双向链表的最后一个结点 */
pLast = root;
}
}
pFirst->prior = pLast;
pLast->next = pFirst;
return pFirst;
}int main()
{
return 0;
}答:我已经给出了一段用C语言编写的代码,它用于将一棵二叉搜索树转换为一个排序的双向链表。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)