我是一个Python人.学习C语言,我一直在尝试在C中实现二进制搜索树.我写下了代码,我已经尝试了几个小时但是,无法按预期获得输出.请帮忙!
请指正.
#include<stdlib.h>
#include<stdio.h>
typedef int ElementType;
typedef struct TreeNode {
ElementType element;
struct TreeNode *left, *right;
} TreeNode;
TreeNode *createTree(){
//Create the root of tree
TreeNode *tempNode;
tempNode = malloc(sizeof(TreeNode));
tempNode->element = 0;
tempNode->left = NULL;
tempNode->right = NULL;
return tempNode;
}
TreeNode *createNode(ElementType X){
//Create a new leaf node and return the pointer
TreeNode *tempNode;
tempNode = malloc(sizeof(TreeNode));
tempNode->element = X;
tempNode->left = NULL;
tempNode->right = NULL;
return tempNode;
}
TreeNode *insertElement(TreeNode *node, ElementType X){
//insert element to …我如何在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的输入字符串的所有排列.我想出了如何计算这些排列的数量,但我无法弄清楚实际找到它们的任何算法.
我有一个家庭作业，内容如下（不要发火/担心，我不是要你做我的家庭作业）：
编写一个程序，通过使用二叉搜索树的快速排序方法对一组数字进行排序。推荐的实现是使用递归算法。
这是什么意思？以下是我迄今为止的解释，正如我在下面解释的那样，我认为两者都有缺陷：
A. 从用户那里获取一组数字（整数或其他）。使用数组上的普通快速排序算法对它们进行快速排序。然后将东西放入二叉搜索树中，使数组的中间元素成为根，等等，完成。
B. 从用户那里获取数字，使用二叉搜索树的标准属性，将它们直接一一放入树中。树已经“排序”了，一切都很好——做得很好。
这就是我困惑的原因。选项“A”完成了作业要求的一切，除了它并没有真正使用二叉树，因为它是在二叉树上的家庭作业，所以它在最后一分钟抛出它。这让我认为预期的练习不可能是“A”，因为主要主题不是快速排序，而是二叉树。
但是选项“B”也好不到哪里去——它根本不使用快速排序！所以，我很困惑。
以下是我的问题：
如果解释是选项'A'，就这么说，我没有问题，谢谢你的时间，再见。
如果解释是选项'B'，为什么在二叉树中插入值的排序方法与快速排序相同？他们不似乎天生就比一个事实，即他们都（在表格我已经学会为止）使用递归分而治之的策略和划分他们的投入在两个类似的其他。
如果解释是别的……我该怎么办？
关于螺纹二进制搜索树的解释(如果你知道它们,请跳过它):
我们知道在具有n个节点的二叉搜索树中,有n + 1个左右指针包含null.为了使用包含null的内存,我们按如下方式更改二叉树 -
对于树中的每个节点z:
如果left [z] = NULL,我们在left [z]中输入tree-predecessor(z)的值(即指向包含前任键的节点的指针),
如果right [z] = NULL,我们在右[z]中输入tree-successor(z)的值(同样,这是指向包含后继键的节点的指针).
像这样的树称为线程二进制搜索树,新链接称为线程.
我的问题是: 螺纹二进制搜索树的主要优点是什么(与"常规"二叉搜索树相比).在网上快速搜索告诉我,迭代地实现有序遍历有助于,而不是递归地实现.
这是唯一的区别吗？还有其他方法可以使用线程吗？
这是如此有意义的优势吗？如果是这样,为什么？递归遍历也花费O(n)时间,所以..
非常感谢你.
algorithm binary-tree asymptotic-complexity binary-search-tree data-structures
假设有一个像下面那个需要存储在数组中的二叉树.
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 …