Marge Binar Tree

[sk.Silvia]

hi there i have a problem :

so i have two tree structures New (has value 77 in left upper corner) and BinTree (is the large tree) are declared as standard tree

Delphi-Quellcode:

type TBinTree=class
      Value:integer;
      Left,Right: TBinTree;
      constructor Create(New_Value:integer; New_Left, New_Right:TBinTree); Overload;
      constructor PowerCreate(Node:TBinTree); Overload;
      ...
      end; 

  constructor TBinTree.Create(New_Value:integer; New_Left, New_Right:TBinTree);
      begin
      Value:=New_Value;
      Left:=New_Left;
      Right:=New_Right;
      end;

  constructor TBinTree.PowerCreate(Node:TBinTree);
      begin
      Self:=Node;
      end;

und ich mochte jetzt den ganzen rechten teil (.Right) von BinTree Baum mit Value=1 in den rechten teil von New baum tree stecken (2)) und dann diesen grossen New in den rechten teil (.Right) von BinTree mit Value=1 stecken, alzo eine neue node mit value=77 zwichen value=1 und value=2 erstelen, und dann will ich aber frei mit dem New tree arbeiten (wenn ich zumbeispiel New andere, mochte ich net das auch die node in BinTree geendert wird), weiss aber nich wie ich es machen soll sodas ich nicht die adresse von New in := aber eine neue node erstelle

Delphi-Quellcode:

  
procedure TEngine.Insert;
var X:TBinTree;
      begin
      X:=TBinTree.PowerCreate(NewNode);
      X.Right:=TBinTree.PowerCreate(BinTree.IsOverParentLine(Selected).Right); //BinTree.IsOverParentLine(Selected)=> Value=1
      BinTree.IsOverParentLine(Selected).Right:=TBinTree.PowerCreate(X); //ako precerpat celu nodu aj s pamatov
      end;

das geht aber nich denn immer bleibt die New node mit der node in BinTree verbunden

http://www.kolaudacia.sk/bintree.gif

[Der_Unwissende]

Hi,
excuse me, I don't know if I get you right.
Well do you want to merge some trees (lets call them t1, t2, ... tn) to a new one (tNew). But although tNew contains the nodes of t1, t2, ..., tn you want independed changes (so changing t1 does not correspond in a change of nodes in tNew)?

If so, you can't just use references (light copies by := ) but you have to make deep copies (by creating new nodes with given values).

Well of course just if I get what your problem is

Regards Der Unwissende

[sk.Silvia]

ok, lets say that t1 has only left childrens and t2 only right childrens, i want marge up t2 to t1.right so t1 is a compleate tree, but t2 stays as before, and by acting with right childrens of t1 i will act only them, not also t2...so better to say, i will insert one tree to another but i will that the inserted tree will stay separate

lets say i have a main tree called t1 with many childrens and parents...then i have a tree caled New (better to say its a node, that contains no children - the whole tree is consists only from one item)...and now i will add this New (tree-node) to t1 tree (between a parent and a child)...i was consluding it like this

will insert New between Parent and Child ->
- i set the nil child of New to Child of the Parent
- i set New as the child of the Parent (New includes the whole old Child (tree))

Thats fine, but the inserted node stays connected to New node also when i construct it, when i Set New to nil, also the inserted node (once new) set itself to nil

[marabu]

Hi Silvia,

to improve on the semantics of your code you could name your class TBinaryTreeNode - it is a node after all and only aggregating some nodes will produce a binary tree.

Since you stress the decoupling of the new node from its tree-instance, this seems not to be a coding exercise in balanced binary trees. So I present some code for you to study, that in fact is focusing on the forementioned thought of a deep copy:

Delphi-Quellcode:

unit BinTree;

interface

type
  PBinaryTreeNode = ^TBinaryTreeNode;
  TBinaryTreeNode = class
  private
    FValue: Integer;
    FLeft: TBinaryTreeNode;
    FRight: TBinaryTreeNode;
  public
    constructor Create(Value: Integer);
    function Clone(deep: Boolean = false): TBinaryTreeNode;
    property Value: Integer read FValue;
    property Left: TBinaryTreeNode read FLeft write FLeft;
    property Right: TBinaryTreeNode read FRight write FRight;
  end;

implementation

constructor TBinaryTreeNode.Create(Value: Integer);
begin
  inherited Create;
  FValue := Value;
end;

function TBinaryTreeNode.Clone(deep: Boolean = false): TBinaryTreeNode;
begin
  Result := TBinaryTreeNode.Create(FValue);
  if deep then
  begin
    if Assigned(FLeft) then
      Result.Left := FLeft.Clone(true);
    if Assigned(FRight) then
      Result.Right := FRight.Clone(true);
  end;
end;

end.

To insert a copy of node 77 you could use the following lines of code:

Delphi-Quellcode:

var
  bt77, bt1, bt77Clone: TBinaryTreeNode;  

procedure TDemoForm.ButtonClick(Sender: TObject);
begin
  bt77 := TBinaryTreeNode.Create(77);
  bt77Clone := bt77.Clone();
  bt77Clone.Right := bt1.Right;
  bt1.Right := bt77Clone;
end;

Kind regards

marabu

[sk.Silvia]

thanks for your code maribu, is i understood Clone Clone (Creates based on same value) a new node but not only the node, but it also Clone all his childrens and childrens of their childrens...cool...i will find a great use for it when extracting (cloning a part) subtree...


i solded my problems follows

i thought that by using

consturctor PowerCreate(Node:TBinTree);
begin
self=node;
end;

delphi will create a new place in memory cause its in constructor, not only link memory //i thought it creates space for variables included in self and link only to the next dynamic variable, instate of linking all