二元ツリーで値のすべてのパスを見つけて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
};
タイトル:整数と二元ツリーを入力します.
ツリーのルートノードからリーフノードまでのすべてのノードにアクセスしてパスを形成します.
入力した整数に等しいすべてのパスを印刷します.
例えば、整数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);
}
}