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

Question

我正在阅读 this 并且在一个地方它说

最右边的节点将是左子树中具有最大值的节点，我假设最左边是右子树中的最大值。

但是，在 another article 中，它向我展示了一种查找最左边节点的不同方法：

1) 如果给定的节点没有权限 child :

转到给定节点的根，直到它是任何节点的左侧 child。该节点将是树中的下一个更高节点。

2) 如果给定的节点有权利 child :

a) 如果给定节点的右边child没有左边child

The right child will be the next higher node.

b) 如果给定节点的右边child已经离开child

The leftmost leaf node will be the next higher node.

即第二种方法没有return第一种方法建议的最大价值请澄清..

Answer 1

根据您所附的 link 判断，我假设您是在专门谈论二叉搜索树，它有关于其节点 make-up 的规则。

作为二叉树（以及子树）的一般规则：

节点右侧的每个 child 都将大于该节点。
节点左侧的每个 child 都将小于该节点。

因此，任何给定 sub-tree 的 right-most child 将始终是最高值。此外，任何给定 sub-tree 的 left-most child 将始终是最低值。

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

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

        9
      /   \
     4     13
   /  \   /  \
  1   5  11  16

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

与在树中搜索最低节点值类似，我们从树的根节点开始，一直向下遍历每个左边 child 直到没有更多的左边 children 存在。

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

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

Answer 2

想法是使用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);
        }
    }
}

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

What is leftmost & rightmost node of a binary subtree?

java

binary-tree

data-structures