标签: binary-tree

我正在尝试控制台二叉树中的每个数据。我的主要问题是我想以递归方式实现。到目前为止我基本上有这个代码：

this.levelOrder = function (root) {
    if (root.data != null) {
        console.log(root.data);

        if (root.left != null) {
            this.levelOrder(root.left);
        }

        if (root.right != null) {
            this.levelOrder(root.right)
        }
    } else {
        return;
    }
};

输出是3 2 1 5 4 7

但应该是3 2 5 1 4 7。所以基本上我正在访问节点的第一个子节点，而不是首先打印所有子节点。

我正在尝试解决以下问题，假设我有这个二叉树......

       3
      / \
     9  20
       /  \
      15   7

然后我需要获取每个级别的所有节点，所以我的结果将是......

[[3],[9,20],[15,7]]

我相信我正在接近解决方案，但我不确定我哪里出错了，如果有人可以帮助我解决我的解决方案，那就太好了，如果我走错了路，请告诉我。

我的第一步是使用以下函数获取树的深度......

def get_depth(self, root):
    if root.left == None and root.right == None:
        return 1
    return max(self.get_depth(root.left), self.get_depth(root.right)) + 1

深度是3。

接下来我调用了一个函数，该函数旨在给我预期的结果......

def levelOrder(self, root):
    depth = self.get_depth(root)
    return self.find_comb(root, [[]]*depth, 0)

def find_comb(self, root, result, level):
    if root is None:
        return None
    self.find_comb(root.left, result, level+1)
    self.find_comb(root.right, result, level+1)
    result[level].append(root.val)
    return result

我的思考过程是，我将递归遍历树，并且level参数将跟踪我当前所在的级别。然后我会将该root.val级别上的所有内容附加到该索引的结果中。

假设我在 level 上1（我们从 0 开始），那么 level 上的节点 …

我正在尝试解决Algoexpert 的节点深度问题。该问题要求您计算给定二叉树中所有节点的深度总和。例如，给定这棵树 -

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

总和应该是 16。

我为其编写了一个递归解决方案，我认为这是正确的，但有趣的是，只有第一个测试通过，而其余测试用例失败。这是我的解决方案-

import java.util.*;

class Program {

  // static variable to hold the final sum
  private static int finalSum = 0;

  public static int nodeDepths(BinaryTree root) {
        // Write your code here.
        int runningSum = 0;
        depthHelper(root.left, runningSum);
        depthHelper(root.right, runningSum);
        return finalSum;
  }
    
    private static void depthHelper(BinaryTree node, int runningSum) {
        if(node == null) return;
        runningSum++;
        finalSum …

我在 leetcode 中遇到了以下问题 - https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

我能够编写下面的算法（找到前序和后序遍历并保存它们。然后从遍历中重建树），但遇到了一个更基本的问题 - 即，如何构造具有重复值的二叉树。我失败的测试用例是 [3,2,4,3]，其中前序和后序是相同的。

任何帮助和建议表示赞赏。

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return null;
        ArrayList<Integer> inorder = inOrder(root, new ArrayList<Integer>());
        ArrayList<Integer> preorder = preOrder(root, new ArrayList<Integer>());
        StringBuilder sb = new StringBuilder("");
        for(int val : inorder){
            sb.append(val + " ");
        }
        sb.append("|");
        for(int val : preorder){
            sb.append(val + " ");
        }
        String serialized = sb.toString();
        return serialized;
    }

    // Decodes your encoded data …

考虑计算结构上不同的二叉搜索树的数量的问题:

给定N,找到包含值1 ... N的结构上不同的二叉搜索树的数量

给出一个解决这个问题的算法很容易:修复根中的每个可能的数字,然后递归地解决左右子树的问题:

countBST(numKeys)
    if numKeys <= 1
        return 1
    else
        result = 0
        for i = 1 .. numKeys
            leftBST = countBST(i - 1)
            rightBST = countBST(numKeys - i)

            result += leftBST * rightBST

        return result

我最近熟悉了treaps,我给自己提出了以下问题:

给定N,找到包含值1 ... N的不同treap的数量,优先级为1 .. N.如果它们在相对于密钥或优先级的结构上不同,则两个treap是不同的(请继续阅读以进行说明).

我一直试图找出一个可以解决这个问题的公式或算法,但我还没有成功.这是我注意到的:

1. 对于这些问题的答案n = 2,并n = 3似乎是2和6,基于我在纸上画树木.
2. 如果我们忽略了表示treaps的部分也可能与节点的优先级不同,那么问题似乎与仅计算二进制搜索树相同,因为我们将能够为每个BST分配优先级,以便它也尊重堆不变量.我没有证明这一点.

3. 我认为困难的部分是考虑到在不改变结构的情况下置换优先级的可能性.例如,考虑这个treap,其中节点表示为(key, priority)对:

