二进制搜索树

我的教授发布了一些期末考试的复习题。我似乎无法找到答案。任何帮助将不胜感激！二进制搜索树

考虑n个节点的二叉树：
a。什么是叶节点的最小和最大数量？ b。高度的最小值和最大值是多少？
c。树使用了多少指针（不包括空指针，并假设我们没有保存存储父代的字段）？

* d。将n个节点插入（最初为空）的二叉搜索树时，最糟糕的关怀运行时间是多少？

来源

2011-05-24 ylhtravis

你应该去和教授交谈，看看他是否能够让你从这些问题中领悟到你的理解。也许他可以阐明他正在寻找的整体概念。 – 2011-05-24 17:31:57

你知道二叉树是什么吗？如果是这样，请尝试将一些数字检查是否可以找出答案，如n = 3,4等 – 2011-05-24 17:32:04

教授没有说“平衡二叉树”，最坏的二叉树退化为....布勒？ Bueler？任何人？ – 2011-05-24 17:33:34

叶子的最大数目是ceil（n/2）。最小数量为1
最大高度为n。最低限度是楼层（log_2（n））

来源

2011-05-24 17:44:39 arclight

尝试在纸上绘制各种树木，看看你得到了什么。请记住，二叉树被定义为一棵树，其中每个节点可以有0个（在这种情况下，它是一片叶子），1个或2个孩子。对于你的问题，你应该检查每个节点1个孩子非常不平衡的情况。

来源

2011-05-24 17:31:55

考虑：

如果你想最大限度地提高叶片数，你要尽可能少的内部节点（如果你正在试图尽量减少叶片数相反）。你怎么能做到这一点？

要获得最大高度的树，您将尽可能少地放置每个级别的节点。你怎么能这样做？相反，对于最小高度，您可以在每个级别放置多少个节点？

有多少种方法可以到达树的每个节点？因此，你需要多少指针？

来源

2011-05-24 17:33:41 William

我假设你要么在C或C++编码。

a。一个节点，如果结构是这样定义的： struct node {struct node * left，* right; }; 您可以观察到该结构可以具有0,1或2个叶子。所以，最大值是2，最小值是0叶。

b.Minimal高度为零，其中只包含根节点。请注意，根节点不计为1的高度。它有时也称为深度。下面是高度的算法：

int height(struct node *tree) 
    { 
    if (tree == NULL) return 0; 
    return 1 + max (height (tree->left), height (tree->right)); 
    }

℃。如果我采取这种方式，请原谅我，但是我假设我们是否将它映射在一张纸上，我们会试图找到我们将使用的“链接”的数量？在这种情况下，它仅仅是树中节点的数量-1作为根节点。在此页面http://forums.techarena.in/software-development/1147688.htm上找到的此算法可以帮助您：检查root是否为空，然后将左右节点作为参数传递给函数。

int countnodes(Node* root) 
{ 
    if (root == null || k<=0) 
    { 
     return 0; 
    } else { 
     return 1 + count(root.left,k-1) + count(root.right,k-1); 
    } 
} 
// remember to subtract one at the end. 
int totalnodes = countnodes(root) - 1;

d。最佳情况下的时间复杂度为O（nlogn），其中n是要插入的节点数。最糟糕的情况是O（n）。它是直接线性的。

如果你有任何其他问题只是谷歌它，有很多东西要知道二叉搜索树。但其中大部分只是递归，你可以在30秒内学习。

我希望这会有所帮助。祝您考试顺利！几个月前我有我的。;）

来源

2011-05-24 17:39:56

二进制搜索树

回答

相关问题