如何将树转换为线程化二叉树

-2

我有一个用于创建二叉树及其递归输出的代码。如何将二叉树转换为线程树并迭代打印？如何将树转换为线程化二叉树

type 
    PAvl = ^TAvl; 
    TAvl = record 
      key: integer; 
      left: PAvl; 
      right: PAvl; 
      isThreaded: boolean; 
     end; 

procedure create(var root: PAvl; digit: integer); 
begin 
    if root = nil then begin 
    New(root); 
    root^.key := digit; 
    root^.left := nil; 
    root^.right := nil; 
    end 
    else if root.key > digit then 
    create(root.left, digit) 
    else 
    create(root.right, digit); 
end; 

procedure Print(root: PNode; depth: integer = 0); 
var 
    i: integer; 
begin 
    if root <> nil then 
    begin 
    Print(root^.right, depth + 1); 
    for i:=1 to depth do 
     Write(#9); 
    Writeln(root^.data); 
    Print(root^.left, depth + 1); 
    end; 
end;

来源

2016-05-30 Alexander Dimov

维基百科有一个很好的解释：https://en.wikipedia.org/wiki/Threaded_binary_tree – Johan

代码不是真实的，只是来自两个来源的混合。 – MBo

答案与您所做的一样简单直接。（双关意图）你可以事先决定你喜欢哪种遍历方法。孩子第一或自我第一。然后你做遍历，建立链接。基本上你有一个树和一个链表实现。

更难的问题是保持野兽的平衡。有一个链表和节点数有助于这一点。提示，我将使用递归函数来查找列表的中间部分，使新叶节点（或者如果没有节点存在，则为root），然后将自身从临时左侧链和临时右侧链中删除。调用每个临时链上的函数以获取子节点。

对于大多数不涉及搜索优化的实现，您将希望指向父代，而不是让节点指向子代。这允许给定父母的任何n个孩子。如果需要，可以将子列表设置为不齐整的数组或链表。所以最后你会将搜索链与其他数据结构结合起来以得到你的结果。

当然，另一个问问自己的是实施是否保证将所有内容都保存在内存中。很多时候，如果数据库存在的话，让数据库完成这项工作会更好。

祝福。好问题。

来源

2016-05-31 12:02:47 Michael

如何将树转换为线程化二叉树

回答

相关问题