WOLFRAM

Wolfram 语言与系统参考资料中心

"BinaryTree" （数据结构）

"BinaryTree"

表示一个可变的二叉树，其中存储在每个节点上的值为普通表达式.

更多信息

  • 二叉树可基于与每个节点关联的数据访问节点，以及表示最多有两个分支的层级关系：
  • CreateDataStructure["BinaryTree",v]创建具有指定初始值 v 和空的左子树和右子树的新的 "BinaryTree"
    CreateDataStructure["BinaryTree",v{l,r}]创建具有指定初始值 v 和指定左子树和右子树的新的 "BinaryTree"
    Typed[x,"BinaryTree"]指定 x 的类型为 "BinaryTree"
  • 对于类型为 "BinaryTree" 的数据结构，可进行以下操作：
  • ds["BreadthFirstScan",f]对 ds 执行广度优先扫描，将每个节点的数据传递给 f时间：O(n)
    ds["Copy"]返回 ds 的副本时间：O(n)
    ds["Data"]返回存储在节点 ds 的数据时间：O(1)
    ds["InOrderScan",f]对 ds 执行中序扫描，将每个节点的数据传递给 f时间：O(n)
    ds["Left"]返回 ds 的左子树的数据结构时间：O(1)
    ds["LeftNullQ"]如果 ds 的左子树为空则返回 True时间：O(1)
    ds["NullQ"]如果 ds 为空则返回 True时间：O(1)
    ds["PostOrderScan",f]对 ds 执行后序扫描，将每个节点的数据传递给 f时间：O(n)
    ds["PreOrderScan",f]对 ds 执行前序扫描，将每个节点的数据传递给 f时间：O(n)
    ds["Right"]返回 ds 的右子树的数据结构时间：O(1)
    ds["RightNullQ"]如果 ds 的右子树为空则返回 True时间：O(1)
    ds["SetData",v]将存储在节点 ds 的数据设为 v时间：O(1)
    ds["SetLeft",l]将节点 ds 的左子树设为 l时间：O(1)
    ds["SetRight",r]将节点 ds 的右子树设为 r时间：O(1)
    ds["ValidQ"]如果 ds 是有效的树则返回 True时间：O(n)
    ds["Visualization"]返回 ds 的可视化时间：O(n)
  • 还支持以下函数：
  • dsi===dsj如果 dsi 等于 dsj 则为 True
    FullForm[ds]ds 的完全形式
    Information[ds]关于 ds 的信息
    InputForm[ds]ds 的输入形式
    Normal[ds]将 ds 转换成普通表达式

范例

打开所有单元 关闭所有单元

基本范例  (2)

可用 CreateDataStructure 创建新的 "BinaryTree"：

Wolfram Language code: ds = CreateDataStructure["BinaryTree", 10]

提取其中存储的值：

Wolfram Language code: ds["Data"]

插入要存储的新值：

Wolfram Language code: ds["SetData", 12]

确认值已更新：

Wolfram Language code: ds["Data"]

左子树为空：

Wolfram Language code: ds["LeftNullQ"]

右子树为空：

Wolfram Language code: ds["RightNullQ"]

用指定的子树创建新的 "BinaryTree"：

Wolfram Language code: ds = CreateDataStructure["BinaryTree", 1 -> {2 -> {5, Null}, 8}]

有左子树：

Wolfram Language code: ds["LeftNullQ"]

返回左子树：

Wolfram Language code: ds["Left"]

返回表达式形式的 ds：

Wolfram Language code: Normal[ds]

可视化数据结构：

Wolfram Language code: ds["Visualization"]

范围  (1)

信息  (1)

可用 CreateDataStructure 创建新的 "BinaryTree"：

Wolfram Language code: ds = CreateDataStructure["BinaryTree", f[1]]

数据结构 ds 的信息：

Wolfram Language code: Information[ds]

应用  (7)

二叉搜索树  (1)

二叉树的一种用途是用于存储有序的内容. 通常，通常被称为二叉搜索树. 下面是一个简单的插入程序：

Wolfram Language code: insert[node_, d_] := With[{curr = node["Data"]}, Which[ d < curr, If[node["LeftNullQ"], node["SetLeft", CreateDataStructure["BinaryTree", d]], insert[node["Left"], d]] , d > curr, If[node["RightNullQ"], node["SetRight", CreateDataStructure["BinaryTree", d]], insert[node["Right"], d]] ] ]

创建一棵二叉树并插入 30 个随机数：

