如何在BST中随机返回叶节点？

Question

---

我想获得一个叶子节点作为输出（只是其中之一）。但是每次都不会有相同的叶子节点...我想借助“ srand”函数每次获得一个不同的叶子节点...我尝试使用数组解决此问题，但未能成功。然后，我决定在一位对此帖子发表评论的朋友的帮助下继续使用其他算法...我正在生成一个随机整数，如果是奇数，我继续与左孩子，反之亦然...但是获得与输出相同的节点不能解决问题...

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.
p = (rand()%2) == 0 ? p->left : p->right;

（（是的，nitpickers，我知道== 0实际上不是必需的。但是，更清楚的是，尤其是对于经验不足的程序员。无需告诉我，每当有人写== 0时小猫都会死掉。）