2301_78364727 2023-12-07 16:35 采纳率: 90.9%
浏览 12
已结题

C++数据结构与算法

如何让先序中序后序的输出格式加上节点路径呢，具体实现如下要求

#include <iostream>
#include<stack>
#include <queue>
#define random(a,b) (rand()%(b-a)+a)//定义一个随机数生成的宏
using namespace std;

class BSTreeNode
{
    int data;
    BSTreeNode* left, * right;

public:
    BSTreeNode(int element) : data(element), left(NULL), right(NULL) {}
    int GetData() const
    {
        return data;
    }
    void SetData(const int& d)//设置节点数据
    {
        data = d;
    }
    BSTreeNode* GetLeft()//获取左节点
    {
        return left;
    }
    BSTreeNode* GetRight()
    {
        return right;
    }
    void SetLeft(BSTreeNode*& newLeft)//设置左节点
    {
        left = newLeft;
    }
    void SetRight(BSTreeNode*& newRight)
    {
        right = newRight;
    }
};


void bulidBST(BSTreeNode*& treeRoot, int arr[], int size)
{
    for (int i = 0; i < size; i++)//遍历
    {
        int tData = arr[i];//获取数组中的值
        BSTreeNode* newNode = new BSTreeNode(tData);//创建一个新的二叉数节点，节点值为数组中的元素值
        if (treeRoot == NULL)
        {
            treeRoot = newNode;
        }
        else//如果树不为空
        {
            BSTreeNode* pTemp = treeRoot;//创建一个新的临时指针指向根节点
            while (true)
            {
                if (tData < pTemp->GetData())//如果新节点数值小于当前节点
                {
                    if (pTemp->GetLeft() == NULL)//并且当前节点的左节点为空
                    {
                        pTemp->SetLeft(newNode);//把新节点插入为该节点的左节点
                        break;
                    }
                    else//如果当前节点的左节点不为空，就移动到左节点
                    {
                        pTemp = pTemp->GetLeft();
                    }
                }
                else//新节点不小于当前节点
                {
                    if (pTemp->GetRight() == NULL)//右节点为空
                    {
                        pTemp->SetRight(newNode);//新节点为当前节点的右节点
                        break;
                    }
                    else//如果右节点不为空
                    {
                        pTemp = pTemp->GetRight();//继续访问，移到右节点的
                    }
                }
            }
        }
    }
}
//遍历顺序：先序--根左右
void PreOrder(BSTreeNode* everyTreeNode)
{
   if (everyTreeNode)
    {
      cout << everyTreeNode->GetData() / 100 << ":" << everyTreeNode->GetData() % 100 << "\t";  //按时间格式输出 
      PreOrder(everyTreeNode->GetLeft());
      PreOrder(everyTreeNode->GetRight());
   }
}

//遍历顺序：中序--左根右
void InOder(BSTreeNode* everyTreeNode)
{
    if (everyTreeNode)//如果不为空
    {
        InOder(everyTreeNode->GetLeft());
        cout << everyTreeNode->GetData() / 100 << ":" << everyTreeNode->GetData() % 100 << "\t";  //按时间格式输出 RBN
        InOder(everyTreeNode->GetRight());
    }
}

