标签: binary-tree

我正在研究一种用C++编写的有点复杂的数学代码.我正在使用(模板化)树结构进行自适应函数表示.由于某些数学属性,我最终会遇到需要从一种节点更改为另一种节点的情况.这需要在存储和性能方面透明地并且以最小的开销发生,因为这些结构用于非常繁重的计算.

具体情况如下:我有一个模板化的抽象基类,它定义了一般的双链节点的一般数学和结构属性.每个节点除了跟踪它的子节点之外,还需要来自它的父节点和顶级Tree类的信息.两个类继承自此类,FunctionNode和GenNode.这些类在存储和功能方面非常不同,并且不应该(至少是公开的)彼此的祖先.因此,我想构建一个这样的树:

     T
     N
    / \
   N    N
       / \
      G   N
     / \
    G   G

Run Code Online (Sandbox Code Playgroud)

其中T是树,N是普通的FunctionNode,G是GenNode.问题是N - G转换:N需要有G型子,G是N型父.由于N和G只是堂兄而不是兄弟,我不能将N*转换为G*.G足以知道N是一个BaseNode,但N必须以某种方式以多态方式存储G,以便在遍历树时自动调用正确的虚拟.任何想法如何优雅和有效地解决这个问题将不胜感激!:)当然有人可能会破解这个,但由于这是一个非常基础的代码,我想有一个很好的解决方案.未来可能会有很多此代码的衍生产品.

最好的祝福,

Jonas Juselius

特罗姆瑟大学理论与计算化学中心

我目前正试图绕过递归,所以我选择了一本c ++教科书并开始阅读.关于递归的章节中的前几页很容易理解,但后来我找到了一个对我没有意义的项目.

 int height(node *p)
 {
    if(p==NULL)
       return 0;
    else{
   return 1 + max(height(p->llink),height(p->rlink));

  }

如果max给出了两个值中最大的值,那么max如何从它返回的高度获得它的参数.如果有人可以帮助我会非常感激.....

基本上我想将BST树变成一个映射,其中节点是键,节点的出现次数是值.所以,如果我输入这个:

toMap(叶子13)

我会的

> [(13,1)]

这是我到目前为止:

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

toMap' :: Int -> Tree a -> ([(a, Int)], Int)
toMap' a Empty = ([], a)
toMap' a (Node x xl xr) = ((x, a): xl' ++ xr', k)
                      where (xl', i) = toMap' (a+1) xl
                            (xr', k) = toMap' (i) xr

toMap :: Tree a -> [(a, Int)]
toMap = fst. toMap' …

我正在研究用于插入二叉搜索树的代码.它适用于我插入的第一个节点,使其成为根,但之后它似乎没有插入任何节点.我确定设置左/右引用是个问题,但我无法弄明白.请帮忙!

    //params: key of node to be inserted, parent node
    public void insert(int newKey, TreeNode parent){

    //if the root of the tree is empty, insert at root
    if(this.getRoot() == null){
        this.root = new TreeNode(newKey, null, null);
    }

    //if the node is null, insert at this node
    else if(parent == null)
        parent = new TreeNode(newKey, null, null);


    else{
        //if the value is less than the value of the current node, call insert on the node's left child
        if(newKey < parent.getKey()) { …

我正在尝试使用Haskell Diagrams库来绘制二叉树.

这是我的树型:

data Tree a = Empty
            | Node { label :: a, left,right :: Tree a }

leaf :: a -> Tree a
leaf a = Node a Empty Empty

这是一个随机树:

t0 = Node 1 (Node 2 (leaf 3) (leaf 4))   (Node 5 (leaf 6) (leaf 7))

为了在中间绘制一个带有char的圆圈,我正在使用这个简单的函数(工作正常):

diagNode :: String -> Diag

这是我绘制二叉树的代码:

diagTree :: Show s => Tree s -> Diag
diagTree Empty = diagNode "Empty"

diagTree (Node x Empty Empty) = connectOutside "X" "L" $ …

我对部分有序的树如何工作有点困惑.它们和二叉树有什么相同之处？另外,它最适合用于什么？

例如,如果我将5,6,4,9,3,1,7插入空树中,我会得到:

      5
     / \
    4   6
  /      \
 3       9
/       /
1      7

所以我定义了一个递归函数,它将x的值作为参数(如算术变量x,即"x + 3 = 5")并返回算术表达式的结果.表达式取自二进制表达式树,如下所示:

你从根部开始,继续向下工作,直到你击中叶子,一旦你做到了,你就会回来.树上的表达式是:

x*((x + 2)+ cos(x-4)).

我的这个函数的代码如下:

     // Returns the value of the expression rooted at a given node
// when x has a certain value
double evaluate(double x) {
    if (this.isLeaf()) {
        //convert every instance of 'x' to the specified value
        if (this.value.equals("x")) {
            this.value = Double.toString(x);
        }
        //return the string-converted-to-double

        return Double.parseDouble(this.value);
    }
    //if-else statements to work as the arithmetic operations from the tree. Checks the given node and performs the required operation
    else …

static int sum=0;
    public static int size(TreeNode root){
        if(root==null)
        return sum;
        sum++;
        sum=size(root.left);
        sum=size(root.right);
        return sum;
    }

我们必须完成函数"size",它计算二叉树中的节点数.我写了上面的代码.对于某些测试用例,它给出了错误的答案.请解释上面的代码有什么问题.

我被要求为以下二进制树实现一个功能：

data BinaryTree a = Nil | BNode a (BinaryTree a) (BinaryTree a) 

我需要实现的功能应该产生一个完整的，对称的，无限的二进制树a，并且具有以下特征：

infTree :: a -> BinaryTree a

我该如何实施？

下面的代码测试二叉树是否平衡。有人告诉我它的运行时间是O（n log n）。

据我了解...

• getHeight() 访问每个节点一次，所以它是O（n）。

• isBalanced()调用getHeight()..然后递归

如果isBalanced()在所有n个节点上调用if ，并且调用的getHeight()是O（n），为什么复杂度不是O（n²）？

int getHeight(TreeNode root) {
    if (root == null) return -1; 
    return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}

boolean isBalanced(TreeNode root) {
    if (root == null) return true;
    int heightDiff = getHeight(root.left) - getHeight(root.right);
    if (Math.abs(heightDiff) > 1) 
        return false;
    else
        return isBalanced(root.left) && isBalanced(root.right);

}