如何在 BST 中随机 return 叶节点？

Question

我想获得一个叶节点作为输出（只是其中一个）。但每次都不是相同的叶节点...我想在 [ 的帮助下每次都获得不同的叶节点=24=] 函数...我尝试使用数组解决这个问题，但无法解决 successfull.Then 我决定在评论此 post 的朋友的帮助下继续使用不同的算法。 ..
如果奇怪，我将生成一个随机整数，我继续向左 child ，反之亦然... 但是得到相同的节点作为一个输出并不能解决问题...

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

您可以通过使用您已知的信息来大大简化您的代码。例如，循环的前几行是：

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;
        }
    }

当你进入循环时，你知道，最多有一个子指针为空。所以你知道如果 p->left == NULL，p->right 不能为 null。否则你永远不会进入循环体。并且因为如果两个子指针都为空（即 p 指向叶节点），则不会进入循环体，因此没有理由在分配指针后检查叶节点。 while条件会适时退出循环，p会指向一个叶子节点，可以打印数据了。

此外，您可以通过在到达具有两个子节点的节点时选择一个新的随机数来增加获得哪个叶节点的可变性。

生成的代码更短更简单。它减少了重复代码并消除了冗余逻辑检查。

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);
}

可以使用ternary operator进一步压缩"randomly select a child node"：

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

（是的，吹毛求疵的人，我知道 == 0 实际上不是必需的。不过，它更清楚，尤其是对于经验不足的程序员。无需告诉我每次有人写时小猫都会死== 0.)

如何在 BST 中随机 return 叶节点？

How can I return leaf nodes randomly in a BST?

c

binary-tree

binary-search-tree

data-structures

我有 13 或 NULL 作为输出