Netjava Lesson 12ツリー

2013.07.31
 
授業内容:ツリー
 
まず、前の授業の内容を振り返ってみましょう.前の授業ではチェーン時計を話していました.デュアルチェーンテーブルの各ノードは,データを格納する3つの部分,および前のノードのアドレスと次のノードのアドレスをそれぞれ格納する3つの部分から構成されることが分かった.では、今日お話しするツリーは、デュアルチェーンテーブルのノードと同じ構成ですが、データ部分を格納するほか、このノードをルートノードとする左サブツリーと右サブツリーのアドレスをそれぞれ格納しています.二叉木とチェーンテーブルの最大の違いは、チェーンテーブルがチェーンであり、特殊な二叉木であり、二叉木は木のように根と葉を持っていることだ.
 
次に、具体的には、ツリーについて説明します.まず、ツリーにはルートノードと呼ばれる最上位のノードがあり、ルートノードの下には葉ノードと呼ばれるノードがたくさんあります.各ノードには、データとその左右のサブツリーのアドレスが格納され、なければnullになります.ツリーとツリーの最大の違いは、ツリーがノードごとに2つのフォークしか開かないことであり、私たちの生活の中のツリーは複数のフォークを開くことができ、ツリーの特例と言える.
二叉木の遍歴方式:前序遍歴、中序遍歴、後序遍歴、深さ優先遍歴、広さ優先遍歴、層序遍歴.ここでは、前の3つの比較的基本的な遍歴方式を紹介します.前の遍歴、中の遍歴、後の遍歴です.前の順序:ルートノードを先に巡回し、左ノードを巡回し、最後に右ノードを巡回します.ルートノードの下の左ノードにサブツリーがある場合は、ルートノードとして同じルールでサブツリーを巡ります.前序遍歴は3つの字で精巧に概括することができる:根左右.同じように、中序遍歴:左根右、後序遍歴:左右根を要約することもできます.
 
理論は総じて理論であり、実践してこそ真の知識を得ることができ、次に二叉木を始めます.まず、ノードクラスを構築します.

public class Node {
	private int data;//      
	private Node left;//    
	private Node right;//    

	/**
	 *     
	 * 
	 * @param data      
	 */
	public Node(int data) {
		this.data = data;
	}

	/**
	 *     
	 * 
	 * @param data      
	 * @param left   
	 * @param right   
	 */
	public Node(int data, Node left, Node right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public Node getLeft() {
		return left;
	}

	public void setLeft(Node left) {
		this.left = left;
	}

	public Node getRight() {
		return right;
	}

	public void setRight(Node right) {
		this.right = right;
	}
}

 
ノードクラスを作成し、ノードの追加、ノードの削除、および3つのループを含むツリーの構築を開始します.

public class NodeTree {

	private Node root;//    

	/**
	 *       
	 * 
	 * @param node       
	 */
	public void add(Node node) {
		//        
		if (root == null) {
			//  node      
			root = node;
		} else {
			//           
			querynode(root, node);
		}
	}

	/**
	 *         
	 * 
	 * @param root   
	 * @param node    
	 * @return
	 */
	public boolean remove(Node root, Node node) {
		//            
		if (root == node) {
			//        
			root = null;
		} //        ，  true
		else if (findnode(root, node)) {
			return true;
		}
		//      ，  false
		return false;
	}

	/**
	 *       
	 * 
	 * @param node1   
	 * @param node2     
	 * @return
	 */
	public boolean findnode(Node node1, Node node2) {
		//           
		if (node1.getLeft() != null) {
			//            
			if (node1.getLeft() == node2) {
				//            ，   true
				node1.setLeft(null);
				return true;
			}//   ，        
			else {
				findnode(node1.getLeft(), node2);
			}
		}
		//           
		if (node1.getRight() != null) {
			//            
			if (node1.getRight() == node2) {
				//            ，   true
				node1.setRight(null);
				return true;
			}//   ，        
			else {
				findnode(node1.getRight(), node2);
			}
		}
		return false;
	}

	/**
	 *        
	 * 
	 * @param node1   
	 * @param node2      
	 */
	public void querynode(Node node1, Node node2) {
		//            
		if (node1.getData() < node2.getData()) {
			//                ，      
			if (node1.getRight() != null) {
				querynode(node1.getRight(), node2);
			} else {
				//       ，       
				node1.setRight(node2);
			}
		} else {
			//                ，      
			if (node1.getLeft() != null) {
				querynode(node1.getLeft(), node2);
			} else {
				//       ，       
				node1.setLeft(node2);
			}
		}
	}

	/**
	 *     
	 * 
	 * @param node   
	 */
	public void preorder(Node root) {
		//           
		if (root != null) {
			//      
			visit(root);
			//       
			preorder(root.getLeft());
			//      
			preorder(root.getRight());
		}
	}

	/**
	 *     
	 * 
	 * @param root   
	 */
	public void inorder(Node root) {
		if (root != null) {
			//         
			if (root.getLeft() != null) {
				//       
				inorder(root.getLeft());
			}
			//      
			visit(root);
			//         
			if (root.getRight() != null) {
				//       
				inorder(root.getRight());
			}
		}
	}

	/**
	 *     
	 * 
	 * @param root   
	 */
	public void postorder(Node root) {
		if (root != null) {
			//         
			if (root.getLeft() != null) {
				//       
				postorder(root.getLeft());
			}
			//         
			if (root.getRight() != null) {
				//       
				postorder(root.getRight());
			}
			//      
			visit(root);
		}
	}

	/**
	 *      
	 * 
	 * @return    
	 */
	public Node getRoot() {
		return root;
	}

	/**
	 *     
	 * 
	 * @param node       
	 */
	public void visit(Node node) {
		//      data
		System.out.print(node.getData() + " ");
	}
}

 
これで二叉樹の構築が完成し、勉強していない前は複雑な感じがしましたが、努力を通じて想像していたほど難しくないと思います.できないことを恐れず、問題に驚かされるのを恐れています.同志たち、努力しましょう.