老师儿180 2022-12-18 20:49 采纳率: 50%
浏览 29
已结题

数据结构 树的祖先应该怎么找 怎么处理带空格的输入流

img


这个问题是用层序遍历建树,然后求公共祖先,但题目是英语的qwq。
我已经大概把框架写出来,但是不知道为什么,出现了错误,而且我一直不太理解如何将带空格的输入流变成我们想要的输入形式。
希望可以帮忙看看,补齐代码,必有感谢。


```c++
#include <vector>
#include <iostream>
#include <string>
#include<queue>
#include<sstream>
#include <string>
#include <iomanip>
#include <utility>
#include <iostream>
#include <stdexcept>
#include<algorithm>
using namespace std;

typedef int type;
typedef struct treeNode {
    type data;
    treeNode* left;
    treeNode* right;
}treeNode;
treeNode* creatBinTree(vector<int> arr) {
    queue<treeNode*> q;

    if (arr.empty()) {
        return nullptr;
    }

    treeNode* head = new treeNode; //创建头节点
    head->data = arr[0];  //存放数组首元素
    q.push(head); //入队

    treeNode* bt;
    int i = 1;
    while (!q.empty()) {
        bt = q.front();  //取出头节点,准备给它安排左右孩子
        q.pop(); //头节点出队,每一次新的循环,都让头出队

                 //先弄左孩子
                 //i只要不超过数组的有效长度,就有左孩子
        if (i < arr.size()) {
            if (arr[i] == 0)
            {
                bt->left = nullptr;
                i++;
            }
            else
            {
                bt->left = new treeNode;
                bt->left->data = arr[i];
                q.push(bt->left);  //左孩子入队
                i++; //数组后移
            }
        }
        else {
            bt->left = nullptr;
        }

        //再弄右孩子
        if (i < arr.size()) {
            if (arr[i] == 0)
            {
                bt->right = nullptr;
                i++;
            }
            else {

                bt->right = new treeNode;
                bt->right->data = arr[i];
                q.push(bt->right);  //右孩子入队
                i++;  //数组后移
            }
        }
        else {
            bt->right = nullptr;
        }
    }
    return head;  //最后队列为空就出while,返回头节点
}

treeNode* anc(treeNode* root, int p, int q) 
 {        if (root->data == q || root->data == p || root== nullptr) {return root};        
    treeNode* left = anc(root->left, p, q);        
 treeNode* right = anc(root->right, p, q); 
 if (left != nullptr && right != nullptr) 
 {return root; }       
 if (left ==nullptr) 
 {    return right;   }    
  return left;    
  
  }

int main() {
    vector<int> a;
    a.push_back(20);
    a.push_back(5);
    a.push_back(15);
    a.push_back(4);
    a.push_back(9);
    a.push_back(13);
    a.push_back(17);
    a.push_back(2);
    a.push_back(0);
    a.push_back(8);
    a.push_back(0);
    a.push_back(12);
    a.push_back(14);
    a.push_back(16);
    a.push_back(18);
    a.push_back(1);
    a.push_back(3);
    treeNode* tou = creatBinTree(a);
    cout<<tou->left->right->left->data;
    cout<<anc(tou, 2, 18)->data;
}



```

  • 写回答

2条回答 默认 最新

  • yy64ll826 2022-12-19 09:15
    关注

    树如何找共同祖先_树的基础知识
    https://blog.csdn.net/weixin_28756413/article/details/112150741
    C++处理输入流中以逗号或者空格分隔的数据
    https://blog.csdn.net/qq_34525916/article/details/121379665
    可以借鉴下

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 12月27日
  • 已采纳回答 12月19日
  • 创建了问题 12月18日

悬赏问题

  • ¥15 需要数据库运行的图片
  • ¥15 如何获取vue-video-editor?
  • ¥100 vs2019 mfc程序如何实现64*64/48*48大小的真彩色工具栏
  • ¥15 全志v3s耳机音频输出口怎么外接功放
  • ¥15 华为ensp使用基本ACL限制公司网络访问
  • ¥15 帮我做下照片上的PLC题
  • ¥15 labview2022 使用modbus报缺少依赖?
  • ¥15 谷歌地图是不是不开通结算功能,api会使用不了哦
  • ¥15 unity腾讯云对象存储机型适配
  • ¥15 求全国交通咨询模拟代码,要求如下,可以完全在dev c++运行