二叉树是一种包含不同节点的二叉数据结构，其中每个节点最多有两个子节点。这些节点遵循一些属性，包括：
- 二叉树的左节点的值小于根节点的值。
- 二叉树的右节点的值比根节点的值大。
- 所有子节点都必须遵循上述属性。
我们可以通过不同的方式来遍历二叉搜索树：- 无序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 <strong>name</strong> == '<strong>main</strong>':
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 个值将是二叉搜索树的叶子节点。