Tùy chọn khác, dựa trên thực hiện Thay thế lười. Nếu nó là hiệu suất quan trọng và sẽ có rất nhiều thay đổi được thực hiện cho nó, tôi sẽ đề nghị điểm chuẩn nó.
Tôi đã thực hiện nó trong F #, tuy nhiên tôi không nghĩ rằng tôi đã sử dụng bất cứ điều gì "inpure" ngoại trừ chức năng in ấn của tôi.
Đây là một chút tường của văn bản, Nguyên tắc cơ bản là giữ cho cây Lười biếng, thay thế các nút bằng cách thay thế hàm trả về nút.
Bí quyết là bạn cần một số cách để xác định một nút, đó không phải là tham chiếu/tên riêng của nó và không theo giá trị. Việc nhận diện phải trùng lặp trên ReplaceNodes Trong trường hợp này, tôi đã sử dụng System.Object vì chúng có liên quan riêng biệt.
type TreeNode<'a> = {
getChildren: unit -> seq<TreeNode<'a>>;
value: 'a;
originalRefId: System.Object; //This is set when the onject is created,
// so we can identify any nodes that are effectivly this one
}
let BasicTreeNode : 'a ->seq<TreeNode<'a>>-> TreeNode<'a> = fun nodeValue -> fun children ->
{value = nodeValue; originalRefId = System.Object(); getChildren = fun() -> children;}
let rec ReplacementNode : TreeNode<'a> -> TreeNode<'a> -> TreeNode<'a> -> TreeNode<'a> =
fun nodeToReplace -> fun newNode -> fun baseNode ->
if (System.Object.ReferenceEquals(baseNode.originalRefId, nodeToReplace.originalRefId)) then
//If it has the same Oringal
newNode //replace the node
else
//Just another pass on node, tranform its children, keep orignial reference
{value = baseNode.value;
originalRefId = baseNode.originalRefId;
getChildren = fun() ->
baseNode.getChildren() |> Seq.map(ReplacementNode nodeToReplace newNode); }
type TreeType<'a> = {
Print: unit -> unit;
ReplaceNode: TreeNode<'a> -> TreeNode<'a> -> TreeType<'a>;
//Put all the other tree methods, like Traversals, searches etc in this type
}
let rec Tree = fun rootNode ->
{
Print = fun() ->
let rec printNode = fun node -> fun depth ->
printf "%s %A\n" (String.replicate depth " - ") node.value
for n in node.getChildren() do printNode n (depth + 1)
printNode rootNode 0
;
ReplaceNode = fun oldNode -> fun newNode ->
Tree (ReplacementNode oldNode newNode rootNode)
}
Test Case/Ví dụ:
let e = BasicTreeNode "E" Seq.empty
let d = BasicTreeNode "D" Seq.empty
let c = BasicTreeNode "C" Seq.empty
let b = BasicTreeNode "B" [d;e]
let a = BasicTreeNode "A" [b;c]
let originalTree = Tree a
printf "The Original Tree:\n"
originalTree.Print()
let g = BasicTreeNode "G" Seq.empty
let newE = BasicTreeNode "E" [g]
let newTree = originalTree.ReplaceNode e newE
printf "\n\nThe Tree with a Local Change: \n"
newTree.Print()
printf "\n\nThe Original Tree is Unchanged: \n"
originalTree.Print()
printf "\n\nThe Tree with a Second Local Change: \n"
let h = BasicTreeNode "H" Seq.empty
let newC = BasicTreeNode "C" [h]
let newTree2 = newTree.ReplaceNode c newC
newTree2.Print()
printf "\n\nTrying to Change a node that has been replaced doesn't work \n"
let i = BasicTreeNode "i" Seq.empty
let newnewC = BasicTreeNode "C" [h; i]
let newTree3 = newTree.ReplaceNode c newC //newTree.ReplaceNode newc newnewC would work
newTree3.Print()
Chúng ta đã thấy ở phần cuối của bài kiểm tra đó sử dụng một Tên cũ nút (/ tài liệu tham khảo) cho đối tượng bị thay thế không hoạt động. còn có tùy chọn của việc tạo ra một loại mới có tài liệu tham khảo Id của nút khác:
//Like a basicTreeNode, but reuses an existing ID, so they can be replaced for oneanother
let EdittedTreeNode = fun orignalNode -> fun nodeValue -> fun children ->
{value = nodeValue; originalRefId = orignalNode.originalRefId; getChildren = fun() -> children;}
Bạn cũng có thể chỉnh sửa định nghĩa ReplacementNode, để nó duy trì ID, của nút nó thay thế. (Bằng cách không chỉ trở newNode, thay vì trở về thêm một nút mới mà có value, và getChildren của newNode, nhưng originalRefId của nodetoReplace)
Dưới đây là một liên kết cho những người như tôi, những người không biết những gì một "dây kéo" là trong ngữ cảnh này: http://tomasp.net/blog/tree-zipper-query.aspx –