标签: binary-tree

我有点不得不把我以前的C问题暂停,因为现在这个问题更重要了......

我已经在二叉搜索树上编写了插入和删除函数,但删除函数不完整.我需要帮助的一些事情......

1)我的插入功能是好还是可以以某种方式改进？

2)我的删除功能没有删除具有左右子节点的节点.我在过去的几个小时里搜索过很多但是找不到合适的方法.

2.a)我应该如何删除具有2个子节点的节点？

2.b)与第一个问题一样,删除功能是好还是可以改进？这个我知道它可以因为我在那些ifs中重复了很多代码,但是我不知道如何改进它,我也需要帮助.

typedef struct sClientProfile *ClientProfile;
typedef struct sClientTree *ClientTree;

typedef struct sClientProfile {
    char *clientName;
    int clientAge;
    int clientNIF;
} nClientProfile;

typedef struct sClientTree {
    ClientProfile clientProfile;
    char *clientName;

    ClientTree leftTree;
    ClientTree rightTree;
} nClientTree;

void addClientToTree(ClientTree *cTree, ClientProfile cProfile) {
    if(!*cTree) {
        ClientTree new = (ClientTree)malloc(sizeof(nClientTree));

        if(!new) {
            perror("malloc");
        }

        new->clientName = strdup(cProfile->clientName);
        new->clientProfile = cProfile;

        new->leftTree = NULL;
        new->rightTree = NULL;

        *cTree = new;
    } else {
        if(strcmp((*cTree)->clientName, cProfile->clientName) …

如果我有10个元素并以空树开头,那么以big-O表示法将10个元素插入Red Black的复杂性是多少？

它是否会超过O(log 10),因为每次插入元素时,它都必须搜索元素的适当位置,并在祖先节点和子节点之间执行一系列旋转.所以如果我有N个元素并且在红黑树中插入N次,那么它会不会成为O(n log n)？

谢谢你的帮助.

嘿所有,所以我试图构建一个简单的二叉树,它有两个键,并评估其排序的总和.这是它的样子:

struct SumNode
{
    int keyA;
    int keyB;
    SumNode *left;
    SumNode *right;
};

class SumBTree
{
    public:
        SumBTree();
        ~SumBTree();

        void insert(int, int);
        SumNode *search(int, int);
        SumNode *search(int);
        void destroy_tree();

    private:
        SumNode *root;

        void insert(int,int, SumNode*);
        SumNode *search(int,int, SumNode*);
        SumNode *search(int, SumNode*);
        void destroy_tree(SumNode*);
};


SumBTree::SumBTree()
{
    root = NULL;
}

SumBTree::~SumBTree(){};


void SumBTree::insert(int a, int b, SumNode *leaf)
{
    int sum = a + b;
    int leafsum = leaf->keyA + leaf->keyB;

    if (sum < leafsum)
    {
        if (leaf->left != NULL) …

所以我完成了List练习并继续使用Binary Trees.我的代码到目前为止:

tree.h中

#include "Node.h"

class Tree
{
private:
    int mCount;
    Node *root;

public:
    Tree();
    ~Tree();

    void insert(int, Node *);
};

Tree.cpp

void Tree::insert(int data, Node *node)
{
    if( root == 0 )
    {
        Node *temp = new Node;
        temp->setData(100);
        temp->setRight(0);
        temp->setLeft(0);
        root = temp;
    }
    else
    {
        if( data > root->getData() )
            return insert( data, root->getRight() );
        else
            return insert( data, root->getLeft() );
    }
}

main.cpp中

int main(int argc, char** argv)
{
    Tree *tree = new Tree;
    tree->insert( 100, …

我正在C中完成一项家庭作业,我认为二叉搜索树是实现我的解决方案的最佳方式.问题是我们不允许定义结构或任何复合数据类型,所以没有

struct TreeNode {
    struct TreeNode* parent;
    struct TreeNode* left;
    struct TreeNode* right;
    int key;
    int value;
}

或类似的东西.

树必须完全用指针实现,所以我一直在尝试定义一些宏来使导航和编辑树更容易,比如这个用来获取指向节点父节点的指针(指针所在的位置)是无效指针):

#define PARENT(ptr) *(void *)(ptr+ALIGNMENT)

当然,问题在于你无法取消引用void指针.我的问题是:如果你有一个void指针指向存储器中存储另一个void指针的位置,你怎么能读取存储的指针.

或者,如果这是不可能的,有没有更好的方法来做这棵树？

我有一个二叉树:

struct node 
{
    int n; // value of node
    struct node *left; // left subtree
    struct node *right; // right subtree
    struct node *level; // level pointer (node “to the right”)
}

最初,level字段设置为NULL.

我需要编写一个函数来链接树中同一级别的所有节点(不仅是示例,而是任何给定的树).

void linkSameLevel(struct node *t);

我怎么知道我的函数的运行时间和内存使用量对于包含n个节点的深度为d的树？

在这里我有:

这就是我需要的:

我目前正在开发一个带有二叉树的项目，并且已经从存储库中获取了用于打印出树的代码。

长话短说，如果我可以在代码中实现接口，它将以我想要的格式打印输出。

但是，其中之一需要异常返回接口类。（见下文）

@Override
public IBT getLeft() {

    return null;
}

这是获取左子树的方法，其中IBT是二叉树接口。

这比我做的简单吗？

返回接口有帮助吗？

我是SML的新手并且正在进行关于树遍历的练习.这是问题的设定.

datatype 'a bTree = nil | bt of 'a bTree * 'a * 'a bTree;

我需要编写一个函数inorder,它接受一个二叉树并在inorder遍历中返回树的所有成员的列表.

我写了这一行:

fun inorder(nil) = nil
  | inorder(bt(left,key,right)) = inorder(left) @ [key] @ inorder(right);

但得到一些错误,不知道如何解决:

Error: operator and operand don't agree [tycon mismatch]
operator domain: 'Z list * 'Z list
operand:         'Z list * 'Y bTree
in expression:
  (key :: nil) @ inorder right

Error: operator and operand don't agree [tycon mismatch]
operator domain: 'Z list * 'Z list
operand:         'Y bTree * _ …

我有这个二叉树结构:

# A Node is an object
# - value : Number
# - children : List of Nodes
class Node:
    def __init__(self, value, children):
        self.value = value
        self.children = children

我可以很容易地递归地对节点求和:

def sumNodesRec(root):
    sumOfNodes = 0
    for child in root.children:
        sumOfNodes += sumNodesRec(child)
    return root.value + sumOfNodes 

示例树:

exampleTree = Node(1,[Node(2,[]),Node(3,[Node(4,[Node(5,[]),Node(6,[Node(7,[])])])])])

sumNodesRec(exampleTree)

> 28

但是,我很难弄清楚如何迭代地对所有节点求和.通常,使用定义中具有"左"和"右"的二叉树,我可以找到总和.但是,这个定义在迭代地思考它时会让我有点沮丧.

任何帮助或解释都会很棒.我试图确保我并不总是递归地做事情,所以我试图将正常的递归函数创建为迭代类型.

我正在努力使用树定义地图foldBT.我的想法是将树转换为列表,将运算符映射到列表,然后将列表转换回树.但它听起来效率低,也没有利用foldBT...我试图运行,foldBT (*2) Nil (numTree [3,5,7]但ghci报告错误.我真的不明白这个功能foldBt是如何运作的.一个例子就是很棒.

data SimpleBT a = Nil | N a (SimpleBT a) (SimpleBT a) deriving (Show, Eq)

foldBT :: (a -> b -> b -> b) -> b -> SimpleBT a -> b
foldBT f e Nil = e
foldBT f e (N a left right) = f a (foldBT f e left) (foldBT f e right)

mapTree :: (a -> b) -> SimpleBT a -> SimpleBT b
mapTree …