ヤン-教科書の答え

二分木のコピーコンストラクター（再帰的および非再帰的）



Copy Constructor Binary Tree Recursive



学習プロセスにおける二分木の探索-構築

二分木は、データ構造の非常に重要な章です。配列やリンクリストなどのループに依存する前の章から、難易度が少し飛躍しました。これは、二分木が再帰に関して多くのアルゴリズムを使用しているためです。 だが 二分木の本当の難しさは再帰ではなく、再帰なしで関数を実装する方法です（スタックを使用）。

1.二分木のいくつかの要素

（1）二分木のノード

二分木は非常に多くのノードで構成されているため、二分木を構築するには、大きなツリーノードを構成する部分を準備する必要があります。
ノードには、データフィールドと2つのポインタフィールド（Javaにはポインタがありませんが、関数は類似しており、後続を指します）と、コンストラクタなどの必要な関数が含まれています。
もちろん、toString関数と判定リーフノード関数は、必要に応じて他の関数を追加できます。



public class BinaryNode<T> { public T data public BinaryNode<T> left,right //Data field data and left node, right node public BinaryNode(T data,BinaryNode<T> left,BinaryNode<T> right) { this.data=data this.left=left this.right=right } public BinaryNode(T data) { this(data,null,null) } //The constructor of the node is divided into a complete structure and a structure that only assigns data fields public String toString() { return this.data.toString() } public boolean isLeaf()//Judging if it’s a leaf { return this.left==null&&this.right==null } }

（2）非再帰的メソッド用のスタックを準備します

再帰の本質は、システムがスタックを作成することです。したがって、スタックを自分で使用する場合、再帰は使用しません。 （何ですか？スタックが何であるかわかりません！ええと、スタックを挿入またはトラバースできないリンクリストとして扱うことができます。このリンクリストは、最初にテーブルの一番上にある要素に対してのみ操作できます。とアウト）
次に、スタックコードを出力します。

public final class LinkedStack<T> implements Stack<T> { private SinglyList<T> list public LinkedStack()//Constructor { this.list=new SinglyList<T>() } public boolean isEmpty()// Determine whether it is empty { return this.list.isEmpty() } public void push(T x)//Into the stack operation { this.list.insert(0,x) } public T peek()//Observe the top element of the stack { return this.list.get(0) } public T pop()//Pull operation { return this.list.remove(0) }

上記はスタックのコードです。以下に、スタックで使用されるリンクリストのコードを示します。



public class SinglyList<T> { public Node<T> head public SinglyList() { this.head=new Node<T>() } public SinglyList(T[] values) { this() Node<T> rear=this.head for(int i=0i<values.lengthi++) { rear.next=new Node<T>(values[i],null) rear=rear.next } } public boolean isEmpty() { return this.head.next==null } public T get(int i) { Node<T> p=this.head.next for(int j=0p!=null&&j<ij++) p=p.next return (i>=0&&p!=null)?p.data:null } public String toString(Node<T> p) { String str=p.toString() if(p.next!=null) { str=str+toString(p.next) } return str } @Override public String toString() { return 'SinglyList{' + 'head=' + head + '}' } public Node<T>insert (int i, T x) { if(x==null) throw new NullPointerException('X==null') Node<T> front=this.head for(int j=0front.next!=null&&j<ij++) front=front.next front.next=new Node<T>(x,front.next) return front.next } public Node<T> insert(T x) { return insert(Integer.MAX_VALUE,x) } public T remove(int i) { Node<T> front=this.head for(int j=0front.next!=null&&j<ij++) front=front.next if(i>=0&&front.next!=null) { T old=front.next.data front.next=front.next.next return old } return null } public void clear() { this.head.next=null } }

これは、リンクリストを学習したときに模倣した単一リンクリストです。機能はそれほど多くありませんが、十分です。

2.主な記事二分木の構造

（1）二分木のデータフィールド

public BinaryNode<T> root

はい、二分木ノードは1つだけです。

（2）二分木の再帰的コピーコンストラクター

public BinaryTree(BinaryTree<T> tree)//Copy constructor { root=create(tree.root) } private BinaryNode<T> create(BinaryNode<T> node)// recursion { BinaryNode<T> head=null if(node!=null) { head=new BinaryNode<T>(node.data) head.left=create(node.left) head.right=create(node.right) } return head }

再帰、自分自身を呼び出してください。パラメータは簡単に変更できる必要があります。ツリーは煩雑すぎてノードは満足しているだけなので、当然2つの関数があります。1つはバイナリツリーのコピーコンストラクター本体で、1回しか実行できません。もう1つは当然、再帰する（自分自身を呼び出す）ためのパラメーターとして二分木ノードを受け取る本体です。
再帰コンストラクターのアルゴリズムがどのように実装されているかを分析してみましょう。



