Python中预排序二叉搜索树的叶节点

二叉树是一种包含不同节点的二叉数据结构，其中每个节点最多有两个子节点。这些节点遵循一些属性，包括：

二叉树的左节点的值小于根节点的值。
二叉树的右节点的值比根节点的值大。
所有子节点都必须遵循上述属性。

我们可以通过不同的方式来遍历二叉搜索树：

无序Inorder
前序Preorder
后序Postorder

中序算法：

左子树
根节点
右子树

预购算法：

根节点
左子树
右子树

后序算法：

左子树
右子树
根节点

问题陈述
我们有一个二叉搜索树的预序。我们需要从给定的二叉搜索树的预序中打印前导节点。二叉搜索树中可以有任意数量的叶节点。
考虑所有节点值都是正数并且已经被预先排序。我们必须打印树中的叶节点。
让我们通过几个例子来理解这个问题。

示例1：

输入：
{ 300 , 224 , 125 , 70 , 149 , 388 }

输出：
70 149 388

解释：
给定的二叉搜索树是：

第一个元素将是根，如前序遍历一样；我们首先遍历根节点，然后遍历左子树，然后遍历右子树。大于根节点的元素是左子树中的元素，其余的元素是右子树中的元素。使用此输入创建二叉搜索树后，我们得到元素 [70, 149, 388] 作为叶节点。

示例2：

输入：

{ 42, 30, 27, 23, 19, 22, 26, 29, 15, 32, 31, 35, 38 }

输出：

15 22 26 29 31 38

解释：

第一个元素将是根，如前序遍历一样；我们首先遍历根节点，然后遍历左子树，然后遍历右子树。使用此输入创建二叉搜索树后，我们得到元素[15, 22, 26, 29, 31, 38]是叶节点。

从二叉搜索树的前序中查找叶节点有两种方法。

1、简单方法
在此，我们首先使用中序数组和预序数组来查找二叉搜索树的预序。我们首先迭代前序数组，然后找到中序数组的元素。

def Search(inorder, ln, rn, k):  
    mid = (ln + rn) >> 1  
    if (inorder[mid] == k):  
        return mid  
    elif (inorder[mid] > k):  
        return binarySearch(inorder, ln, mid - 1, k)  
    else:  
        return binarySearch(inorder, mid + 1, rn, k)  
  
# leaf nodes from preorder traversal  
def leafNodes_Pre(preorder, inorder, ln, rn, index, n):  
  
如果没有左子树或右子树，则打印叶节点  ；
    if(ln == rn):  
        print(inorder[ln], end = " ")  
        index[0] = index[0] + 1  
        return  
  
检查数组是否越界  ；
    if (ln < 0 or ln > rn or rn >= n):  
        return  
# 搜索 inorder 数组中 preorder 的索引；
    loc = binarySearch(inorder, ln, rn, preorder[index[0]])  
  
# I提高index；
    index[0] = index[0] + 1  
  
# 搜索左侧子树的叶节点；
    leafNodes_Pre(preorder, inorder, ln, loc - 1, index, n)  
  
# 搜索右侧子树的叶节点  ；
    leafNodes_Pre(preorder, inorder, loc + 1, rn, index, n)  
  
def leafNodes(preorder, n):  
  
# storing inorder traversal  
    inorder = [0] * n  
  
    for i in range(n):  
        inorder[i] = preorder[i]  
  
# Sorting the array after searching the preorder  
    inorder.sort()  
  
    index = [0]  
      
# Printing the Leaf Nodes.  
    leafNodes_Pre(preorder, inorder, 0, n - 1, index, n)  
  
preorder = [42, 30, 27, 23, 19, 22, 26, 29, 15, 32, 31, 35, 38]  
num = len(preorder)  
print("The Leaf Nodes present in the binary search tree is: ")  
leafNodes(preorder, num)

输出:

The Leaf Nodes present in the binary search tree are:
15 22 26 29 31 38

解释：

首先，我们将遍历数组以查找无序数组中的元素。我们使用二进制搜索，因为它以升序遍历。我们将查找元素的范围设置为 [L，R]。如果 L 的值等于 R，我们就会得到叶节点。现在，我们将从 L = 0 和 R = node - 1 的值开始查找预序数组的根节点。为了搜索左侧子树的元素，我们设置 L = 0 和 R = root index。对于右侧子树，我们设置set L = root index + 1，R = node -1。

2.使用堆栈stack
我们将使用堆栈，并使用两个指针遍历数组。

def leafNode(preorder, node):  
    cn = [ ]  
    i = 0  
    for j in range(1, node):  
        found = False  
        if preorder[i] > preorder[j]:  
            cn.append(preorder[i])  
   
        else:  
            while len(cn) != 0:  
                if preorder[j] > cn[-1]:  
                    cn.pop(-1)  
                    found = True  
                else:  
                    break  
   
        if found:  
            print(preorder[i], end = " ")  
        i += 1  
          
    print(preorder[node - 1])  
      
if __name__ == '__main__':  
    preorder = [300, 214, 120, 66, 45, 54, 78, 142, 198, 37, 100, 44]  
    node = len(preorder)   
    print("The Leaf Nodes present in the binary search tree is: ")  
    leafNode(preorder, node)

输出:

The Leaf Nodes present in the binary search tree are:
54 78 44

解释：

开始时，i = 0，j = 1。比较 array 和 array[j]，如果 array > array[j]，则表示 array[j] 在 a 的左边。然后，a 将被推入堆栈。现在我们将弹出元素，直到 array > 栈顶元素，然后打印第 j 个值。第 j 个值将是二叉搜索树的叶子节点。