二元ツリーで値のすべてのパスを見つけてjavaバージョン


4.ある値に対するすべてのパスを二元ツリーで検索します.
タイトル:整数と二元ツリーを入力します.
ツリーのルートノードからリーフノードまでのすべてのノードにアクセスしてパスを形成します.
入力した整数に等しいすべてのパスを印刷します.
例えば、整数22と次のような二元ツリーを入力する
10
/\
5 12
/\
4 7
10、12、10、5、7の2つのパスが印刷されます.
ツリーノードのデータ構造は、次のように定義されます.
struct BinaryTreeNode//a node in the binary tree
{
int m_nValue;//value of node
BinaryTreeNode *m_pLeft;//left child of node
BinaryTreeNode *m_pRight;//right child of node
};

/**
 * 
 */
package com.lhp;

import java.util.ArrayList;
import java.util.List;

/**
	4.                 
	  :            。
	                                。
	                。
	      22       
	10
	/ \
	5 12
	/\
	4 7
	        :10, 12  10, 5, 7。
	             :
	struct BinaryTreeNode // a node in the binary tree
	{
	int m_nValue; // value of node
	BinaryTreeNode *m_pLeft; // left child of node
	BinaryTreeNode *m_pRight; // right child of node
	};
 */
 
/**
 *    
 */
class BinaryTree {
	private BinaryTreeNode root;	//  

	public BinaryTreeNode getRoot() {
		return root;
	}

	public void setRoot(BinaryTreeNode root) {
		this.root = root;
	}
	
	/**
	 *      
	 * @param   
	 */
	public synchronized void addNode(BinaryTreeNode node) {
		if (null == this.root) {
			this.root = node;
			return;
		}
		
		BinaryTreeNode tempNode = this.root;
		
		while (true) {
			if (node.getM_nValue() > tempNode.getM_nValue()) {	//      
				if (null == tempNode.getM_pRight()) {
					tempNode.setM_pRight(node);
					return;
				} else {
					tempNode = tempNode.getM_pRight();
					continue;
				}
			} else if (node.getM_nValue() < tempNode.getM_nValue()) {	//      
				if (null == tempNode.getM_pLeft()) {
					tempNode.setM_pLeft(node);
					return;
				} else {
					tempNode = tempNode.getM_pLeft();
					continue;
				}
			} else {	//      
				return;
			}
		}
	}
	
	/**
	 *               
	 * @param     
	 */
	public synchronized void printSumPath(int sumValue) {
		printSumPath(this.root, new ArrayList<Integer>(), 0, sumValue);
	}
	
	/**
	 * @param   
	 * @param       
	 * @param       
	 * @param     
	 */
	private void printSumPath(BinaryTreeNode node, List<Integer> path, int tempSum, int sumValue) {
		if (null == node) {
			return;
		}
		
		tempSum += node.getM_nValue();
		path.add(node.getM_nValue());
		
		boolean isLeaf = (null == node.getM_pLeft() && null == node.getM_pRight());	//      
		
		if (isLeaf && tempSum == sumValue) {	//   
			System.out.print("sumPath(" + sumValue + "): ");
			for (int i : path) {
				System.out.print(i + " ");
			}
			System.out.println();
		}
		
		// 《   ,   》 :-)
		printSumPath(node.getM_pLeft(), path, tempSum, sumValue);
		printSumPath(node.getM_pRight(), path, tempSum, sumValue);
		
		//                           ,             ,          ...
		path.remove(path.size() - 1);	//       
		//       ,  path            ,       (            ),     ,         tempSum+=XXX;         ,      return         
	}
	
	/**
	 *       
	 */
	public synchronized void print() {
		if (null == this.root) {
			System.out.print("HashCode: " + this.hashCode() +  ";   ;");
			return;
		}
		System.out.print("HashCode: " + this.hashCode() +  ";  : ");
		print(this.root);
		System.out.println();
	}
	
	private void print(BinaryTreeNode node) {
		if (null != node) {
			System.out.print(node.getM_nValue() + " ");
			print(node.getM_pLeft());
			print(node.getM_pRight());
		}
	}
}

/**
 *   
 */
class BinaryTreeNode {
	private int m_nValue; // value of node
	private BinaryTreeNode m_pLeft; // left child of node
	private BinaryTreeNode m_pRight; // right child of node
	
	BinaryTreeNode(int value) {
		this.m_nValue = value;
	}
	
	public int getM_nValue() {
		return m_nValue;
	}
	public void setM_nValue(int mNValue) {
		m_nValue = mNValue;
	}
	public BinaryTreeNode getM_pLeft() {
		return m_pLeft;
	}
	public void setM_pLeft(BinaryTreeNode mPLeft) {
		m_pLeft = mPLeft;
	}
	public BinaryTreeNode getM_pRight() {
		return m_pRight;
	}
	public void setM_pRight(BinaryTreeNode mPRight) {
		m_pRight = mPRight;
	}
}

public class Four {
	public static void main(String[] args) {
		BinaryTree tree = new BinaryTree();
		tree.addNode(new BinaryTreeNode(10));
		tree.addNode(new BinaryTreeNode(5));
		tree.addNode(new BinaryTreeNode(12));
		tree.addNode(new BinaryTreeNode(4));
		tree.addNode(new BinaryTreeNode(7));
		tree.addNode(new BinaryTreeNode(9));
		tree.addNode(new BinaryTreeNode(3));
		tree.print();
		tree.printSumPath(22);
		tree.printSumPath(31);
	}
}