跟我一起学“仓颉”算法-二叉查找树练习题

目录

一、练习题

二、小结

一、练习题

1. 给定一个字母二叉树的树叶删除序列，输出树的先序遍历。

package Algorithm.bst import std.collection.* public class Node { public var val: String public var left: Option<Node> public var right: Option<Node> public init(val: String) { this.val = val this.left = Option<Node>.None this.right = Option<Node>.None } } public class LeafDeletionSequenceToPreorder { // 根据树叶删除序列构建二叉树 public static func buildTreeFromLeafDeletion(deletionSequence: Array<String>): Node { // 反转删除序列，得到类似后序遍历的顺序 let reversed = Array<String>(deletionSequence.size, repeat: '') for (i in 0..deletionSequence.size) { reversed[i] = deletionSequence[deletionSequence.size - 1 - i] } // 使用哈希表记录每个节点的父节点关系 let nodeMap = HashMap<String, Node>() var root = Option<Node>.None // 处理反转后的序列 for (i in 0..reversed.size) { let current = reversed[i] let currentNode = Node(current) nodeMap.add(current, currentNode) if (i > 0) { let parentChar = reversed[i - 1] var parentNode = nodeMap[parentChar] if (parentNode.left.isNone()) { parentNode.left = currentNode } else { parentNode.right = currentNode } } else { root = currentNode } } return root.getOrThrow() } // 先序遍历二叉树 public static func preorderTraversal(root: Option<Node>): String { let sb = StringBuilder() preorderHelper(root, sb) return sb.toString() } private static func preorderHelper(node: Option<Node>, sb: StringBuilder): Unit { if (node.isNone()) { return } sb.append(node.getOrThrow().val) preorderHelper(node.getOrThrow().left, sb) preorderHelper(node.getOrThrow().right, sb) } }

测试代码

package Algorithm import Algorithm.bst.* main(): Int64 { // 示例输入 let deletionSequence = ["C", "B", "D", "A"] // 构建二叉树 let root = LeafDeletionSequenceToPreorder.buildTreeFromLeafDeletion(deletionSequence) // 输出先序遍历结果 let preorder = LeafDeletionSequenceToPreorder.preorderTraversal(root) println("前序遍历: " + preorder) return 0 }

二、小结

本章为大家详细的介绍了仓颉数据结构与算法中二叉查找树练习题的内容，下一章，为大家带来平衡二叉树的内容。最后，创作不易，如果大家觉得我的文章对学习仓颉数据结构与算法有帮助的话，就动动小手，点个免费的赞吧！收到的赞越多，我的创作动力也会越大哦，谢谢大家🌹🌹🌹！！！