             (3, 5)
             /    \ 
        (2, 3)    (4, 4)
        /              \
   (1, 1) …

   Run Code Online (Sandbox Code Playgroud)

伙计我是数据结构的新手.大多数时候在书籍和参考书中我看到这个结构的二叉树

struct btree {
    int data;
    struct btree *left;
    struct btree *right;
};

但在上面的图像中它会是这样的

struct btree
{
    int data;
    struct btree *left;
    struct btree *right;
    struct btree *parent;
};

所以我的问题是它依赖于程序员来选择树节点的结构(例如还包括指向父节点的指针)或者我们只能有两个指针,一个指向左边的子节点,另一个指向右边的子节点.

我需要帮助理解这个面试问题:

问:找到一个算法,在二元搜索树中找到给定节点的下一个节点(例如,顺序后继节点),其中每个节点都有一个到其父节点的链接.

父母是指有序的前任还是直接的父母？如何创建一个树,其中节点具有到根节点的链接或者有前导的链接？任何帮助理解下面的数据结构和程序将不胜感激......

解决方案(如表格中所示)如下所示:

 public static TreeNode inorderSucc(TreeNode e) {
   if (e != null) {
     TreeNode p;

     // Found right children -> return 1st inorder node on right
     if (e.parent == null || e.right != null) {
       p = leftMostChild(e.right);
     } else {
       // Go up until we’re on left instead of right (case 2b)
       while ((p = e.parent) != null) {
         if (p.left == e) {
           break;
         }
         e = p;
       }
     }
     return p;
   }
   return null;
 } …

我一直在做一项任务,现在我被困在破坏者身上.我必须创建一个包含所有常用成员函数和一些特殊运算符的通用二叉树.还有一个限制:一切都必须迭代地工作,所以这次没有讨厌的递归黑客.

BinTreeNode类的析构函数显然有些问题,因为如果我删除这样的节点:

BinTreeNode<int> * node = new BinTreeNode<int>();
delete node; 

我仍然可以访问它的数据:

node->getData(); //should fail miserably

所以删除没有效果,但我不知道如何纠正析构函数.在我看来,算法应该是正确的,所以我怀疑我如何使用指针有问题,但在这一点上我很困惑,我甚至不理解我自己的代码.

我有这个代码:

BinTree.h

#ifndef BINTREE_H_
#define BINTREE_H_

#ifndef NULL
#define NULL 0
#endif

#include "BinTreeNode.h"

template <class T>
class BinTree
{
    private:
        BinTreeNode<T> * root;
    public:
        //constructors and destructor
        BinTree():
            root(NULL){}

        BinTree(T data):
            root(new BinTreeNode<T>(data)){}

        ~BinTree();

        //search
        BinTreeNode<T> * search(T data);

        //insert
        bool insert(T data);

        //remove
        bool remove(T data);
};

template <class T>
BinTree<T>::~BinTree()
{
    delete root;
}

template <class T>
BinTreeNode<T> * BinTree<T>::search(T data) …

如何设计一个有很多(无限数量)分支的树？

我们应该使用哪种数据结构来存储子节点？

是否有可能在R的分类树分析中获得节点的p值？我使用的是rpart,无法为每个节点找到p值.也许这只能通过回归而不是类别来实现.

structure(list(subj = c(702L, 702L, 702L, 702L, 702L, 702L, 702L, 
702L, 702L, 702L, 702L, 702L, 702L, 702L, 702L, 702L, 702L, 702L, 
702L, 702L, 702L, 702L, 702L, 702L), visit = c(4L, 4L, 4L, 4L, 
4L, 4L, 4L, 4L, 4L, 4L, 4L, 4L, 4L, 4L, 4L, 4L, 4L, 4L, 4L, 4L, 
4L, 4L, 4L, 4L), run = structure(c(1L, 1L, 2L, 2L, 2L, 2L, 2L, 
2L, 2L, 2L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 4L, 4L, 4L, 4L, 4L, 
4L), .Label …