//遍历顺序：后序--左右根
void PostOrder(BSTreeNode* everyTreeNode)
{
    if (everyTreeNode)
    {
        PostOrder(everyTreeNode->GetLeft());
        PostOrder(everyTreeNode->GetRight());
        cout << everyTreeNode->GetData() / 100 << ":" << everyTreeNode->GetData() % 100 << "\t";  //按时间格式输出 RBN
    }
}
void diedai1(BSTreeNode* treeNode)
{
    cout << "用迭代方式进行先序遍历。\n";
    stack<BSTreeNode*> S;//定义一个栈，用来储存S中的数据
    S.push(treeNode);//入栈
    while (!S.empty()) {//若栈不为空
        auto curNode = S.top();//获取栈顶部元素并赋值给curNode
        cout << curNode->GetData() / 100 << ":" << curNode->GetData() % 100 << "\t";//输出curNode的数据除以100的商和余数
        S.pop();//弹出顶部元素
        auto right = curNode->GetRight();//获取右节点
        if (right != NULL) {//right不为空
            S.push(right);//将他压入栈
        }
        auto left = curNode->GetLeft();
        if (left != NULL) {
            S.push(left);
        }
    }
}
void diedai2(BSTreeNode* treeNode)
{
    cout << "用迭代方式进行中序遍历。\n";
    stack<BSTreeNode*> S;
    while (1)
    {
        if (treeNode)
        {
            S.push(treeNode);//入栈
            treeNode = treeNode->GetLeft();//把treeNode左节点赋值给他
        }
        else if (!S.empty())//栈不为空
        {
            treeNode = S.top();//获取栈顶元素
            S.pop();//出栈
            cout << treeNode->GetData() / 100 << ":" << treeNode->GetData() % 100 << "\t";
            treeNode = treeNode->GetRight();
        }
        else break;//否则跳出循环
    }
}
//层次遍历：按照二叉树的层次高低遍历，优先遍历第一层的所有节点，然后遍历第二层，以此类推
void LevelPrint(BSTreeNode* treeNode)
{
    queue<BSTreeNode*> nodes;
    queue<string> paths;
    int levelLength = 0;
    if (treeNode)
    {
        nodes.push(treeNode);
        paths.push("");
        while (!nodes.empty())
        {
            auto curNode = nodes.front();
            auto curPath = paths.front();
            nodes.pop();
            paths.pop();
            if (curPath.length() > levelLength)
            {
                cout << endl;
                levelLength = curPath.length();
            }
            cout << curPath << " - " << curNode->GetData() / 100 << ":" << curNode->GetData() % 100 << "\t"; //随机航班数已考虑时间格式，取小时数直接除100求商即可，除60取商会导致时刻值与前面随机数不符 RBN
            auto left = curNode->GetLeft();
            if (left)
            {
                nodes.push(left);
                paths.push(curPath + "0");
            }
            auto right = curNode->GetRight();
            if (right)
            {
                nodes.push(right);
                paths.push(curPath + "1");
            }
        }
    }
}
//获取高度
int GetHeight(BSTreeNode* treeNode)
{
    if (!treeNode)
        return 0;
    int left = GetHeight(treeNode->GetLeft());
    int right = GetHeight(treeNode->GetRight());
    return left > right ? left + 1 : right + 1;
}
// 二叉搜索树的最近公共祖先
BSTreeNode* LowestCommonAncestor(BSTreeNode* root, BSTreeNode* p, BSTreeNode* q)
{
    //当两个子节点都小于根节点时，则在左侧查找
    if (root->GetData() > p->GetData() && root->GetData() > q->GetData())
    {
        return LowestCommonAncestor(root->GetLeft(), p, q);
    }
    //当两个子节点都大于根节点时，则在右子树查找
    if (root->GetData() < p->GetData() && root->GetData() < q->GetData())
    {
        return LowestCommonAncestor(root->GetRight(), p, q);
    }
    return root;
}
BSTreeNode* findNearestDeparture(BSTreeNode* root, int queryTime) {
    BSTreeNode* closestNode = nullptr; // 保存最近的节点
    int minTimeDiff = INT_MAX; // 初始化最小时间差为最大整数

    BSTreeNode* current = root; // 从根节点开始遍历
    while (current != nullptr) {
        int timeDiff = abs(current->GetData() - queryTime); // 计算当前节点数据与查询时间的差值
        if (timeDiff < minTimeDiff) { // 如果当前节点的时间差小于最小时间差
            minTimeDiff = timeDiff; // 更新最小时间差
            closestNode = current; // 更新最近的节点
        }
        if (current->GetData() > queryTime) { // 如果当前节点的数据大于查询时间
            current = current->GetLeft(); // 移动到左子节点
        }
        else if (current->GetData() < queryTime) { // 如果当前节点的数据小于查询时间
            current = current->GetRight(); // 移动到右子节点
        }
        else { // 如果当前节点的数据等于查询时间
            return current; // 直接返回当前节点
        }
    }
    return closestNode; // 返回最近的节点
}
int main()
{
    const int fly_num = 31;
    int array[fly_num] = { };  // 初始化都为0
    int random_values;
    srand((int)time(0));  // 产生随机种子
    for (int i = 0; i < fly_num; i++)
    {
        random_values = random(1, 1440);
        for (int j = 0; j < fly_num; j++)
        {
            //写入航班时刻前先做时间有效性处理,即：将后两位表示分钟数的值调整为0--60之间 
            random_values = (random_values / 100) * 100 + (random_values % 100) * 100 % 60;
            if (array[j] == random_values) {//去重
                i--;
                break;
            }
            if (array[j] == 0)
            {
                array[j] = random_values; // 赋值
                break;
            }
        }
    }

    cout << endl << "随机产生的 " << fly_num << " 架次航班信息如下：" << endl;
    for (int i = 0; i < fly_num; i++)
    {
        cout << array[i] << "(" << i << ")" << " ";
    }
    cout << endl;
    //声明树的根节点
    BSTreeNode* tree = NULL;
    bulidBST(tree, array, fly_num);//建立二叉搜索树，此后根结点已知

    cout << endl << "先序递归遍历二叉树" << endl;
    PreOrder(tree);
  //  PreOrderWithPaths(tree, ""); // 调用修改后的先序遍历函数，初始路径为空
    PreOrderWithPaths(tree, ""); // 调用修改后的先序遍历函数，初始路径为空

    cout << endl << "中序递归遍历二叉树" << endl;
    InOder(tree);
    cout << endl << "后序递归遍历二叉树" << endl;
    PostOrder(tree);
    // 按层次输出二叉搜索树的结果
    cout << endl << "按层次输出二叉搜索树的结果" << endl;
    LevelPrint(tree);
    cout << endl;
    diedai1(tree);
    cout << endl;
    diedai2(tree);
    cout << endl << "本次随机航班信息的二叉树的高度是: " << GetHeight(tree) << endl;

    int a = 1;
    while (a) {
        int c = 0, d = 0;
        cout << "请输入需要查询的时间，时和分" << endl;
        cin >> c;
        cin >> d;
        cout << "输入的时间为" << c << ":" << d << endl;
        int queryTime = 100 * c + d;

        BSTreeNode* nearestNode = findNearestDeparture(tree, queryTime);
        cout << "离查询时间最近的起飞时间节点是: "
            << nearestNode->GetData() / 100 << ":" << nearestNode->GetData() % 100 << endl;
        cout << "继续查询请输入1，退出查询请输入0" << endl;
        int b; cin >> b; a = b;
    }
    int t1, t2;
    int m = 1;
    while (m) {
        cout << endl << "请输入需要寻找共同祖先两个随机节点的秩: ";
        cin >> t1 >> t2;
        auto p = new BSTreeNode(array[t1]);
        auto q = new BSTreeNode(array[t2]);
        auto lca = LowestCommonAncestor(tree, p, q);
        int n = lca->GetData();
        cout << " 最近的共同祖先是: " << n / 100 << ":" << n % 100 << endl;
        cout << "继续查询请输入1，退出查询请输入0" << endl;
        int b; cin >> b; m = b;
    }
    cout << endl << "关于航班信息的二叉树创建/搜索，已经完成." << endl;
    system("pause");
    return 0; 
}

