找到BST中每个级别的最大元素.
[1] In O(n) time and O(1) space
[2] In O(logn) time and O(n) space
编辑:@Imposter发布的解决方案适用于[1]这是[1]的解决方案
private int level = 0;
private int VisitedLevels = -1;
public void findLargestByLevel(AvlNode root)
{
if(root == null) return;
else
{
if(level > VisitedLevels)
{
System.out.println(root.data + " @ Level = " + level);
VisitedLevels++;
}
level++;
findLargestByLevel(root.right);
findLargestByLevel(root.left);
level--;
}
}
但我仍然无法找到[2]的解决方案
我想到的方法:如果我们预处理树并将其展平,就像树的序列化一样,
100
50 200
20 75
#L0, 100, #L1, 50, 200, #L2, 20, 75, #L3
#L是级别的标记:
然后我们可以轻松地回答O(1)时间内级别最高和最低的查询.此外,如果树被修改,我们可以在LogN时间内执行序列化数据的插入和删除.请为[2]推荐某人,虽然在我看来zit看起来无法实现[2],但我想听听别人的建议
我正在研究一种寻找阳极母体的方法.我从根开始,然后沿着叶子向下,只要它们不是空的而不是孩子的节点.
下面是我的代码,它有点凌乱,因为我试图测试它看到什么出错.
我拥有的树是
10
/ \
2 20
\ / \
3 18 22
/
21
传入的x是20,所以10是父级,但是当我运行它时,22作为父级出现.while循环似乎不起作用,是不是我写的方式？
public Node<E> findParent(E x)
{
Node<E> node = root;
System.out.println("node is " + node.getData() + " before the search");
System.out.println("The value of x is " + x);
System.out.println("The value of node.getRight is " + node.getRight().getData());
boolean test = !node.getRight().getData().equals(x);
System.out.println("does nodes data equal x " + test);
while(((node!=null) && (node.getLeft()!=null) && (!node.getLeft().getData().equals(x))) ||
((node != null) && (node.getRight()!=null) && (!node.getRight().getData().equals(x))))
{ System.out.println("why didnt …如何在Haskell中搜索二叉搜索树中的元素？我定义了我的树:
data Tree a =
Null |
L a |
N (Tree a) a (Tree a)
deriving Show
我想创建一个在BST中搜索元素的函数:
findElem :: Tree a -> a -> Maybe a
findElem tree n = ...
我该怎么做？
我在c中编写了一个二叉搜索树,并且在我的函数的开头和头文件中的'*'token'消息之前我一直得到愚蠢的"错误:预期')''
主文件
#include <stdlib.h>
#include <stdio.h>
#include "func.h"
#define ARRAYSIZE 12
int main(int argc, char *argv[3]) {
typedef struct node {
int value;
struct node * left;
struct node * right;
} * node;
node* root = NULL;
int nodes[ARRAYSIZE] = {3,6,2,1,7,8,3,5,7,2,9,4};
int i;
for(i = 0; i < ARRAYSIZE; i++) {
root = insert(root, nodes[i]);
}
if (strcmp(argv[1], "q") == 0) quit();
if (strcmp(argv[1], "i") == 0) insert(argv[2]);
if (strcmp(argv[1], "d") == 0) delete(argv[2]);
if (strcmp(argv[1], "s") == 0) …在这里我已经制作了一个删除二进制搜索树(BST)的程序,但是在执行时得到了分段错误(核心转储),我认为它在删除函数中但不知道我是否删除了删除函数的函数调用然后它的工作原理很好,就像找到最大元素,inorder遍历,但删除将无法正常工作.
#include<stdio.h>
#include<stdlib.h>
struct BST{
int data;
struct BST *left;
struct BST *right;
};
struct BST *newNode(int data){
struct BST *temp = (struct BST *)malloc(sizeof(struct BST));
temp->data=data;
temp->left=0;
temp->right=0;
return temp;
}
void inOrder(struct BST *root){
if(root==0)
return;
inOrder(root->left);
printf("%d",root->data);
inOrder(root->right);
}
struct BST *findMax(struct BST *root){
if(root==0)
return 0;
if(root->right!=0)
return findMax(root->right);
return root;
}
struct BST *dele(struct BST *root,int data){
if(root==0)
return 0;
if(data<root->data)
root->left=dele(root->left,data);
if(data>root->data)
root->right=dele(root->right,data);
else{
if(root->left && root->right)
{
struct BST *temp=findMax(root->left);
root->data=temp->data;
root->left=dele(root->left,root->data);
} …我试图比较在Java和C++中实现BST的方式.在Java中,Node看起来像
class Node{
int data;
Node left;
Node right;
}
在C++中它将是:
class Node{
int data;
Node *left;
Node *right;
}
我很困惑java方法的工作原理.据我所知,在C++中,左右两边都是指向包含下一个Node的内存区域的指针.在Java中,我并没有真正了解所有内容最终是如何连接的.左边和右边是节点本身,而不是指向节点的指针,因此Java中的每个Node对象占用3个节点的空间(一个用于自身,另一个用于子节点)？如果有人能够解释所有节点的连接方式以及内存分配的差异,那么这将是非常有用的.
另外,在C++中可以做同样的事情吗？你能不能让Node离开Node而不是指针？如果是这样,首先使用指针有什么好处？谢谢!
我在这个程序中面临分段错误.当我想出它时,流程似乎是正确的.请帮我查一下这个程序的错误.
#include<iostream>
#include<cstdlib>
using namespace std;
struct node
{
int data;
struct node* left;
struct node* right;
};
typedef struct node* Node;
void insert(Node,int);
Node root = NULL;
int main()
{
insert(root,2);
insert(root,1);
insert(root,3);
cout<<root->data<<" "<<root->left->data<<" "<<root->right->data<<endl;
return 0;
}
void insert(Node nod,int val)
{
if(nod == NULL)
{
Node newnode = new(struct node);
newnode->data = val;
newnode->left = NULL;
newnode->right = NULL;
nod = newnode;
if(root == NULL)
{
root = newnode;
}
}
else if(nod->data > val)
{ …我正在尝试使用C++创建二叉搜索树.我只使用函数来插入数据和查找数据.我似乎无法使程序工作,虽然我发现它是非常逻辑和正确的？
任何帮助将不胜感激.
#include<iostream>
using namespace std;
template <class T>
class BinarySearchTree
{
private:
struct tree
{
tree *leftchild;
tree *rightchild;
T data;
};
tree *root;
public:
BinarySearchTree()
{
root=NULL;
}
void insert(T);
void searchForItem(T);
};
template<class T>
void BinarySearchTree<T>::insert(T newNum)
{
tree *newItem = new tree;
tree *parent;
newItem->data = newNum;
newItem->leftchild = NULL;
newItem->rightchild = NULL;
if(root==NULL)
root=newItem;
else
{
tree *current;
current=root;
while(current)
{
parent = current;
if(newItem->data > current->data)
current = current->rightchild;
else
current = current->leftchild;
} …我试图使用递归在二叉搜索树中插入值，但是当我使用中序遍历运行它时，我得到 None 的输出。我尝试查看其他语言实现此功能，我只是尝试复制它，但它不起作用。我将树的根传递给插入函数，如果它不为空，我希望它向左或向右遍历。有人可以告诉我这有什么问题吗？我尝试将 bst.root 转换为 bst.get_root() ，但仍然产生相同的结果。
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
self.size = 0
def get_size(self):
return self.size
def get_root(self):
return self.root
def insert(self, root, value):
if root is None:
root = Node(value)
else:
if value < root.value:
root.left = self.insert(root.left, value)
else:
root.right = self.insert(root.right, value)
return root
def inorder(self, root):
if root == None:
return
else:
self.inorder(root.left)
print(root.value, end=" -> ") …当我运行我的程序时,我的'if'语句被编译为无法访问的代码,这反过来导致我的contains方法连续打印false,即使该数字存在于树中.我无法弄清楚为什么有人可以帮助我？我对编程很新.
这是我的节点类.
class Node<T> where T : IComparable
{
private T data;
private int balanceFactor = 0; //added for AVLTree
public Node<T> Left, Right;
public Node(T item)
{
data = item;
Left = null;
Right = null;
}
public T Data
{
set { data = value; }
get { return data; }
}
}
这是我的二叉搜索树类.
class BSTree<T> : BinTree<T> where T : IComparable
{ //root declared as protected in Parent Class – Binary Tree
public BSTree()
{
root = …可以用这个按顺序打印
void printInOrder(noBinTree *n){
if(n != NULL){
printInOrder(n->left);
printf(" %d ", n->number);
printInOrder(n->right);
}
}
并得到
1、2、3、4、5
我需要做什么才能按降序打印它（仅通过操作该函数）并得到 5、4、3、2、1 作为结果？
就数据结构而言，C ++中的std :: set不是真正的集合。std :: unordered_set是一个实数集，但std :: set是一个二叉搜索树，更具体地说是一棵红黑树。那么为什么将其称为std :: set？是否有一些特定功能可以将std :: set与二叉树区分开？谢谢。