  1. コピーによって構築されたツリーが空かどうかを判断し、空の場合はnull（空のツリー）を返し、空でない場合はノードを作成しましょう
    。 画像

  2. ノード1の左ノードを作成し、コピーして作成されたツリーの左下隅まで、作成されたノードの左ノードを作成し続けます。
    画像
    コピーされたツリーのノード3がリーフノード（左ノードも右ノードもなし）であるとすると、ノード3の左右のノードcreateは、それ自体を呼び出さずにnull値を返し、create（ノード）を実行します。 riegt）ノード2を作成するとき。
    画像
    ノード4を作成すると、ノード2のすべての作成ステートメントが完了し、ノード2からノード1のcreate（node.right）などに戻ります。
    上記は再帰的方法の分析です。最初に最後まで作成してから、ゆっくりと戻ります。次のノードが作成されたら、前のノードの作成（node.right）に戻るか、もう一度上に戻ります。

（3）二分木の非再帰的コピーコンストラクター

二分木の非再帰的コピーコンストラクターは、2つのスタックを使用します。1つはコピーされたツリーをスタックとともにトラバースし、もう1つはコピーされるツリーのノードを格納します。まず、以下のコードを入力します。

private BinaryNode<T> othercreate(BinaryNode<T> node)// Non-recursive copy constructor { BinaryNode<T> temp=null//Used to store the created node LinkedStack<BinaryNode<T>> stack1=new LinkedStack<BinaryNode<T>>() LinkedStack<BinaryNode<T>> stack2=new LinkedStack<BinaryNode<T>>() if(node==null)//Determine whether the copied tree is empty { return null } temp=new BinaryNode<T>(node.data)Create the root node of the copied tree first root=temp stack1.push(node)//Into the stack stack2.push(temp)//Into the stack while(!stack1.isEmpty()) { if(node.left!=null) { node=node.left temp.left=new BinaryNode<T>(node.data) temp=temp.left stack1.push(node) stack2.push(temp) } else if(node.right!=null) { node=node.right temp.right=new BinaryNode<T>(node.data) temp=temp.right stack1.push(node) stack2.push(temp) } else { while(!stack1.isEmpty()&&(stack1.peek().right==null||stack2.peek().right!=null)) { stack1.pop() stack2.pop() } if(!stack1.isEmpty()) { node=stack1.peek().right temp=new BinaryNode<T>(node.data) stack2.peek().right=temp stack1.push(node) stack2.push(temp) } } } return root }

分析：

  1. まず、コピーしたツリーが空かどうかを判断します。空の場合は空のツリーを返します。空でない場合は、コピーされたツリーのルートノードが作成され、作成されたノードとコピーされたツリーのルートノードがスタックにプッシュされます。
    画像

  2. 次に、このノードに左の子ノードがあるかどうかを確認します。存在する場合は作成してスタックにプッシュし、存在しない場合は正しいノードがあるかどうかを確認し、作成してスタックにプッシュします。
    画像