img

  • 写回答

8条回答 默认 最新

  • 小王子同学 2023-12-07 17:08
    关注

    在你的程序的基础上修改的，你运行一下看看，是不是你想要的结果。

    #include <iostream>
#include<stack>
#include <queue>
#define random(a,b) (rand()%(b-a)+a)//定义一个随机数生成的宏
using namespace std;
 
class BSTreeNode
{
    int data;
    BSTreeNode* left, * right;
 
public:
    BSTreeNode(int element) : data(element), left(NULL), right(NULL) {}
    int GetData() const
    {
        return data;
    }
    void SetData(const int& d)//设置节点数据
    {
        data = d;
    }
    BSTreeNode* GetLeft()//获取左节点
    {
        return left;
    }
    BSTreeNode* GetRight()
    {
        return right;
    }
    void SetLeft(BSTreeNode*& newLeft)//设置左节点
    {
        left = newLeft;
    }
    void SetRight(BSTreeNode*& newRight)
    {
        right = newRight;
    }
};
  
void bulidBST(BSTreeNode*& treeRoot, int arr[], int size)
{
    for (int i = 0; i < size; i++)//遍历
    {
        int tData = arr[i];//获取数组中的值
        BSTreeNode* newNode = new BSTreeNode(tData);//创建一个新的二叉数节点，节点值为数组中的元素值
        if (treeRoot == NULL)
        {
            treeRoot = newNode;
        }
        else//如果树不为空
        {
            BSTreeNode* pTemp = treeRoot;//创建一个新的临时指针指向根节点
            while (true)
            {
                if (tData < pTemp->GetData())//如果新节点数值小于当前节点
                {
                    if (pTemp->GetLeft() == NULL)//并且当前节点的左节点为空
                    {
                        pTemp->SetLeft(newNode);//把新节点插入为该节点的左节点
                        break;
                    }
                    else//如果当前节点的左节点不为空，就移动到左节点
                    {
                        pTemp = pTemp->GetLeft();
                    }
                }
                else//新节点不小于当前节点
                {
                    if (pTemp->GetRight() == NULL)//右节点为空
                    {
                        pTemp->SetRight(newNode);//新节点为当前节点的右节点
                        break;
                    }
                    else//如果右节点不为空
                    {
                        pTemp = pTemp->GetRight();//继续访问，移到右节点的
                    }
                }
            }
        }
    }
}

