标签: binary-tree

如何定义一个Haskell函数,它将函数应用于二叉树中的每个值？所以我知道它与map函数类似- 它的类型是:

mapT :: (a -> b) -> Tree a -> Tree b

但那就是它......

我有一个形状的二叉树.我想将它转换为相同形状的 BST搜索树.可能吗？

我试过像 - 的方法

• 按顺序遍历二叉树并将内容放入数组中.然后将其映射到BST,记住条件(左val <= root <=右val).这适用于某些情况,但对其他情况不利.

PS:我看过这个 - 二叉树问题.检查相似的形状.但是,比较2个BST的形状相似性很容易.

一种新的树木和递归功能....

我知道如何创建堆栈以及如何创建递归函数的基础知识.

我正在进行预先排序的遍历搜索,当搜索的值与该节点的值匹配时,该搜索应返回树中节点的地址.

我在返回部分遇到问题...我试着在调用堆栈上读取一些东西......但我不明白如何实现它.它已经存在或者我必须制作这个堆栈吗？如果我必须制作它,我该如何制作这个堆栈？我读到它需要与树的高度成正比...是找到树高的最佳方法来制作另一个函数吗？

这是我到目前为止编写的一些代码:Tree和NodePtr是一个指向节点的指针......

NodePtr SearchTree(int v, Tree T)
{
    //printf(" %i \n", T->value);

    if(T->value == v) 
    {
        return T;
    }
    else
    {
        if(T->Left != NULL) SearchTree(value, T->Left);
        if(T->Right != NULL) SearchTree(value, T->Right);
    }

    return NULL;
}

private void sumNode(TNode node) {
    int sum = 0;
    if (node == null)
        return;

    sumNode(node.getLeft());
    sumNode(node.getRight());
    if (node.getLeft() != null && node.getRight() != null) {
        sum = (node.getData() + node.getLeft().getData() + node.getRight()
                .getData());
    } else if (node.getLeft() != null) {
        sum = (node.getData() + (Integer) node.getLeft().getData());
    } else if (node.getRight() != null) {
        sum = (node.getData() + node.getRight().getData());
    } else {
        sum = 0;
    }
    node.setData(sum);
}

我知道我的方法是完全错误的-我不知道该怎么做。

我想将每个节点值替换为其所有后代的总和，有人可以指导我该怎么做吗？

我已经解决了这个问题。甚至伪代码也将不胜感激。

问题是：

• 我的树有： 5 2 1 3 6 8
• 其结果是：0 …

假设一个二叉搜索树,我想在我们尝试插入已经存在的元素时返回错误.有没有办法让这项工作？

data BST2 a = EmptyBST2 | Node2 a (BST2 a) (BST2 a)  deriving Show

insert2 :: a -> Either b (BST2 a) -> Either b (BST2 a)
insert2 elem (Right EmptyBST2) = Right (Node2 elem EmptyBST2 EmptyBST2)
insert2 elem (Right (Node2 root left right))
  | (elem == root) = Left "Error: Element already exist."
  | (elem < root) = (Node2 root (insert2 elem left) right)
  | otherwise = (Node2 root left (insert2 elem right))

注意:我是Haskell的新手.

我在编译器课程中有这个问题,但我真的不知道如何处理它.谁能请给我一个比标题中给出的更好的暗示？

显示由以下语法生成的所有二进制字符串都具有可被3整除的值.

提示:对解析树中节点的数值使用归纳.

num -> 11 | 1001 | num 0 | num num

Run Code Online (Sandbox Code Playgroud)

有没有办法将auto_ptr设置为NULL或等效？例如,我正在创建一个由节点对象组成的二叉树:

struct Node {
    int weight;
    char litteral;
    auto_ptr<Node> childL;
    auto_ptr<Node> childR;
    void set_node(int w, char l, auto_ptr<Node> L, auto_ptr<Node> R){
        weight = w;
        litteral = l;
        childL = L;
        childR = R;
    }
};

对于不是父节点的节点,我计划这样做:

auto_ptr<Node> n(new Node);
(*n).set_node(i->second, i->first, NULL, NULL);

这会引发错误.有没有办法将它设置为NULL,还是有另一种有意义的行动方案？

给定一个二叉树,其节点具有以下类型:

struct Node {
  Node* left;
  Node* right;
  int data;
  Node* foo;   // uninitialized - use it any way you like
};

按级别顺序打印树数据,并使foo每个节点的成员指向下一个兄弟节点.

除了具有非数组类型的常量变量外,我们不允许使用任何其他存储(特别是不允许使用外部队列).

我在java中创建了一个二进制搜索树,允许用户将节点添加到树中

这是我在java中的二叉树的实现,它在创建时接受根节点,然后自动确定它应该将子节点添加到树的左侧或右侧.

public class BinarySearchTree {

    Node root = null;
    public BinarySearchTree(Node root){
        this.root =root;
    }
    public void add(int data){
        Node newNode = new Node(data);
        if(this.root ==null){
            newNode =this.root;
        }
        if(data>this.root.data){
            addRight(root,newNode);
        }

        if(data<this.root.data){
            addLeft(root,newNode);
        }
    }

    public Node getRoot(){
       return  this.root;
    }

    private void addLeft(Node root, Node newNode) {
        if(root.leftChild == null){
            root.leftChild = newNode;
        }
        else {
            this.root = this.root.leftChild;
            add(newNode.data);
        }
    }

    private void addRight(Node root,Node newNode) {
        if (root.rightChild == null){
            root.rightChild = newNode;
        }
        else …

我正在研究一个检查元素是否是二叉树的一部分的函数.我为我的树定义了一个类型,称为Tree函数以获取根元素和左右子树,以及一个函数,isElement用于检查值是否在我的树中.不幸的是,该函数仅适用于根元素.

以下示例说明了从isElement函数中获得的错误结果:

*Main>let tree = Node 1 Empty (Node 2 Empty (Node 3 Empty Empty))
*Main> isElement  tree 2
False
*Main> isElement  tree 3
False
*Main> isElement  tree 1
True

这是我的代码:

data Tree a = Node a (Tree a) (Tree a) 
        |Empty
        deriving (Show)

nodeValue :: Tree t -> t
nodeValue (Node x _ _) = x

rightTree :: Tree t -> Tree t
rightTree (Node _ _ x) = x

leftTree :: Tree …