  3. ノードがリーフノードに到達すると、次にポップされます。次の操作ですか

while(!stack1.isEmpty()&&(stack1.peek().right==null||stack2.peek().right!=null)) { stack1.pop() stack2.pop() } if(!stack1.isEmpty()) { node=stack1.peek().right temp=new BinaryNode<T>(node.data) stack2.peek().right=temp stack1.push(node) stack2.push(temp)

ここでの判断は、次の3つの状況に対処することです。

  1. 空のスタックが構築されました。
  2. コピーされたツリーには、現時点では適切な子ノードがないため、スタックから再度ポップされます。
  3. コピーされたツリーはすでに適切なノードを確立しています。これは、無制限のループが作成されたツリーの適切な子ノードを作成しないようにするために行われているため、スタックからポップアウトし続けます。

以下は自然に飛び出します。ポップされた要素はすでに作成されており、左側のノードがあるため、自信を持って右側のノードに割り当てることができます。ただし、スタックが空であるために終了する場合もありますが、この時点でコピーは完了しており、当然、適切なノード割り当て操作を実行する必要はありません。したがって、if判定を追加します。

要約すると、2つのスタックの要素は同じです。 1つのスタックは、コピーされたコンストラクターをトラバースするために使用され、もう1つのスタックは自然に作成されます。もちろん、再帰的に書くのは本当に簡単です。スタックを使用するよりもはるかに便利であり、再帰をお勧めします。
最後に、私が書いた二分木のすべてのコードを入れます。

public class BinaryTree<T> { public BinaryNode<T> root public BinaryTree() { this.root=null } public BinaryTree(BinaryTree<T> tree)//Copy constructor { root=othercreate(tree.root) } private BinaryNode<T> crate(BinaryNode<T> node)// recursion { BinaryNode<T> head=null if(node!=null) { head=new BinaryNode<T>(node.data) head.left=crate(node.left) head.right=crate(node.right) } return head } private BinaryNode<T> othercreate(BinaryNode<T> node)// Non-recursive copy constructor { BinaryNode<T> temp=null LinkedStack<BinaryNode<T>> stack1=new LinkedStack<BinaryNode<T>>() LinkedStack<BinaryNode<T>> stack2=new LinkedStack<BinaryNode<T>>() if(node==null) { return null } temp=new BinaryNode<T>(node.data) root=temp stack1.push(node) stack2.push(temp) while(!stack1.isEmpty()) { if(node.left!=null) { node=node.left temp.left=new BinaryNode<T>(node.data) temp=temp.left stack1.push(node) stack2.push(temp) } else if(node.right!=null) { node=node.right temp.right=new BinaryNode<T>(node.data) temp=temp.right stack1.push(node) stack2.push(temp) } else { while(!stack1.isEmpty()&&(stack1.peek().right==null||stack2.peek().right!=null)) { stack1.pop() stack2.pop() } if(!stack1.isEmpty()) { node=stack1.peek().right temp=new BinaryNode<T>(node.data) stack2.peek().right=temp stack1.push(node) stack2.push(temp) } } } return root } public boolean isEmpty() { return this.root==null } public BinaryNode<T> insert(T x)//Insert x as the root node and the original node as the left child of x return the inserted node { return this.root=new BinaryNode<T>(x,this.root,null) } public BinaryNode<T> insert(BinaryNode<T> parent,T x,boolean leftChild) { if(x==null) return null if(leftChild) return parent.left=new BinaryNode<T>(x,parent.left,null) return parent.right=new BinaryNode<T>(x,null,parent.right) }//Insert a node after the parent node is given without using recursion public void remove(BinaryNode<T> parent,boolean leftChild) { if(leftChild) parent.left=null else parent.right=null }//Delete a subtree public void clear() { this.root=null }//Empty the entire tree public void preorder() { preorder(this.root) System.out.println() } private void preorder(BinaryNode<T> p) { if(p!=null) { System.out.print(p.data.toString()+' ') preorder(p.left) preorder(p.right) } }//First root traverse the binary tree public void inorder() { inorder(root) System.out.println() } private void inorder(BinaryNode<T> node) { if(node!=null) { inorder(node.left) System.out.print(node.data.toString()+' ') inorder(node.right) } }//The middle root traverses the binary tree public void afterorder() { afterorder(root) System.out.println() } private void afterorder(BinaryNode<T> node) { if(node!=null) { afterorder(node.left) afterorder(node.right) System.out.print(node.data.toString()+' ') } }//After root traversal public String toString() { return toString(root) } private String toString(BinaryNode<T> node) { if(node!=null) { return node.data.toString()+' '+toString(node.left)+toString(node.right) } return '' } //First root traversal returns toString public int size() { return size(root) } private int size(BinaryNode<T> node) { if(node==null) return 0 return 1+size(node.left)+size(node.right) }//Return the number of nodes in the binary tree public int height() { return height(root) } public int height(BinaryNode<T> node) { int ldep=0 int rdep=0 if (node==null) return 0 if(node!=null) { ldep=height(node.left) rdep=height(node.right) } if(ldep>rdep) return ldep+1 return rdep+1 } }