// 遍历顺序：先序--根左右
void PreOrder(BSTreeNode *everyTreeNode, string path)
{
    if (everyTreeNode)
    {
        cout << path << everyTreeNode->GetData() / 100 << ":" << everyTreeNode->GetData() % 100 << "\t";
        PreOrder(everyTreeNode->GetLeft(), path + "L");
        PreOrder(everyTreeNode->GetRight(), path + "R");
    }
}

// 遍历顺序：中序--左根右
void InOder(BSTreeNode *everyTreeNode, string path)
{
    if (everyTreeNode)
    {
        InOder(everyTreeNode->GetLeft(), path + "L");
        cout << path << everyTreeNode->GetData() / 100 << ":" << everyTreeNode->GetData() % 100 << "\t";
        InOder(everyTreeNode->GetRight(), path + "R");
    }
}

// 遍历顺序：后序--左右根
void PostOrder(BSTreeNode *everyTreeNode, string path)
{
    if (everyTreeNode)
    {
        PostOrder(everyTreeNode->GetLeft(), path + "L");
        PostOrder(everyTreeNode->GetRight(), path + "R");
        cout << path << everyTreeNode->GetData() / 100 << ":" << everyTreeNode->GetData() % 100 << "\t";
    }
}
void diedai1(BSTreeNode* treeNode)
{
    cout << "用迭代方式进行先序遍历。\n";
    stack<BSTreeNode*> S;//定义一个栈，用来储存S中的数据
    S.push(treeNode);//入栈
    while (!S.empty()) {//若栈不为空
        auto curNode = S.top();//获取栈顶部元素并赋值给curNode
        cout << curNode->GetData() / 100 << ":" << curNode->GetData() % 100 << "\t";//输出curNode的数据除以100的商和余数
        S.pop();//弹出顶部元素
        auto right = curNode->GetRight();//获取右节点
        if (right != NULL) {//right不为空
            S.push(right);//将他压入栈
        }
        auto left = curNode->GetLeft();
        if (left != NULL) {
            S.push(left);
        }
    }
}
void diedai2(BSTreeNode* treeNode)
{
    cout << "用迭代方式进行中序遍历。\n";
    stack<BSTreeNode*> S;
    while (1)
    {
        if (treeNode)
        {
            S.push(treeNode);//入栈
            treeNode = treeNode->GetLeft();//把treeNode左节点赋值给他
        }
        else if (!S.empty())//栈不为空
        {
            treeNode = S.top();//获取栈顶元素
            S.pop();//出栈
            cout << treeNode->GetData() / 100 << ":" << treeNode->GetData() % 100 << "\t";
            treeNode = treeNode->GetRight();
        }
        else break;//否则跳出循环
    }
}
//层次遍历：按照二叉树的层次高低遍历，优先遍历第一层的所有节点，然后遍历第二层，以此类推
void LevelPrint(BSTreeNode* treeNode)
{
    queue<BSTreeNode*> nodes;
    queue<string> paths;
    int levelLength = 0;
    if (treeNode)
    {
        nodes.push(treeNode);
        paths.push("");
        while (!nodes.empty())
        {
            auto curNode = nodes.front();
            auto curPath = paths.front();
            nodes.pop();
            paths.pop();
            if (curPath.length() > levelLength)
            {
                cout << endl;
                levelLength = curPath.length();
            }
            cout << curPath << " - " << curNode->GetData() / 100 << ":" << curNode->GetData() % 100 << "\t"; //随机航班数已考虑时间格式，取小时数直接除100求商即可，除60取商会导致时刻值与前面随机数不符 RBN
            auto left = curNode->GetLeft();
            if (left)
            {
                nodes.push(left);
                paths.push(curPath + "0");
            }
            auto right = curNode->GetRight();
            if (right)
            {
                nodes.push(right);
                paths.push(curPath + "1");
            }
        }
    }
}
//获取高度
int GetHeight(BSTreeNode* treeNode)
{
    if (!treeNode)
        return 0;
    int left = GetHeight(treeNode->GetLeft());
    int right = GetHeight(treeNode->GetRight());
    return left > right ? left + 1 : right + 1;
}
// 二叉搜索树的最近公共祖先
BSTreeNode* LowestCommonAncestor(BSTreeNode* root, BSTreeNode* p, BSTreeNode* q)
{
    //当两个子节点都小于根节点时，则在左侧查找
    if (root->GetData() > p->GetData() && root->GetData() > q->GetData())
    {
        return LowestCommonAncestor(root->GetLeft(), p, q);
    }
    //当两个子节点都大于根节点时，则在右子树查找
    if (root->GetData() < p->GetData() && root->GetData() < q->GetData())
    {
        return LowestCommonAncestor(root->GetRight(), p, q);
    }
    return root;
}
BSTreeNode* findNearestDeparture(BSTreeNode* root, int queryTime) {
    BSTreeNode* closestNode = nullptr; // 保存最近的节点
    int minTimeDiff = INT_MAX; // 初始化最小时间差为最大整数
 
    BSTreeNode* current = root; // 从根节点开始遍历
    while (current != nullptr) {
        int timeDiff = abs(current->GetData() - queryTime); // 计算当前节点数据与查询时间的差值
        if (timeDiff < minTimeDiff) { // 如果当前节点的时间差小于最小时间差
            minTimeDiff = timeDiff; // 更新最小时间差
            closestNode = current; // 更新最近的节点
        }
        if (current->GetData() > queryTime) { // 如果当前节点的数据大于查询时间
            current = current->GetLeft(); // 移动到左子节点
        }
        else if (current->GetData() < queryTime) { // 如果当前节点的数据小于查询时间
            current = current->GetRight(); // 移动到右子节点
        }
        else { // 如果当前节点的数据等于查询时间
            return current; // 直接返回当前节点
        }
    }
    return closestNode; // 返回最近的节点
}
int main()
{
    const int fly_num = 31;
    int array[fly_num] = { };  // 初始化都为0
    int random_values;
    srand((int)time(0));  // 产生随机种子
    for (int i = 0; i < fly_num; i++)
    {
        random_values = random(1, 1440);
        for (int j = 0; j < fly_num; j++)
        {
            //写入航班时刻前先做时间有效性处理,即：将后两位表示分钟数的值调整为0--60之间 
            random_values = (random_values / 100) * 100 + (random_values % 100) * 100 % 60;
            if (array[j] == random_values) {//去重
                i--;
                break;
            }
            if (array[j] == 0)
            {
                array[j] = random_values; // 赋值
                break;
            }
        }
    }
 
    cout << endl << "随机产生的 " << fly_num << " 架次航班信息如下：" << endl;
    for (int i = 0; i < fly_num; i++)
    {
        cout << array[i] << "(" << i << ")" << " ";
    }
    cout << endl;
    //声明树的根节点
    BSTreeNode* tree = NULL;
    bulidBST(tree, array, fly_num);//建立二叉搜索树，此后根结点已知
 
    cout << endl << "先序递归遍历二叉树" << endl;
    PreOrder(tree, "");
    cout << endl << "中序递归遍历二叉树" << endl;
    InOder(tree, "");
    cout << endl << "后序递归遍历二叉树" << endl;
    PostOrder(tree, "");
    // 按层次输出二叉搜索树的结果
    cout << endl << "按层次输出二叉搜索树的结果" << endl;
    LevelPrint(tree);
    cout << endl;
    diedai1(tree);
    cout << endl;
    diedai2(tree);
    cout << endl << "本次随机航班信息的二叉树的高度是: " << GetHeight(tree) << endl;
 
    int a = 1;
    while (a) {
        int c = 0, d = 0;
        cout << "请输入需要查询的时间，时和分" << endl;
        cin >> c;
        cin >> d;
        cout << "输入的时间为" << c << ":" << d << endl;
        int queryTime = 100 * c + d;
 
        BSTreeNode* nearestNode = findNearestDeparture(tree, queryTime);
        cout << "离查询时间最近的起飞时间节点是: "
            << nearestNode->GetData() / 100 << ":" << nearestNode->GetData() % 100 << endl;
        cout << "继续查询请输入1，退出查询请输入0" << endl;
        int b; cin >> b; a = b;
    }
    int t1, t2;
    int m = 1;
    while (m) {
        cout << endl << "请输入需要寻找共同祖先两个随机节点的秩: ";
        cin >> t1 >> t2;
        auto p = new BSTreeNode(array[t1]);
        auto q = new BSTreeNode(array[t2]);
        auto lca = LowestCommonAncestor(tree, p, q);
        int n = lca->GetData();
        cout << " 最近的共同祖先是: " << n / 100 << ":" << n % 100 << endl;
        cout << "继续查询请输入1，退出查询请输入0" << endl;
        int b; cin >> b; m = b;
    }
    cout << endl << "关于航班信息的二叉树创建/搜索，已经完成." << endl;
    system("pause");
    return 0; 
}
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(7条)

报告相同问题？

问题事件

  • 系统已结题 12月15日
  • 已采纳回答 12月7日
  • 修改了问题 12月7日
  • 修改了问题 12月7日
  • 展开全部

悬赏问题

  • ¥100 matlab2009 32位一直初始化
  • ¥15 Expected type 'str | PathLike[str]…… bytes' instead
  • ¥15 为什么在iis上部署网站，服务器可以访问，但是本地电脑访问不了
  • ¥15 三极管电路求解，已知电阻电压和三级关放大倍数
  • ¥15 ADS时域 连续相位观察方法
  • ¥15 Opencv配置出错
  • ¥15 关于模型导入UNITY的.FBX: Check external application preferences.警告。
  • ¥15 气象网格数据与卫星轨道数据如何匹配
  • ¥100 java ee ssm项目 悬赏，感兴趣直接联系我
  • ¥15 微软账户问题不小心注销了好像