Wolfram Language code: ds = CreateDataStructure["BinaryTree", 50]; Scan[insert[ds, #]&, RandomInteger[{0, 500}, 30]];
Wolfram Language code: ds["Visualization"]

下面对树进行中序扫描. 由于树已排序，因此按排好的顺序访问元素，如本例所示：

Wolfram Language code: arr = CreateDataStructure["DynamicArray"];ds["InOrderScan", arr["Append", #]&]; arr//Normal

这种基本二叉搜索树的问题是插入链可能变得不平衡，从而树的最大深度变大. 各种形式的平衡二叉树可以纠正此问题.

树旋转  (1)

对排好序的二叉树进行树旋转涉及在保持元素顺序的同时改变树的结构. 许多技术用旋转来创建平衡二叉树.

下面显示了一些基本的左右树旋转操作：

Wolfram Language code: RightRotate[y_] := Module[{x, tmp}, x = y["Left"]; tmp = x["Right"]; x["SetRight", y]; y["SetLeft", tmp]; x]
Wolfram Language code: LeftRotate[x_] := Module[{y, tmp}, y = x["Right"]; tmp = y["Left"]; y["SetLeft", x]; x["SetRight", tmp]; y]

下面创建一个二叉树. 注意，它在左侧有两个层级的节点，在右侧没有. 这种存储结构效率低下：

Wolfram Language code: ds = CreateDataStructure["BinaryTree", 3 -> {1 -> {0, Null}, Null}]; ds["Visualization"]

进行右旋转，将节点移到右边，保持排好的顺序，使树的结构更平衡：

Wolfram Language code: ds = RightRotate[ds]; ds["Visualization"]

进行左旋转，将节点移回到左边，保持排好的顺序：

Wolfram Language code: ds = LeftRotate[ds]; ds["Visualization"]

RandomTree  (1)

将随机节点插入二叉树的指定深度的程序：

Wolfram Language code: InsertRandom[node_, lim_] := Module[ {test, newNode}, test = RandomChoice[ {Left, Right, All}]; If[ (test === Left || test === All) && lim ≥ 0, newNode = CreateDataStructure["BinaryTree", 1]; node["SetLeft", newNode]; InsertRandom[newNode, lim - 1]]; If[(test === Right || test === All) && lim ≥ 0, newNode = CreateDataStructure["BinaryTree", 1]; node["SetRight", newNode]; InsertRandom[newNode, lim - 1]]; node ]
Wolfram Language code: ds = InsertRandom[CreateDataStructure["BinaryTree", 1], 4]
Wolfram Language code: ds["Visualization"]

计算二叉树的最大深度  (1)

二叉树的最大深度是从根节点到叶节点的最长路径上节点的数量.

计算二叉树的最大深度的程序：

Wolfram Language code: MaximumDepth[tree_] := If[tree["NullQ"], 0, Max[MaximumDepth[tree["Left"]], MaximumDepth[tree["Right"]]] + 1 ]

样例树：

Wolfram Language code: tree = CreateDataStructure["BinaryTree", 1 -> {2 -> {5 -> {7 -> {8, Null}, Null}, Null}, 2 -> {Null, 5}}]; tree["Visualization"]

最大深度：

Wolfram Language code: MaximumDepth[tree]

求最近公共祖先  (1)

树中两个节点的最近公共祖先是将两个节点都作为后代的最低（或最深）的节点. 可以使用一些简单的代码进行计算.

将随机节点插入树中的程序. 使用计数器来确保所有节点都是不同的：

Wolfram Language code: InsertRandom[node_, cnt_, lim_] := Module[ {test, newNode}, test = RandomChoice[ {Left, Right, All}]; If[ (test === Left || test === All) && lim ≥ 0, newNode = CreateDataStructure["BinaryTree", cnt["Increment"]]; node["SetLeft", newNode]; InsertRandom[newNode, cnt, lim - 1]]; If[(test === Right || test === All) && lim ≥ 0, newNode = CreateDataStructure["BinaryTree", cnt["Increment"]]; node["SetRight", newNode]; InsertRandom[newNode, cnt, lim - 1]]; node ]

设置随机种子以获得可重现的例子：

Wolfram Language code: SeedRandom[ 14]

创建随机树并可视化：

Wolfram Language code: tree = InsertRandom[CreateDataStructure["BinaryTree", 0], CreateDataStructure["Counter", 1], 7]; tree["Visualization"]

求最近公共祖先的程序：

Wolfram Language code: LowestCommonAncestor[tree_, left_Integer, right_Integer] := Which[ tree["NullQ"], tree, tree["Data"] === left, tree, tree["Data"] === right, tree, True, Module[{sleft, sright}, sleft = LowestCommonAncestor[tree["Left"], left, right]; sright = LowestCommonAncestor[tree["Right"], left, right]; Which[ sleft["NullQ"], sright, sright["NullQ"], sleft, True, tree ] ] ]

求最近公共祖先：

Wolfram Language code: LowestCommonAncestor[tree, 15, 20]["Data"]

可视化是验证答案的好方法：

Wolfram Language code: LowestCommonAncestor[tree, 15, 20]["Visualization"]

测试二叉树是否是对称的  (1)

如果二叉树的中间竖直向下有一个对称平面，则它是对称的.

下面的程序测试二叉树是否对称. 该程序检查数据是否相等以及左右节点是否对称：

Wolfram Language code: SymmetricTreeQ[tree_] := SymmetricTreeQ[tree["Left"], tree["Right"]] SymmetricTreeQ[x_, y_] := Which[ x["NullQ"] && y["NullQ"], True, x["NullQ"] || y["NullQ"], False, True, x["Data"] == y["Data"] && SymmetricTreeQ[x["Left"], y["Right"]] && SymmetricTreeQ[x["Right"], y["Left"]] ]

不对称的树：

Wolfram Language code: tree = CreateDataStructure["BinaryTree", 1 -> {2 -> {5, Null}, 8}];tree["Visualization"]

验证该树是不对称的：

Wolfram Language code: SymmetricTreeQ[tree]

对称的树：

Wolfram Language code: tree = CreateDataStructure["BinaryTree", 1 -> {2 -> {5, Null}, 2 -> {Null, 5}}]; tree["Visualization"]

验证该树是对称的：

Wolfram Language code: SymmetricTreeQ[tree]

求二叉树的直径  (1)

二叉树的直径是任何两个节点之间（可能通过也可能不通过根）最长路径的长度.

下面的程序计算二叉树的直径：

Wolfram Language code: BinaryTreeDiameter[tree_] := Module[{diameter}, diameter = CreateDataStructure["Value", 1]; BinaryTreeDepth[diameter, tree]; diameter["Get"] - 1 ] BinaryTreeDepth[diameter_, tree_] := Module[{left, right}, If[tree["NullQ"], Return[0]]; left = BinaryTreeDepth[diameter, tree["Left"]]; right = BinaryTreeDepth[diameter, tree["Right"]]; diameter["Set", Max[diameter["Get"], left + right + 1]]; Max[left, right] + 1 ]

样例树：

Wolfram Language code: tree = CreateDataStructure["BinaryTree", 1 -> {2 -> {5, Null}, 2 -> {Null, 5}}]; tree["Visualization"]

计算直径：

Wolfram Language code: BinaryTreeDiameter[tree]

另一个样例树：

Wolfram Language code: tree = CreateDataStructure["BinaryTree", 1 -> {2 -> {5 -> {7 -> {8, Null}, Null}, Null}, 2 -> {Null, 5}}]; tree["Visualization"]

计算直径：

Wolfram Language code: BinaryTreeDiameter[tree]

可能存在的问题  (2)

空的节点  (1)

用一些数据创建二叉树：

Wolfram Language code: ds = CreateDataStructure["BinaryTree", 10]

提取右子树：

Wolfram Language code: rChild = ds["Right"]

这是一个空节点：

Wolfram Language code: rChild["NullQ"]

对空节点的内容进行操作会出现错误：

Wolfram Language code: rChild["Data"]

空节点序列化的结果为 Null：

Wolfram Language code: InputForm[ rChild]
Wolfram Language code: DataStructure["BinaryTree", {"Data" -> Null}]

用 CreateDataStructure 创建空节点：

Wolfram Language code: CreateDataStructure["BinaryTree", Null]["NullQ"]
Wolfram Language code: CreateDataStructure["BinaryTree"]["NullQ"]

空节点的 Wolfram 语言表示非常有用，因为它允许编写算法来对二叉树的节点进行操作，而不必检查它们是否为空l.

有效的树  (1)

Wolfram 语言与二叉树的接口应灵活高效. 这将影响创建的结构.

用一些数据创建二叉树：

Wolfram Language code: ds = CreateDataStructure["BinaryTree", 10]

创建另一个树，并将其作为右子树：

Wolfram Language code: ds1 = CreateDataStructure["BinaryTree", 20]; ds["SetRight", ds1]; ds["Visualization"]

现在，使得右子树与父树相等：

Wolfram Language code: ds1["SetRight", ds];

结果将不再是一个树. 通过 "ValidQ" 即可确认：

Wolfram Language code: ds["ValidQ"]

如果不是有效的树，某些操作会给出错误：

Wolfram Language code: ds//Normal

当创建无效的结构时，插入函数不会给出错误，因为这会降低效率. 如序列化数据结构之类的操作内置有检查机制.