Как я могу случайно вернуть листовые узлы в BST?

Question

---

Я хочу получить один из конечных узлов в качестве выходных данных (только один из них). Но не один и тот же конечный узел каждый раз ... Я хочу получать разные конечные узлы каждый раз с помощью Функция "srand" ... Я пытался решить эту проблему с помощью массива, но не смог успешно. Затем я решил go с другим алгоритмом с помощью друга, который прокомментировал этот пост ...
Я генерирую случайное целое число, если это нечетное I go на левом потомке, наоборот ... Но получить тот же узел, что и выход, не может решить проблему ...

void LeafNodesRandomly(BST*p)
{
int i;
srand(time(NULL));
i=rand()%2;//Generating a random int for determining to go right or left of a current node
//printf("%d\t",i);

while(p->left !=NULL || p->right !=NULL)
{
    if(p->left==NULL && p->right!=NULL)//Just have a right child
    {
        p=p->right;
        if(p->left==NULL && p->right==NULL)//If the right child is a leaf node print and break
        {
            printf("%d\t",p->data);
            break;
        }
    }

    if(p->left!=NULL && p->right==NULL)//Just have a left child
    {
        p=p->left;
        if(p->left==NULL && p->right==NULL)//If the left child is a leaf node print and break
        {
            printf("%d\t",p->data);
            break;
        }
    }

    if(p->left!=NULL && p->right!=NULL)// The current node have two children
    {
        if(i==0)
        {
            p=p->left;
            if(p->left==NULL && p->right==NULL)// If the randomly generated int is "0" go left child and if the left child is a leaf node print and break
            {
                printf("%d\t",p->data);
                break;
            }
        }

        if(i==1)
        {
            p=p->right;
            if(p->left==NULL && p->right==NULL)// If the randomly generated int is "1" go right child and if the right child is a leaf node print and break
            {
                printf("%d\t",p->data);
                break;
            }
        }
    }



 /*if(i==0) // If you open this if and else block you can randomly reach some of other leafs!!!
    {
        i=i+1;
    }
    else
        i=i-1;
    } */
    }

}

---

Это моя основная функция:

У меня 13 или NULL в качестве выхода

#include <stdio.h>
#include <stdlib.h>
#include<time.h>
#include "bst.h"

int main()
{
    BST*root=NULL;

    root=AddNode(root,9);
    root=AddNode(root,11);
    root=AddNode(root,7);
    root=AddNode(root,13);
    root=AddNode(root,10);
    root=AddNode(root,5);
    root=AddNode(root,6);
    root=AddNode(root,8);

   LeafNodesRandomly(root);
}

Answer 1

Вы можете немного упростить свой код, используя информацию, которую вы уже знаете. Например, первые несколько строк вашего l oop:

while(p->left !=NULL || p->right !=NULL)
{
    if(p->left==NULL && p->right!=NULL)//Just have a right child
    {
        p=p->right;
        if(p->left==NULL && p->right==NULL)//If the right child is a leaf node print and break
        {
            printf("%d\t",p->data);
            break;
        }
    }

Когда вы вводите l oop, вы знаете, что, как правило, один из дочерних указателей равен нулю. Итак, вы знаете, что если p->left == NULL, p->right не может быть нулевым. Иначе ты бы никогда не вошел в тело l oop. И поскольку тело l oop не будет введено, если оба дочерних указателя равны нулю (т. Е. p указывает на конечный узел), нет никакой причины проверять конечный узел после назначения указателя. Условие while будет выходить из l oop соответствующим образом, p будет указывать на листовой узел, и вы можете распечатать данные.

Кроме того, вы можете увеличить изменчивость того листа узел, который вы получаете, выбирая новое случайное число всякий раз, когда вы добираетесь до узла, у которого есть два дочерних элемента.

Результирующий код намного короче и проще. Это уменьшает дублирующийся код и устраняет избыточные проверки логики c.

void LeafNodesRandomly(BST*p)
{
    // Seed the random number generator.
    srand(time(NULL));

    // Randomly select a leaf node
    while(p->left !=NULL || p->right !=NULL)
    {
        if(p->left==NULL)//Just have a right child
        {
            p=p->right;
        }
        else if(p->right==NULL)//Just have a left child
        {
            p=p->left;
        }
        else // The current node have two children
        {
            // Randomly select a child node.
            int i = rand()%2;
            if(i==0)
            {
                p=p->left;
            }
            else
            {
                p = p->right;
            }     
        }
    }
    // When you get here, p is pointing to a leaf node.
    printf("%d\t",p->data);
}

"Случайно выбрать дочерний узел" можно дополнительно сжать с помощью троичного оператора :

// Randomly select a child node.
p = (rand()%2) == 0 ? p->left : p->right;

(Да, придирки, я знаю, что == 0 на самом деле не нужен. Хотя это более понятно, особенно для менее опытных программистов. Нет необходимости говорить мне, что котенок умирает каждый раз, когда кто-то пишет == 0.)