二叉树构造类：
public class BinaryTree {
int data; // 根节点数据
BinaryTree left; // 左子树
BinaryTree right; // 右子树
public BinaryTree(int data) // 实例化二叉树类
{
this.data = data;
left = null;
right = null;
}
public void insert(BinaryTree root, int data) { // 向二叉树中插入子节点
if (data > root.data) // 二叉树的左节点都比根节点小
{
if (root.right == null) {
root.right = new BinaryTree(data);
} else {
this.insert(root.right, data);
}
} else { // 二叉树的右节点都比根节点大
if (root.left == null) {
root.left = new BinaryTree(data);
} else {
this.insert(root.left, data);
}
}
}
}
二叉树遍历、深度及求和：
public class BinaryTreePreorder {
private static StringBuffer current = new StringBuffer();
private static int sum = 0;
private static int needSum = 178;
public static void preOrder(BinaryTree root) { //前序遍历(递归)
if (root != null) {
System.out.print(root.data + "-");
preOrder(root.left);
preOrder(root.right);
}
}
public static void inOrder(BinaryTree root) { // 中序遍历
if (root != null) {
inOrder(root.left);
System.out.print(root.data + "--");
inOrder(root.right);
}
}
public static void postOrder(BinaryTree root) { // 后序遍历
if (root != null) {
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data + "---");
}
}
public static int getDepth(BinaryTree node) { //深度
if (node == null) {
return 0;
}
int leftDepth = 0;
int rightDepth = 0;
leftDepth = getDepth(node.left);
rightDepth = getDepth(node.right);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
public static void visit(BinaryTree p) {
System.out.print(p.data + " ");
}
protected static void iterativePreorder(BinaryTree p) { //前序遍历(非递归)
Stack stack = new Stack();
if (p != null) {
stack.push(p);
while (!stack.empty()) {
p = stack.pop();
visit(p);
if (p.right != null)
stack.push(p.right);
if (p.left != null)
stack.push(p.left);
}
}
}
private static void sum(BinaryTree node){ //计算二叉树节点总和数为N的集合，这里N = 178
int val = node.data;
current.append(val+",");
if(node.left==null && node.right==null){ //leaf here
sum = 0;
String[] nums = current.toString().split(",");
for (int i=0;i
sum += Integer.parseInt(nums[i]);
}
if (sum == needSum) {
for (int i=0;i
System.out.print(nums[i]+"-");
}
}
}
else{
if(node.left!=null){
sum(node.left);
current.setLength(current.length()-(node.left.data+"").length()-1);
}
if(node.right!=null){
sum(node.right);
current.setLength(current.length()-(node.right.data+"").length()-1);
}
}
}
public static void main(String[] str) {
int[] array = { 12, 76, 35, 22, 16, 48, 90, 46, 9, 40 };
BinaryTree root = new BinaryTree(array[0]); // 创建二叉树
for (int i = 1; i < array.length; i++) {
root.insert(root, array[i]); // 向二叉树中插入数据
}
System.out.println("(递归)前序遍历：");
preOrder(root);
System.out.println();
System.out.println("(非递归)前序遍历：");
iterativePreorder(root);
System.out.println();
System.out.println("中序遍历：");
inOrder(root);
System.out.println();
System.out.println("后序遍历：");
postOrder(root);
System.out.println();
System.out.println("深度：");
System.out.println( getDepth(root));
System.out.println("遍历求和，取总和为178的序列：");
sum(root);
}
}
二叉树图形：
