线程内二叉树的插入或中序遍历有什么问题

Question

有人请帮我写这段代码，我已经为线程内二叉树编写了它，并制作了两个用于插入和中序遍历的函数。但是这个程序并没有按照我想的那样进行。插入 50,40,30,45 后依次遍历是 30->40->45->50 是正确的。但是在这个序列之后，当我试图在其中添加 42 时，顺序遍历是 42->45->50，这是不正确的。有人能告诉我这段代码哪里出错了吗？因为我已经尝试了很多调试它，根据我的逻辑，它不应该有任何错误。

#include <iostream>
#include <cstdlib>

using namespace std;

struct node{
int data;
bool lthread,rthread;
struct node *lchild,*rchild;
};

typedef struct node node;

node *in_succ(node *ptr){
if(ptr->rthread==true)
    return ptr->rchild;
ptr=ptr->rchild;
while(ptr->lthread==false)
    ptr=ptr->lchild;
return ptr;
}

node *in_pred(node *ptr){
if(ptr->lthread==true)
    return ptr->lchild;
ptr=ptr->rchild;
while(ptr->rthread==false)
    ptr=ptr->rchild;
return ptr;
}

node *ins(node *root,int n){
node *tmp;
tmp=(node*)malloc(sizeof(node));
tmp->data=n;
tmp->rchild=tmp->lchild=NULL;
tmp->rthread=tmp->lthread=true;
if(root==NULL)
    return tmp;
node *ptr=root;
node *par=NULL;
while(1){
    par=ptr;
    if(ptr->data==n){
        return root;
    }else if(ptr->data > n){
        ptr=ptr->lchild;
        if(par->lthread==true)
            break;
    }else{
        ptr=ptr->rchild;
        if(par->rthread==true)
            break;
    }
}
if(par->data>n){
    par->lthread=false;
    tmp->lchild=ptr;
    tmp->rchild=par;
    par->lchild=tmp;
}else{
    par->rthread=false;
    tmp->rchild=ptr;
    tmp->lchild=par;
    par->rchild=tmp;
}
}

void inorder(node *ptr){
if(ptr==NULL)
    return;
while(ptr->lthread==false)
    ptr=ptr->lchild;
while(ptr!=NULL){
    cout<<ptr->data<<" ";
    ptr=in_succ(ptr);
}
}

int main(){
int c,n;
node *root=NULL;
while(1){
    cout<<"1. Insert\n2. Delete\n3. Inorder\n4. Preorder\n5. Postorder\n6. Height\n0. Exit\n";
    cin>>c;
    switch(c){
        case 1:
            cin>>n;
            root=ins(root,n);
            break;
        case 3:
            inorder(root);
            cout<<endl;
            break;
        case 0:
            return 0;
    }
}
}

Answer 1

首先我在函数中发现了一个copy-past错误in_pred

ptr=ptr->rchild; -> ptr=ptr->lchild;

其次你在函数 ins

中忘记了 return root

#include <iostream>
#include <cstdlib>

using namespace std;

struct node{
    int data;
    bool lthread,rthread;
    struct node *lchild,*rchild;
};

typedef struct node node;

node *in_succ(node *ptr){
    if(ptr->rthread==true)
        return ptr->rchild;
    ptr=ptr->rchild;
    while(ptr->lthread==false)
        ptr=ptr->lchild;
    return ptr;
}

node *in_pred(node *ptr){
    if(ptr->lthread==true)
        return ptr->lchild;
    ptr=ptr->lchild;
    while(ptr->rthread==false)
        ptr=ptr->rchild;
    return ptr;
}

node *ins(node *root,int n){
    node *tmp;
    tmp=(node*)malloc(sizeof(node));
    tmp->data=n;
    tmp->rchild=tmp->lchild=NULL;
    tmp->rthread=tmp->lthread=true;
    if(root==NULL)
        return tmp;
    node *ptr=root;
    node *par=NULL;
    while(1){
        par=ptr;
        if(ptr->data==n){
            return root;
        }else if(ptr->data > n){
            ptr=ptr->lchild;
            if(par->lthread==true)
                break;
        }else{
            ptr=ptr->rchild;
            if(par->rthread==true)
                break;
        }
    }
    if(par->data>n){
        par->lthread=false;
        tmp->lchild=ptr;
        tmp->rchild=par;
        par->lchild=tmp;
    }else{
        par->rthread=false;
        tmp->rchild=ptr;
        tmp->lchild=par;
        par->rchild=tmp;
    }
    return root;
}

void inorder(node *ptr){
    if(ptr==NULL)
        return;
    while(ptr->lthread==false)
        ptr=ptr->lchild;
    while(ptr!=NULL){
        cout<<ptr->data<<" ";
        ptr=in_succ(ptr);
    }
}

int main()
{
    int c,n;
    node *root=NULL;
    while(1){
        cout<<"1. Insert\n2. Delete\n3. Inorder\n4. Preorder\n5. Postorder\n6. Height\n0. Exit\n";
        cin>>c;
        switch(c){
            case 1:
                cin>>n;
                root=ins(root,n);
                break;
            case 3:
                inorder(root);
                cout<<endl;
                break;
            case 0:
                return 0;
        }
    }
}

线程内二叉树的插入或中序遍历有什么问题

what's wrong in insertion or inorder traversal of in-threaded binary tree

c++

tree

data-structures