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

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

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

我们可以通过不同的方式来遍历二叉搜索树:
  1. 无序Inorder
  2. 前序Preorder
  3. 后序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 个值将是二叉搜索树的叶子节点。