让我们说我们正在处理密钥1-15.要获得常规BST的最差情况,您可以按升序或降序插入键,如下所示:
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
那么BST将基本上成为一个链表.
对于BST的最佳情况,您可以按以下顺序插入键,它们的排列方式使插入的下一个键是要插入的总范围的一半,因此第一个是15/2 = 8,然后是8/2 = 4等......
8,4,12,2,6,10,14,1,3,5,7,9,11,13,15
那么BST将是一个平衡良好的树,最佳高度为3.
对于红黑树的最佳情况也可以用BST的最佳情况构建.但是我们如何构建一棵红黑树的最坏情况呢？是否与BST的最坏情况相同？是否有特定的模式会产生最坏的情况？
我试图了解BST以及如何迭代地插入元素.我的节点结构实现如下:
struct Node{
Node *left;
Node *right;
T data; //template class
};
我的插入实现看起来像这样:
template<typename T>
bool BST<T>::Insert(const T value)
{
Node *newNode = new Node;
newNode -> data = value;
newNode -> left = NULL;
newNode -> right = NULL;
if(root == NULL) {root = newNode;} //If the BST is empty
else
{//The BST is not empty
Node *ptr = root; //points to the current Node
Node *ptr_parent; //points to the parent Node
while(ptr != NULL)
{
if((ptr -> data) …我已经读过std map是使用二叉搜索树数据结构实现的.
BST是一种顺序数据结构(类似于数组中的元素),它将元素存储在BST节点中并按顺序维护元素.例如,如果element小于node,则将其存储在节点的左侧,如果它大于node,则将其存储在节点的右侧.通过这种方法,我们实现了搜索,插入等各种操作的O(log n)复杂度.
但是,std map是一个关联容器.我们有一个键和值插入.它是否真的使用BST实现,如果是,如何实现？在BST,我们没有任何关键或价值.它是一种标准容器.
我有点困惑.请帮我澄清一下.它不影响我的工作,但我想更好地理解它们.谢谢你的帮助.
我如何在python中表示二叉搜索树？
所以我一直在阅读K&R C书,并在第140-141页的结构第6章中有一个问题,有代码看起来像这样(我拿出了一些更无关紧要的部分)
/*
the program loops through a tree looking for some word
if it finds the word itll incremenet the count by 1
if it doesnt itll add a new node
*/
struct node {
char *word;
int count;
struct node *left;
struct node *right;
}
main() {
struct node *root;
char word[1000];
root = NULL;
while(getword(word, MAXWORD) != EOF) /* getword just grabs 1 word at a time from a file of words */
if(isalpha(word[0])) /* isalpha checks …我正在尝试创建一个balance_bst(bstNode root)函数,但我正在努力实现.
我正在将该函数实现为模板函数,因为我的bstNode类是一个模板类.
这是(部分)我的代码:
template<class Item, class Key>
class bstNode{
public:
//Constructor
bstNode(const Item& init_data = Item(), const Key& init_key = Key(), bstNode<Item, Key>* l_child = NULL, bstNode<Item, Key>* r_child = NULL){
data_field = init_data;
key_field = init_key;
l_ptr = l_child;
r_ptr = r_child;
}
//Destructor
~bstNode(){
data_field = 0;
key_field = 0;
l_ptr = r_ptr = NULL;
}
//Basic Member Functions
bstNode<Item, Key>*& left( ) { return l_ptr; } //returns left child pointer by reference
bstNode<Item, Key>*& right( ) …给我一个字符串,即"CPHBDZ".通过(按此顺序)将字母插入BST,我将:
C
/ \
B P
/ \
H Z
/
D
如果我们将字符串的顺序更改为"CBPHDZ",我们将得到相同的树.我必须找到并列出提供相同BST的输入字符串的所有排列.我想出了如何计算这些排列的数量,但我无法弄清楚实际找到它们的任何算法.
假设有一个像下面那个需要存储在数组中的二叉树.
7
/ \
1 10
/\
9 11
我发现在数组中存储节点的公式从将根节点存储在位置0开始,然后对于索引处的每个节点i,其子节点都放在索引处(i*2)+1 and (i*2)+2.如果任一子array.length - 1节点的索引大于,那么该节点没有子节点.
所以我首先将7放在0位置,然后将其子1和10放在位置i2 + 1和i2 + 2位置为1和2:
|7|1|10| | | |
0 1 2 3 4 5
现在,我坚持使用没有任何孩子的节点1.我应该把它作为孩子们怎么样？
可以设置一些表示缺少节点的默认值,例如-1,如下所示:
|7|1|10|-1|-1|9|11|
0 1 2 3 4 5 6 7
编写T ComputeMedian() const在O(n)时间内计算树中值的函数的实现.假设树是BST但不一定是平衡的.回想一下n个数的中值定义如下:如果n是奇数,则中值是x,使得小于x的值的数量等于大于x的值的数量.如果n是偶数,则一加上小于x的值的数量等于大于x的值的数量.例如,给定数字8,7,2,5,9,中位数为7,因为有两个小于7的值和两个大于7的值.如果我们将3加到集合中,则中位数变为5.
这是二叉搜索树节点的类:
template <class T>
class BSTNode
{
public:
BSTNode(T& val, BSTNode* left, BSTNode* right);
~BSTNode();
T GetVal();
BSTNode* GetLeft();
BSTNode* GetRight();
private:
T val;
BSTNode* left;
BSTNode* right;
BSTNode* parent; //ONLY INSERT IS READY TO UPDATE THIS MEMBER DATA
int depth, height;
friend class BST<T>;
};
二进制搜索树类:
template <class T>
class BST
{
public:
BST();
~BST();
bool Search(T& val);
bool Search(T& val, BSTNode<T>* node);
void Insert(T& val);
bool DeleteNode(T& val);
void BFT(void);
void PreorderDFT(void);
void …我必须为树集编写一个模板.叶子的大小为0.当调用create_empty_set()时,它应该生成一个叶子,当你添加T数据时,叶子应该成为一个分支,它的值应该放在左边或右边.不允许重复.我在这里发布老师的指示:
So, you'll need three classes: a supertype SortedTree and two subtypes named Branch and Leaf.
LinkedList nodes carried little integers with them. For our set, we want to do something better: we wish
the set to be able to contain any kind of values. The way to accomplish this is to make use of templates:
a TreeSet<T> contains values of type T.
Where do the set's elements reside exactly? Each Branch node contains exactly one T, while the leaves …