什么是二进制子树的最左边和最右边的节点？

最右边的节点将在左子树，我认为那时，最左边的是右子树的最大价值最大价值的节点。

然而，在another article它让我看到了不同的方法来找到最左边的节点：

1）如果给定节点没有右孩子：

跳转到指定节点的根，直到它任何节点的左侧子节点。该节点将成为树中的下一个较高节点。

2）如果给定节点具有右子：

a）如果给定节点的右孩子没有左孩子

The right child will be the next higher node.

b）如果给定节点的右子有左子

The leftmost leaf node will be the next higher node.

即第2个方法不返回最大的价值是1方法建议请澄清..

来源

2015-11-01 Square-root

根据你附加的链接判断，我假设你正在专门讨论二元搜索树，它们有关于它们节点构成的规则。

至于二叉树一般规则（通过扩展，子树）：

每个孩子的节点的右侧会比节点更大。
节点左侧的每个小孩都会比节点小。

因此，任何给定子树的最右边的孩子总是最高的值。而且，任何给定子树的最左边的孩子总是最低的值。

请记住，二叉树与二叉搜索树略有不同，并且这些规则不一定适用于二叉树。

让我们用下面的二叉搜索树为例：

假设我们正在试图寻找树的最高节点值。如果我们从节点9开始（“根”），我们继续向下遍历节点的每个右侧子节点，直到没有更多的右侧子节点（即，从节点9开始，然后向下移动到节点13，然后结束节点16）。因此，16是树中最高的值。

类似地，在树中搜索最低节点值时，我们从树的根节点开始，继续遍历每个左边的孩子，直到没有更多的左边孩子存在。

来源：大学（IT学生）在我的数据结构和算法课程中所学这个

希望这会有所帮助，请随时纠正我可能犯任何错误（我是新来的）。

来源

2015-11-01 04:25:48 user3341765

这个想法是使用Level Order Traversal。要找到第一个节点，我们使用一个变量isFirst。为了分离等级，我们在每个关卡后排队NULL。因此，在层次顺序遍历中，如果我们看到NULL，我们知道下一个节点将成为其级别的第一个节点，因此我们设置isFirst。

void printCorner(Node *root) 
{ 
    queue<Node *> q; 
    q.push(root); 
    q.push(NULL); 
    bool isFirst=false; 
    bool isOne = false; 
    int last; 
    Node *temp; 
    while(!q.empty()){ 
     temp = q.front(); 
     q.pop(); 
     if(isFirst){ 
      cout<<temp->key<<" "; 
      if(temp->left)q.push(temp->left); 
      if(temp->right)q.push(temp->right); 
      isFirst = false; 
      isOne = true; 
     } 
     else if(temp==NULL){ 
      if(q.size()>=1)q.push(NULL); 
      isFirst = true; 
      if(!isOne)cout<<last<<" "; 
     } 
     else{ 
      last = temp->key; 
      isOne = false; 
      if(temp->left)q.push(temp->left); 
      if(temp->right)q.push(temp->right); 
     } 
    } 
}

来源

2017-12-24 15:05:03 HeadAndTail

什么是二进制子树的最左边和最右边的节点？

回答

相关问题