时间戳

首页 > 解决方案 > 在二叉非 STL 树中打印具有 2 个孩子的父母的问题

c++ - 在二叉非 STL 树中打印具有 2 个孩子的父母的问题

问题描述

我有一棵非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, amount, 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>>amount;

            for(i = 0; i < amount; 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;
    }

标签： c++binary-tree

解决方案

我们可以让函数返回从节点发出的子树中出现的节点总数（有 2 个子节点）root。假设left_count和right_count是分别出现在 的左右子树中的此类节点的数量，则如果没有 2个子节点root，则返回，但如果有，则返回。left_count + right_countrootleft_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);
}

推荐阅读