标签: binary-tree

可能的重复：
二进制最小堆的链表实现（操作遇到问题......）

问候，

我无法找出一种算法来为我提供二叉堆的链表实现中树节点的位置。我已经使用数组实现了堆，现在我想尝试使用链表；如果我使用数组来表示堆，有没有办法找到其数组索引为 i 的树节点？

一般情况：
我想知道如何写入树（即更改底层的特定节点，将其替换为具有不同值的节点，该节点将旧节点作为其左子节点，将新节点作为右子节点）


特定的应用程序使它变得更加困难：
我试图将一个类似 20 个问题的游戏放在一起，从文件中读取现有的树，询问用户各种问题，如果不知道答案，则会询问用户区分最终猜测和正确答案以及正确答案之间的问题，并将新条目添加到游戏中（用指向猜测和答案的节点中的新问题替换猜测所在的位置）

如果构建二叉树如下

• 根是 1
• 元素 n 的左子元素是 2*n
• 元素 n 的右子元素是 (2*n)+1

如果我得到一个数字 n，找出它是在根的左子树还是右子树中的最快方法是什么？左子树是否有一些容易确定的数学性质？

注意：这不是一个家庭作业问题，尽管它是我试图解决的一个更大的算法问题的一部分。

考虑这个二叉搜索树的例子。

n =10 ;and if base = 2 then 

log n = log ₂ (10) = 3.321928。

我假设这意味着搜索一个元素最多需要 3.321 步（访问）。我还假设 BST 是平衡二叉树。

现在要访问值为 25 的节点。我必须转到以下节点：

50
40
30
25

所以我必须访问4个节点。3.321 几乎等于 4。

这种理解是对还是错？

根据Ray Wenderlich 的这篇文章，我能够创建一个如下的二叉树数据结构：

  enum BinaryTree<T: Comparable> {

  case empty
  indirect case node(BinaryTree<T>, T, BinaryTree<T>)

  var count: Int {
    switch self {
    case let .node(left, _, right):
      return left.count + 1 + right.count
    case .empty:
      return 0
    }
  }

  // 1.
  mutating func naiveInsert(newValue: T) {
    // 2.
    guard case .node(var left, let value, var right) = self else {
      // 3. 
      self = .node(.empty, newValue, .empty)
      return 
    }

    // 4. TODO: Implement naive algorithm!
    if newValue < value …

我写了下面的代码来求二叉树的高度，这是错误的，它在测试用例中失败了，但是为什么它是错误的，如何从逻辑上证明这是错误的？

// 错误代码

public static int height(Node root) {
          if(root != null){
            if(root.left != null && root.right != null){   
              return Math.max(height(root.left), height(root.right)) + 1;
            }else if(root.left != null){
               return height(root.left);  
            }else{
               return height(root.right);
            } 
          }
        return 0;  
    }

而以下代码是正确的！！

//正确的工作代码

public static int height(Node root) {
    if(root != null){
        if(root.left != null || root.right != null){   
          return Math.max(height(root.left), height(root.right)) + 1;
        }
      }
    return 0;  
}

使其中一个正确而另一个错误的两个代码之间的最大区别是什么？

为清楚起见，此处添加了 Node 的类代码。

class Node {
    Node left;
    Node right;
    int data;

    Node(int …

如果我有一个只将值作为参数（而不是节点）的方法，public Node finder (E val)我该如何找到相应的节点，而不管树的高度和宽度如何。如果该方法将 Node 作为参数，那么使用递归将是一个简单的解决方案。但不幸的是，我不允许更改方法签名。我怎样才能以聪明的方式做到这一点，而不是我在下面尝试的愚蠢的方式，这只会以大量的嵌入式if功能结束

public class BinarySearchTree<E extends Comparable<E>> {
    class Node {
        E value;
        Node leftChild = null;
        Node rightChild = null;
        Node(E value) {
            this.value = value;
        }
    }

    public Node finder(E val) {
        
        if (val == null) return null;
        if (root == null) return null;
        
        boolean flag = false;  
        Node temp = root;
        
        //find if Root Node matches value
        if(temp.value.compareTo(val) == 0) {
            flag = true;
            return temp;
        } 
        //if …

我想打印树中的所有节点（首先打印低级别的节点，对于具有相同输出级别的节点，首先打印具有较小值的节点）例如：输入

预期输出：10 6 20 1 8 18 21 7 25。 我试着这样编码

void print_Nodes(Node *root)
{
    if(root == nullptr) return;
        cout << root->value << " ";
    if(root->left!=nullptr){
        cout << root->left->value << " ";
        if(root->right!=nullptr){
            cout << root->right->value << " ";
        }
    }
    print_Nodes(root->right);
    print_Nodes(root->left);
}

但输出是：10 6 20 6 1 8 1 8 7 7 20 18 21 18 21 25。 你能指导我如何解决这个问题吗？

我想编写一个函数来显示给定的树是否是 BinarySearch。

这是我到目前为止所写的：

class Node: 

     def _isBinary(self):
        
        L=[]

        if self.left is not None and self.right is not None:
            if self.left.data>self.data or self.right.data<self.data:
               L.append(1)
            else:
               L+=self.left._isBinary()
               L+=self.right._isBinary()
        else:

            if self.left is not None:
               if self.left.data>self.datat:
                  L.append(1)
               else:
                  self.left._isBinary()

            if self.right is not None:
               if self.right.data<self.data:
                  L.append(1)
               else:
                  self.right._isBinary()

       return L

class tree:
    
    def isBinary(self):
        if self.root is None:
            return
        else:
            return  not 1 in self.root._isBinary(self.root.data)

（顺便说一句，我刚刚报告了代码中感兴趣的部分）这段代码运行良好，但是当例如一个数字（大于根）在树的左侧，但它是较低的数字：

     99
    /  \
   8   888
    \
     100

它应该给我 False，而不是它返回 True。我能做什么？（如果可能，不完全改变我的原始代码？）

我正在研究 Leet Code 问题543。二叉树的直径：

给定root二叉树，返回树的直径长度。

二叉树的直径是树中任意两个节点之间最长路径的长度。该路径可能会也可能不会经过root.

两个节点之间的路径长度由它们之间的边数表示。

实施例1

输入： root = [1,2,3,4,5]
输出： 3
解释： 是路径或3的长度。[4,2,1,3][5,2,1,3]

def diameterOfBinaryTree(self, root):
    return self.getHeight(root.left) + self.getHeight(root.right)

def getHeight(self, root):
    if not root:
        return 0
    return max(self.getHeight(root.left), self.getHeight(root.right)) + 1