层序二叉树存在漏结点现象，如何解决？

Question

（C++）在测试二叉树和前序遍历的过程中，发现在有些情况下存在漏结点现象
例如：输入：
10
1 2 3 null a 4 b 5 c 6 （CSDN平台不允许重复null,第一个后面的用 a b c代替）
输出的前序遍历结果为：
1 2 3 4
后面的被遗漏了，请问代码
应该怎么改才不会漏掉节点呢？

#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>

using namespace std;

//二叉树节点定义
typedef struct BiTNode//二叉树的结点数据结构
{
    int data;
    BiTNode* lchild, * rchild;
};

//按层序输入，结点为空时，输入'#'
BiTNode* CreateBiTree(int* a, int n, int start)//*a为data，n为数组长度，start为根节点
{
    if (a[start] == '#') return NULL;//当根节点为空，即空树

    BiTNode* root = new BiTNode;//新建一个根结点
    root->data = a[start];//给根结点root的成员变量data,lchild,rchild赋初值
    root->lchild = NULL;
    root->rchild = NULL;

    int lnode = 2 * start + 1;//用根节点确定左节点的位置
    int rnode = 2 * start + 2;//用根节点确定右节点的位置

    if (lnode > n - 1) root->lchild = NULL;
    else root->lchild = CreateBiTree(a, n, lnode);//lnode替换start，为左子树的根节点

    if (rnode > n - 1) root->rchild = NULL;
    else root->rchild = CreateBiTree(a, n, rnode);//rnode替换start，为右子树的根节点

    return root;
}

//先序遍历函数（递归完成）
void PreOrderTraverse(BiTNode* T)
{
    if (T) {
        cout << T->data << " ";
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}




int main()
{
    int N = 0;
    cin >> N;



    for (int i = 0; i < N; i++)
    {

        int len = 0;
        cin >> len;

        int nums[100];
        cin.ignore();

        string input;
        getline(cin, input); // 读取一行数据
        stringstream ss(input); // 将字符串转化为数据流
        string temp;
        int index = 0;
        while (ss >> temp) // 从数据流中读取一个字符串
        {
            if (temp == "null") // 如果为null，转化为99999
                nums[index++] = '#';
            else
                nums[index++] = stoi(temp); // 将字符串转化为数字
        }

        // 输出结果
        /*for (int i = 0; i < index; i++)
            cout << nums[i] << " ";
        cout << endl;*/

        PreOrderTraverse(CreateBiTree(nums, len, 0));


        cout << endl;
    }
        return 0;
    
}

Answer 1

在构建二叉树时，由于节点为空的情况较多，可能会被遗漏掉。这是由于，当节点为空时，递归函数并不会进入下一层，所以无法遍历到这些结点。

为了解决这个问题，可以修改一下先序遍历函数，使得当节点为空时，也能进入下一层进行遍历。例如，可以将先序遍历函数修改为如下形式：

void PreOrderTraverse(BiTNode* T)
{
if (T) {
cout << T->data << " ";
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
else {
cout << "null ";
PreOrderTraverse(NULL);
PreOrderTraverse(NULL);
}
}

这样，当遍历到空节点时，就会输出"null"，并继续递归遍历空节点的左右子节点。

希望这能帮到你！望及时采纳。