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

Question

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

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;

Answer 1

答案简单明了，如您所愿。（双关语）你事先决定你喜欢哪种遍历方法。 Child 先还是自己先。然后你进行遍历，设置链接。基本上，您可以同时实现树和链表。

更难的问题是让野兽保持平衡。有一个链表和一个节点数对此有很大帮助。提示，我会使用递归函数找到列表的中间部分，使之成为新的叶节点（如果不存在节点则为根节点），然后 trim self 从临时左链和临时右链中取出.在每条临时链上调用函数获得child个节点。

对于大多数不涉及搜索优化的实现，您将要指向 parent 而不是让节点指向 children。对于给定的 parent，这允许任意 n 个 children。如果需要，您可以将 child 列表设为参差不齐的数组或链表。所以最后你会结合搜索链和其他数据结构来得到你的结果。

当然，要问自己的另一件事是实施是否保证将所有内容都保存在内存中。很多时候，让数据库完成工作要好得多，如果它就在它所在的位置。

祝你好运。好问题。

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

How to convert tree to threaded binary tree

delphi

tree

binary-tree

pointers

binary-search-tree