我正在尝试用单词构建二叉搜索树。然而,当我使用上面的代码时,我只能访问我的根,根的左、右子项似乎为空。
法典:
void NgramTree::insert(std::string str)
{
if(root==NULL)
{
root=new node(str,1);
}
else{
// checkAndIncrease method checks if its already in tree and counts, this method works perfect too. I ve been sure , its going in if block below after first insertion.
bool have=checkAndIncease(root,str);
if(have==false)
{
node* cur=root;
while(cur!=NULL)
{
// first method returns 1 if first arg is smaller,0 if equal 1 if bigger and works perfectly!
int upper=first(cur->data,str,0);
if(upper==1)
{
cur=cur->right;
}
if(upper==0)
{
std::cout<< " hata var";
}
if(upper==-1)
{
cur=cur->left;
std::cout<< "cur=cur->left;\n";
}
}
/// WHEN I RUN PROGRAM, I CAN BE SURE CUR== ROOT->LEFT
if(cur==(root->left))
{
std::cout<< "cur==root->left DOGRUU\n";
}
// Although, cur==root->left, if i use cur here
// They arent connected, both childerens of root seems NULL
// If i do root->left=new Node(str,1) instead of cur just for try
// It works only for one insertion..
cur=new node(str,1);
}
}
}
这是自定义二进制树代码示例。
// TreeNode.h
#include <stdlib.h>
#include <string>
#ifndef __TREE_NODE_H__
#define __TREE_NODE_H__
class CTreeNode
{
public:
CTreeNode(std::string str);
~CTreeNode();
////////////////////////////////////////////////////////////
const CTreeNode* GetLeft() const;
const CTreeNode* GetRight() const;
std::string GetString() const;
void SetValue(std::string str);
private:
CTreeNode* m_pLeft;
CTreeNode* m_pRight;
std::string m_Str;
};
#endif
CTreeNode实现
#include "TreeNode.h"
CTreeNode::CTreeNode(int iValue, std::string str)
{
m_pLeft = NULL;
m_pRight = NULL;
m_Str = str;
}
CTreeNode::~CTreeNode()
{
delete m_pLeft;
m_pLeft = NULL;
delete m_pRight;
m_pRight = NULL;
}
const CTreeNode* CTreeNode::GetLeft() const
{
return m_pLeft;
}
const CTreeNode* CTreeNode::GetRight() const
{
return m_pRight;
}
std::string CTreeNode::GetString() const
{
return m_Str;
}
void CTreeNode::SetValue(std::string str)
{
if (str.compare(m_Str) < 0)
{
if (m_pLeft != NULL)
m_pLeft->SetValue(str);
else
m_pLeft = new CTreeNode(str);
}
else
{
if (m_pRight != NULL)
m_pRight->SetValue(str);
else
m_pRight = new CTreeNode(str);
}
}
CBinaryTree 声明
// BinaryTree.h
#include "TreeNode.h"
#include <iostream>
#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__
class CBinaryTree
{
public:
CBinaryTree();
~CBinaryTree();
////////////////////////////////////////////////////////////
void Add(std::string str);
void PrintLR() const;
private:
void PrintLR(const CTreeNode* pNode) const;
CTreeNode* m_pRoot;
};
#endif /* __BINARY_TREE_H__ */
CBinaryTree实现
#include "BinaryTree.h"
using std::endl;
using std::cout;
CBinaryTree::CBinaryTree()
{
m_pRoot = NULL;
}
CBinaryTree::~CBinaryTree()
{
delete m_pRoot;
m_pRoot = NULL;
}
void CBinaryTree::Add(std::string str)
{
if (m_pRoot != NULL)
m_pRoot->SetValue(str);
else
m_pRoot = new CTreeNode(str);
}
void CBinaryTree::PrintLR() const
{
PrintLR(m_pRoot);
}
void CBinaryTree::PrintLR(const CTreeNode* pNode) const
{
if (pNode == NULL)
return;
PrintLR(pNode->GetLeft());
cout << pNode->GetString() << endl;
PrintLR(pNode->GetRight());
}
在你的情况下
void NgramTree::insert(std::string str)
{
if(root==NULL)
{
root=new node(str,1);
}
else{
// checkAndIncrease method checks if its already in tree and counts, this method works perfect too. I ve been sure , its going in if block below after first insertion.
bool have=checkAndIncease(root,str);
if(have==false)
{
node* cur=root;
while(cur!=NULL)
{
// first method returns 1 if first arg is smaller,0 if equal 1 if bigger and works perfectly!
int upper=first(cur->data,str,0);
if(upper==1)
{
if (cur->right == NULL)
{
cur->right = new node(str, 1)
break;
}
cur=cur->right;
}
else if(upper==0)
{
std::cout<< " hata var";
}
else
{
if (cur->left == NULL)
{
cur->left = new node(str, 1)
break;
}
cur=cur->left;
}
}
}
}
主要内容:什么是二叉排序树?,使用二叉排序树查找关键字,二叉排序树中插入关键字,二叉排序树中删除关键字,总结前几节介绍的都是有关静态 查找表的相关知识,从本节开始介绍另外一种查找表—— 动态查找表。 动态查找表中做查找操作时,若查找成功可以对其进行删除;如果查找失败,即表中无该关键字,可以将该关键字插入到表中。 动态查找表的表示方式有多种,本节介绍一种使用树结构表示动态查找表的实现方法—— 二叉排序树(又称为 “二叉查找树”)。 什么是二叉排序树? 二叉排序树要么是空 二叉树,要么具有如下特点:
我正在努力实现二叉搜索树。完成实现所需的功能之一是重新平衡功能。 根据规范,该功能的工作方式如下: rebalance() 方法应创建一个平衡树,从而将偏度降低为零。平衡树是指在整个树中,左子树和右子树的大小相差不超过1(即,每个子树也是平衡的)。 为了平衡树,rebalance() 方法应反复将根值移动到较小的子树,并将最小/最大值从较大的子树移动到根,直到树平衡。然后,它应该以递归方式平衡两个
我们已经看到了两种不同的方法来获取集合中的键值对。回想一下,这些集合实现了 map 抽象数据类型。我们讨论的 map ADT 的两个实现是在列表和哈希表上的二分搜索。在本节中,我们将研究二叉查找树作为从键映射到值的另一种方法。 在这种情况下,我们对树中项的确切位置不感兴趣,但我们有兴趣使用二叉树结构来提供高效的搜索。
我正在做一个AlgoExpert挑战,我已经花时间自己解决它,看了关于它的视频讲座,我觉得我有一个很好的理解,但我在递归和树遍历方面的技能现在很低(这就是我工作的原因)。 这是提示 编写一个函数,该函数接受二进制搜索树(BST)和目标整数值,并返回与BST中包含的目标值最接近的值。每个BST节点都有一个整数值、一个左子节点和一个右子节点。其子节点本身是有效的BST节点或无/空 目标:12 这是我目
请帮我修复我的代码。 对于方法,字符串的格式应为 空树应返回一组空括号。 对于我正在进行的Junit测试: 这是我的代码: 谢谢!!
我有一个<code>BinarySearchTree</code>,里面有Instance bankaccount的对象,这是我创建的一个类,所以基本上它只是一个二进制搜索树,我编写了一个方法,它将获取树并对其进行平衡,因为某些原因,它在平衡之前准确地打印出树: 现在,首先我有方法,它接受一个列表和一个并通过按顺序检查树数据来创建树数据的,因此它是一个排序数组。然后使用另一种方法以平衡的方式创建树