在二进制非STL树中打印出有2个孩子的父母的问题。

Question

我有一个非stl树。我在使用函数 void preorder. 它应该打印出所有有2个 "孩子 "的元素，并打印出有2个孩子的父母总数。我不能让它打印出父母的数量。到目前为止，其他一切都很好。你知道如何使它更好吗？

 #include <iostream>
    using namespace std;

    struct elem 
    { 
        int key; 
        elem *left;  
        elem *right;
    }*root=NULL;  

    void add(int n, elem *&t);
    int del(int k);
    elem * &search(int k);
    void show(elem *t, int h);
    void printnode(int n, int h);
    void preorder(elem *t);


    int main()
    {

            int ch,num, ammount,i;
        do
        {   cout<<"\n\t \t Menu";
            cout<<"\n \t 1.Add elements";
            cout<<"\n \t 2.Search an element";
            cout<<"\n \t 3.Print the tree";
            cout<<"\n \t 4.Delete an element";
            cout<<"\n \t 5. Find elements with two children";
            cout<<"\n \t 6.Exit";
        do
        {   cout<<"\n \t Your choice is:\t";
            cin>>ch;
        }
        while (ch<1||ch>6);
        switch(ch)
    {

        case 1: 
            cout<<"\n \t How many elements do you want to add?\t";
            cin>>ammount;
            for(i=0; i<ammount; i++)
            {
                cout<<"\n\t Input list elements:\t";
                cin>>num;
                add(num, root);
            }
        break;


        case 2: 
            int b;
            cout<<"\n \tWhat element do you want to find?";
            cin>>b;
            &search(b);
            break;


        case 3:
            cout<<"\n \n \n";
            show(root, 0);  
            break;

        case 4: 
            cout<<"\n \t Which element do you want to delete?";
            int a;
            cin>>a;
             &search(a);
             break;

        case 5:
            preorder(root);
            break;
    }

    }while(ch!=6); 
    }

    void add(int n, elem *&t)
    {   
        if (t==NULL)    {   
            t=new elem;
            t->key=n;  
            t->left=t->right=NULL;        
        }  else     
        {   
            if (t->key<n)  
                add(n,t->right);   
            else    
            {
                if (t->key>n)       
                    add(n,t->left); 
            }  
        } 
    } 

    elem * &search(int k) 
    {  
        elem **p=&root; 
        for (;;)   

        {   
            if (*p==NULL) 
                return *p; 
            if (k<(*p)->key) 
                p=&(*p)->left;    
            else     
                if (k>(*p)->key) p=&(*p)->right;      
                else 
                    return *p;  
        } 
    } 

    int del(int k) 
    {  
        elem * &p=search(k), *p0=p, **qq, *q;
        if (p==NULL) 
            return 0; 

        if ((p->right==NULL))  
        {
            p=p->left; delete p0;
        } 
        else       
            if(p->left==NULL)    
            { 
                p=p->right; delete p0;
            }    
            else    
            {
                qq=&p->left;     
                while ((*qq)->right)    
                    qq=&(*qq)->right;  
                p->key=(*qq)->key;   
                q=*qq;    
                *qq=q->left;    
                delete q;   
            }   
            return 1;  
    } 

    void printnode(int n, int h) 
    { 
        for(int i=0;i<h;i++)   
            cout<<"\t";
        cout<<n<<endl;
    } 

    void show(elem *t, int h) 
    {  
        if(t)  
        {   
            show(t->right,h+1);    
            printnode(t->key,h);    
            show(t->left,h+1);   
        } 
    }

    void preorder(elem *t)
    {
        int count_total=0;
     if (t)
     {
        int count=0;

        if (t->left!=NULL&&t->right!=NULL) 
        {
            int child_key=0;
            count++;
            cout<<"\n \t Element is:\n\t"<<t->key;

            if(count>count_total)
            {
                count_total=count;
            }
        } 
     preorder(t->left); 
     preorder(t->right);
     }
     cout<<"\n\tTotal number of elements:"<<count_total;
    }

Answer 1

我们可以让函数返回在子树中出现的由节点 root. 假设 left_count 和 right_count 是出现在左子树和右子树中的此类节点的数量。root 分别返回 left_count + right_count 如果 root 没有2个孩子，但如果有，那么我们就返回 left_count + right_count + 1.

int preorder(elem *root)
{
    if (root == nullptr)
        return 0;

    int left_count, right_count;
    left_count = preorder(root->left);
    right_count = preorder(root->right);

    bool is_valid = false;
    if (root->left != nullptr && root->right != nullptr)
    {
        cout << root->key << endl;
        is_valid = true;
    }

    return left_count + right_count + (is_valid ? 1 : 0);
}