没写过Java的二叉树 不知道对不对 class BinaryTree { private BinaryTree left; private BinaryTree right; private int val; }另外你说的“并设计一个方法来计算这个树上最大的val值。”是怎么个计算法? 只是搜索找出最大值嘛?
class BinaryTree { private BinaryTree left; private BinaryTree right; private int val; public int MaxVal()//简单的递归调用,对根节点root.MaxVal()就是整个树的最大值 { return left.MaxVal()>right.MaxVal()?left.MaxVal():right.MaxVal(); } }
这个不对吧 = = class BinaryTree { private BinaryTree left; private BinaryTree right; private int val; // 调用时调用root.maxVal() public int maxVal() { if ((left == null) && (right == null)) { return val; } else if (left == null) { int rightMax = right.maxVal(); return (val > rightMax) ? val : rightMax; } else if (right == null) { int leftMax = left.maxVal(); return (val > leftMax) ? val : leftMax; } else { int leftMax = left.maxVal(); int rightMax = right.maxVal(); int childMax = (leftMax > rightMax) ? leftMax : rightMax; return (val > childMax) ? val : childMax; } } }
public class IntTreeNode { public int data; public IntTreeNode left; public IntTreeNode right;
// constructs a leaf node with given data public IntTreeNode(int data) { this(data, null, null); }
// constructs a branch node with given data, left subtree, // right subtree public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) { this.data = data; this.left = left; this.right = right; } }public class IntTree { private IntTreeNode overallRoot; public IntTree(int max) { if (max <= 0) throw new IllegalArgumentException("max: " + max); this.overallRoot = buildTree(1, max); } private IntTreeNode buildTree(int n, int max) { if (n > max) return null; return new IntTreeNode(n, buildTree(2 * n, max), buildTree(2 * n + 1, max)); } public int countEmpty() { return countEmpty(this.overallRoot); } private int countEmpty(IntTreeNode root) { if ((root.left != null) && (root.right != null)) return (countEmpty(root.left) + countEmpty(root.right)); if (root.left != null) return (countEmpty(root.left) + 1); if (root.right != null) return (countEmpty(root.right) + 1); return 2; } public int countLeftNodes() { return countLeftNodes(this.overallRoot); }
/** * <p> count number of notes in the binary-tree </p> * * @return number of nodes if success */ public int countTotalNodes() { return countTotalNodes(this.overallRoot); } private int countTotalNodes(IntTreeNode root) { if (root!= null) return (countTotalNodes(root.left) + countTotalNodes(root.right) + 1); // already include root node if (root!= null && root.left != null) return (countTotalNodes(root.left)); if (root != null && root.right != null) return (countTotalNodes(root.right)); return 0; } private int countLeftNodes(IntTreeNode root) { if ((root.left != null) && (root.right != null)) return (countLeftNodes(root.left) + countLeftNodes(root.right) + 1); if (root.left != null) return (countLeftNodes(root.left) + 1); if (root.right != null) return countLeftNodes(root.right); return 0; } private List<Integer> inOrderList(IntTreeNode root , List<Integer> list) {
// in case one leaf on parent node. if(node != null && node.left != null && node.left.left != null && node.left.right == null) { node.left.left = null; isLeaf = true; } return isLeaf; } public void printInorder() { System.out.print("inorder:"); printInorder(this.overallRoot); System.out.println(); } private void printInorder(IntTreeNode root) { if (root != null) { printInorder(root.left); System.out.print(" " + root.data); printInorder(root.right); } } public void printPostorder() { System.out.print("postorder:"); printPostorder(this.overallRoot); System.out.println(); } private void printPostorder(IntTreeNode root) { if (root != null) { printPostorder(root.left); printPostorder(root.right); System.out.print(" " + root.data); } } public void printPreorder() { System.out.print("preorder:"); printPreorder(this.overallRoot); System.out.println(); } private void printPreorder(IntTreeNode root) { if (root != null) { System.out.print(" " + root.data); printPreorder(root.left); printPreorder(root.right); } } public void printSideways() { printSideways(this.overallRoot, 0); } private void printSideways(IntTreeNode root, int level) { if (root != null) { printSideways(root.right, level + 1); for (int i = 0; i < level; ++i) System.out.print(" "); System.out.println(root.data); printSideways(root.left, level + 1); } } public void removeLeaves() { removeLeaves(overallRoot); }
public int getTotalNumberofLeavesInTree() { return calculateLeaves(overallRoot); } private void removeLeaves(IntTreeNode node) { if(node == null) return; if(isLeaf(node)){ return; } removeLeaves(node.left); removeLeaves(node.right); } private int calculateLeaves(IntTreeNode node) { if(null==node) return 0;
// only have root node, no any leaves if(node.left == null && node.right == null) return 0;
// identify the leaves layer int totalNodes = countTotalNodes(); int sum = 0; int index = 0; while(totalNodes > sum) { sum += Math.pow(2, index); if(sum > totalNodes) break; index++; }
// find all leaves int lastTwoNodes = 0; for(int i=0; i<index; i++) { lastTwoNodes +=Math.pow(2, i); }
int leavesInLastLayer = (totalNodes - lastTwoNodes); int leavesInlastButTwoLayer = (sum - totalNodes)/2; System.out.println("the number of leaves in last layer= " + leavesInLastLayer); System.out.println("the number of leaves in last but two layer= " + leavesInlastButTwoLayer); return (leavesInLastLayer + leavesInlastButTwoLayer); }
public int sum() { return sum(this.overallRoot); } private int sum(IntTreeNode root) { if (root == null) return 0; return (root.data + sum(root.left) + sum(root.right)); } }
package bean;import java.util.Stack; public class BiTree { private BiTree leftTree;// 左子树 private BiTree rightTree;// 右子树 private Object data;// 节点数据 public final static int MAX = 40; BiTree[] elements = new BiTree[MAX];// 层次遍历时保存各个节点 int front;// 层次遍历时队首 int rear;// 层次遍历时队尾 // 构造函数 public BiTree() { // TODO Auto-generated constructor stub } public BiTree(Object data) { this.data = data; } public BiTree(Object data, BiTree lefTree, BiTree righTree) { this.data = data; this.leftTree = lefTree; this.rightTree = righTree; } // 递归前序遍历二叉树 public void preOrder(BiTree tree) { if (tree != null) { visit(tree.data); preOrder(tree.leftTree); preOrder(tree.rightTree); } } // 非递归实现前序遍历 public void iterativePreOrder(BiTree tree) { Stack<BiTree> stack = new Stack<BiTree>(); if (tree != null) { stack.push(tree); while (!stack.isEmpty()) { tree = stack.pop(); visit(tree.data); if (tree.rightTree != null) stack.push(tree.rightTree); if (tree.leftTree != null) stack.push(tree.leftTree); } } } // 递归中序遍历二叉树 public void inOrder(BiTree tree) { if (tree != null) { inOrder(tree.leftTree); visit(tree.data); inOrder(tree.rightTree); } } // 非递归实现中序遍历 public void iterativeInOrder(BiTree tree) { Stack<BiTree> stack = new Stack<BiTree>(); while (tree != null) { while (tree != null) { if (tree.rightTree != null) stack.push(tree.rightTree);// 当前节点右子入栈 stack.push(tree);// 当前节点入栈 tree = tree.leftTree; } tree = stack.pop(); while (!stack.empty() && tree.rightTree == null) { visit(tree.data); tree = stack.pop(); } visit(tree.data); if (!stack.empty()) tree = stack.pop(); else tree = null; } } // 递归后序遍历二叉树 public void postOrder(BiTree tree) { if (tree != null) { postOrder(tree.leftTree); postOrder(tree.rightTree); visit(tree.data); } } // 非递归实现后序遍历 public void iterativePostOrder(BiTree tree) { BiTree tempTree = tree; Stack<BiTree> stack = new Stack<BiTree>(); while (tree != null) { // 左子树入栈 for (; tree.leftTree != null; tree = tree.leftTree) stack.push(tree); // 当前节点无右子或右子已经输出 while (tree != null && (tree.rightTree == null || tree.rightTree == tempTree)) { visit(tree.data); tempTree = tree;// 记录上一个已输出节点 if (stack.empty()) return; tree = stack.pop(); } // 处理右子 stack.push(tree); tree = tree.rightTree; } } // 层次遍历二叉树 public void LayerOrder(BiTree tree) { elements[0] = tree; front = 0; rear = 1; while (front < rear) { try { if (elements[front].data != null) { System.out.print(elements[front].data + " "); if (elements[front].leftTree != null) elements[rear++] = elements[front].leftTree; if (elements[front].rightTree != null) elements[rear++] = elements[front].rightTree; front++; } } catch (Exception e) { break; } } } // 求二叉树的高度 public static int height(BiTree tree) { if (tree == null) return 0; else { int leftTreeHeight = height(tree.leftTree); int rightTreeHeight = height(tree.rightTree); return leftTreeHeight > rightTreeHeight ? leftTreeHeight + 1 : rightTreeHeight + 1; } } //递归求二叉树值最大的节点 public static int getMaxNode(BiTree tree){ if(tree==null) return -1; else{ int leftTreeMaxNode=getMaxNode(tree.leftTree); int rightTreeMaxNode=getMaxNode(tree.rightTree); int temp=leftTreeMaxNode>rightTreeMaxNode?leftTreeMaxNode:rightTreeMaxNode; return temp>Integer.parseInt(tree.data.toString())?temp:Integer.parseInt(tree.data.toString()); } } // 求data所对应结点的层数,如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层 public int level(Object data) { int leftLevel, rightLevel; if (this == null) return -1; if (data == this.data) return 1; leftLevel = leftTree == null ? -1 : leftTree.level(data); rightLevel = rightTree == null ? -1 : rightTree.level(data); if (leftLevel < 0 && rightLevel < 0) return -1; return leftLevel > rightLevel ? leftLevel + 1 : rightLevel + 1; } // 求二叉树的结点总数 public static int nodes(BiTree tree) { if (tree == null) return 0; else { int left = nodes(tree.leftTree); int right = nodes(tree.rightTree); return left + right + 1; } } // 求二叉树叶子节点的总数 public static int leaf(BiTree tree) { if (tree == null) return 0; else { int left = leaf(tree.leftTree); int right = leaf(tree.rightTree); if (tree.leftTree == null && tree.rightTree == null) return left + right + 1; else return left + right; } } // 求二叉树父节点个数 public static int fatherNodes(BiTree tree) { if (tree == null || (tree.leftTree == null && tree.rightTree == null)) return 0; else { int left = fatherNodes(tree.leftTree); int right = fatherNodes(tree.rightTree); return left + right + 1; } } // 求只有一个孩子结点的父节点个数 public static int oneChildFather(BiTree tree) { int left, right; if (tree == null || (tree.rightTree == null && tree.leftTree == null)) return 0; else { left = oneChildFather(tree.leftTree); right = oneChildFather(tree.rightTree); if ((tree.leftTree != null && tree.rightTree == null) || (tree.leftTree == null && tree.rightTree != null)) return left + right + 1; else return left + right;/* 加1是因为要算上根节点 */ } } // 求二叉树只拥有左孩子的父节点总数 public static int leftChildFather(BiTree tree) { if (tree == null) return 0; else { int left = leftChildFather(tree.leftTree); int right = leftChildFather(tree.rightTree); if ((tree.leftTree != null && tree.rightTree == null)) return left + right + 1; else return left + right; } } // 求二叉树只拥有右孩子的结点总数 public static int rightChildFather(BiTree tree) { if (tree == null || tree.rightTree == null) return 0; else { int left = rightChildFather(tree.leftTree); int right = rightChildFather(tree.rightTree); if (tree.leftTree == null && tree.rightTree != null) return left + right + 1; else return left + right; } } // 计算有两个节点的父节点的个数 public static int doubleChildFather(BiTree tree) { int left, right; if (tree == null) return 0; else { left = doubleChildFather(tree.leftTree); right = doubleChildFather(tree.rightTree); if (tree.leftTree != null && tree.rightTree != null) return (left + right + 1);/* 加1是因为要算上根节点 */ else return (left + right); } } // 访问根节点 public void visit(Object data) { System.out.print(data + " "); } // 将树中的每个节点的孩子对换位置 public void exChange() { if (this == null) return; if (leftTree != null) leftTree.exChange(); if (rightTree != null) rightTree.exChange(); BiTree temp = leftTree; leftTree = rightTree; rightTree = temp; } //递归求所有结点的和 public static int getSumByRecursion(BiTree tree){ if(tree==null){ return 0; } else{ int left=getSumByRecursion(tree.leftTree); int right=getSumByRecursion(tree.rightTree); return Integer.parseInt(tree.data.toString())+left+right; }
} //非递归求二叉树中所有结点的和 public static int getSumByNoRecursion(BiTree tree){ Stack<BiTree> stack = new Stack<BiTree>(); int sum=0; if(tree!=null){ stack.push(tree); while(!stack.isEmpty()){ tree=stack.pop(); sum+=Integer.parseInt(tree.data.toString()); if(tree.leftTree!=null) stack.push(tree.leftTree); if(tree.rightTree!=null) stack.push(tree.rightTree); }
} return sum;
} /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub BiTree e = new BiTree(5); BiTree g = new BiTree(7); BiTree h = new BiTree(8); BiTree l = new BiTree(12); BiTree m = new BiTree(13); BiTree n = new BiTree(14); BiTree k = new BiTree(11, n, null); BiTree j = new BiTree(10, l, m); BiTree i = new BiTree(9, j, k); BiTree d = new BiTree(4, null, g); BiTree f = new BiTree(6, h, i); BiTree b = new BiTree(2, d, e); BiTree c = new BiTree(3, f, null); BiTree tree = new BiTree(1, b, c); System.out.println("二叉树值最大的节点: "); System.out.println(BiTree.getMaxNode(tree));
class BinaryTree {
private BinaryTree left;
private BinaryTree right;
private int val;
}另外你说的“并设计一个方法来计算这个树上最大的val值。”是怎么个计算法? 只是搜索找出最大值嘛?
class BinaryTree {
private BinaryTree left;
private BinaryTree right;
private int val;
public int MaxVal()//简单的递归调用,对根节点root.MaxVal()就是整个树的最大值
{
return left.MaxVal()>right.MaxVal()?left.MaxVal():right.MaxVal();
}
}
这个不对吧 = =
class BinaryTree {
private BinaryTree left;
private BinaryTree right;
private int val;
// 调用时调用root.maxVal()
public int maxVal() {
if ((left == null) && (right == null)) {
return val;
} else if (left == null) {
int rightMax = right.maxVal();
return (val > rightMax) ? val : rightMax;
} else if (right == null) {
int leftMax = left.maxVal();
return (val > leftMax) ? val : leftMax;
} else {
int leftMax = left.maxVal();
int rightMax = right.maxVal();
int childMax = (leftMax > rightMax) ? leftMax : rightMax;
return (val > childMax) ? val : childMax;
}
}
}
public int data;
public IntTreeNode left;
public IntTreeNode right;
// constructs a leaf node with given data
public IntTreeNode(int data) {
this(data, null, null);
}
// constructs a branch node with given data, left subtree,
// right subtree
public IntTreeNode(int data, IntTreeNode left,
IntTreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}public class IntTree {
private IntTreeNode overallRoot; public IntTree(int max) {
if (max <= 0)
throw new IllegalArgumentException("max: " + max); this.overallRoot = buildTree(1, max);
} private IntTreeNode buildTree(int n, int max) {
if (n > max)
return null;
return new IntTreeNode(n, buildTree(2 * n, max), buildTree(2 * n + 1,
max));
} public int countEmpty() {
return countEmpty(this.overallRoot);
} private int countEmpty(IntTreeNode root) {
if ((root.left != null) && (root.right != null))
return (countEmpty(root.left) + countEmpty(root.right));
if (root.left != null)
return (countEmpty(root.left) + 1);
if (root.right != null)
return (countEmpty(root.right) + 1); return 2;
} public int countLeftNodes() {
return countLeftNodes(this.overallRoot);
}
/**
* <p> count number of notes in the binary-tree </p>
*
* @return number of nodes if success
*/
public int countTotalNodes() {
return countTotalNodes(this.overallRoot);
} private int countTotalNodes(IntTreeNode root) {
if (root!= null)
return (countTotalNodes(root.left) + countTotalNodes(root.right) + 1); // already include root node
if (root!= null && root.left != null)
return (countTotalNodes(root.left));
if (root != null && root.right != null)
return (countTotalNodes(root.right));
return 0;
} private int countLeftNodes(IntTreeNode root) {
if ((root.left != null) && (root.right != null))
return (countLeftNodes(root.left) + countLeftNodes(root.right) + 1);
if (root.left != null)
return (countLeftNodes(root.left) + 1);
if (root.right != null)
return countLeftNodes(root.right); return 0;
} private List<Integer> inOrderList(IntTreeNode root , List<Integer> list) {
if (root != null) {
inOrderList(root.left , list);
list.add(root.data);
inOrderList(root.right, list);
}
return list;
} public void callInOrderList() {
List<Integer> list = new ArrayList<Integer>();
inOrderList(overallRoot, list);
} /**
*
* @param node
* @return
* @throws NullPointerException if node is null
*/
private boolean isLeaf(IntTreeNode node) {
boolean isLeaf = false;
if(node != null && node.left != null && node.left.left == null && node.left.right == null) {
node.left = null;
isLeaf = true;
}
if(node != null && node.right != null && node.right.left == null && node.right.right == null) {
node.right = null;
isLeaf = true;
}
// in case one leaf on parent node.
if(node != null && node.left != null && node.left.left != null && node.left.right == null) {
node.left.left = null;
isLeaf = true;
}
return isLeaf;
} public void printInorder() {
System.out.print("inorder:");
printInorder(this.overallRoot);
System.out.println();
} private void printInorder(IntTreeNode root) {
if (root != null) {
printInorder(root.left);
System.out.print(" " + root.data);
printInorder(root.right);
}
} public void printPostorder() {
System.out.print("postorder:");
printPostorder(this.overallRoot);
System.out.println();
} private void printPostorder(IntTreeNode root) {
if (root != null) {
printPostorder(root.left);
printPostorder(root.right);
System.out.print(" " + root.data);
}
} public void printPreorder() {
System.out.print("preorder:");
printPreorder(this.overallRoot);
System.out.println();
} private void printPreorder(IntTreeNode root) {
if (root != null) {
System.out.print(" " + root.data);
printPreorder(root.left);
printPreorder(root.right);
}
} public void printSideways() {
printSideways(this.overallRoot, 0);
} private void printSideways(IntTreeNode root, int level) {
if (root != null) {
printSideways(root.right, level + 1);
for (int i = 0; i < level; ++i)
System.out.print(" "); System.out.println(root.data);
printSideways(root.left, level + 1);
}
} public void removeLeaves() {
removeLeaves(overallRoot);
}
public int getTotalNumberofLeavesInTree() {
return calculateLeaves(overallRoot);
}
private void removeLeaves(IntTreeNode node) {
if(node == null)
return;
if(isLeaf(node)){
return;
}
removeLeaves(node.left);
removeLeaves(node.right);
} private int calculateLeaves(IntTreeNode node) {
if(null==node) return 0;
// only have root node, no any leaves
if(node.left == null && node.right == null)
return 0;
// identify the leaves layer
int totalNodes = countTotalNodes();
int sum = 0;
int index = 0;
while(totalNodes > sum) {
sum += Math.pow(2, index);
if(sum > totalNodes)
break;
index++;
}
// find all leaves
int lastTwoNodes = 0;
for(int i=0; i<index; i++) {
lastTwoNodes +=Math.pow(2, i);
}
int leavesInLastLayer = (totalNodes - lastTwoNodes);
int leavesInlastButTwoLayer = (sum - totalNodes)/2;
System.out.println("the number of leaves in last layer= " + leavesInLastLayer);
System.out.println("the number of leaves in last but two layer= " + leavesInlastButTwoLayer);
return (leavesInLastLayer + leavesInlastButTwoLayer);
}
public int sum() {
return sum(this.overallRoot);
} private int sum(IntTreeNode root) {
if (root == null)
return 0; return (root.data + sum(root.left) + sum(root.right));
}
}
package bean;import java.util.Stack;
public class BiTree {
private BiTree leftTree;// 左子树
private BiTree rightTree;// 右子树
private Object data;// 节点数据
public final static int MAX = 40;
BiTree[] elements = new BiTree[MAX];// 层次遍历时保存各个节点
int front;// 层次遍历时队首
int rear;// 层次遍历时队尾
// 构造函数
public BiTree() {
// TODO Auto-generated constructor stub
}
public BiTree(Object data) {
this.data = data;
}
public BiTree(Object data, BiTree lefTree, BiTree righTree) {
this.data = data;
this.leftTree = lefTree;
this.rightTree = righTree;
}
// 递归前序遍历二叉树
public void preOrder(BiTree tree) {
if (tree != null) {
visit(tree.data);
preOrder(tree.leftTree);
preOrder(tree.rightTree);
}
}
// 非递归实现前序遍历
public void iterativePreOrder(BiTree tree) {
Stack<BiTree> stack = new Stack<BiTree>();
if (tree != null) {
stack.push(tree);
while (!stack.isEmpty()) {
tree = stack.pop();
visit(tree.data);
if (tree.rightTree != null)
stack.push(tree.rightTree);
if (tree.leftTree != null)
stack.push(tree.leftTree);
}
}
}
// 递归中序遍历二叉树
public void inOrder(BiTree tree) {
if (tree != null) {
inOrder(tree.leftTree);
visit(tree.data);
inOrder(tree.rightTree);
}
}
// 非递归实现中序遍历
public void iterativeInOrder(BiTree tree) {
Stack<BiTree> stack = new Stack<BiTree>();
while (tree != null) {
while (tree != null) {
if (tree.rightTree != null)
stack.push(tree.rightTree);// 当前节点右子入栈
stack.push(tree);// 当前节点入栈
tree = tree.leftTree;
}
tree = stack.pop();
while (!stack.empty() && tree.rightTree == null) {
visit(tree.data);
tree = stack.pop();
}
visit(tree.data);
if (!stack.empty())
tree = stack.pop();
else
tree = null;
}
}
// 递归后序遍历二叉树
public void postOrder(BiTree tree) {
if (tree != null) {
postOrder(tree.leftTree);
postOrder(tree.rightTree);
visit(tree.data);
}
}
// 非递归实现后序遍历
public void iterativePostOrder(BiTree tree) {
BiTree tempTree = tree;
Stack<BiTree> stack = new Stack<BiTree>();
while (tree != null) {
// 左子树入栈
for (; tree.leftTree != null; tree = tree.leftTree)
stack.push(tree);
// 当前节点无右子或右子已经输出
while (tree != null
&& (tree.rightTree == null || tree.rightTree == tempTree)) {
visit(tree.data);
tempTree = tree;// 记录上一个已输出节点
if (stack.empty())
return;
tree = stack.pop();
}
// 处理右子
stack.push(tree);
tree = tree.rightTree;
}
}
// 层次遍历二叉树
public void LayerOrder(BiTree tree) {
elements[0] = tree;
front = 0;
rear = 1;
while (front < rear) {
try {
if (elements[front].data != null) {
System.out.print(elements[front].data + " ");
if (elements[front].leftTree != null)
elements[rear++] = elements[front].leftTree;
if (elements[front].rightTree != null)
elements[rear++] = elements[front].rightTree;
front++;
}
} catch (Exception e) {
break;
}
}
}
// 求二叉树的高度
public static int height(BiTree tree) {
if (tree == null)
return 0;
else {
int leftTreeHeight = height(tree.leftTree);
int rightTreeHeight = height(tree.rightTree);
return leftTreeHeight > rightTreeHeight ? leftTreeHeight + 1
: rightTreeHeight + 1;
}
}
//递归求二叉树值最大的节点
public static int getMaxNode(BiTree tree){
if(tree==null)
return -1;
else{
int leftTreeMaxNode=getMaxNode(tree.leftTree);
int rightTreeMaxNode=getMaxNode(tree.rightTree);
int temp=leftTreeMaxNode>rightTreeMaxNode?leftTreeMaxNode:rightTreeMaxNode;
return temp>Integer.parseInt(tree.data.toString())?temp:Integer.parseInt(tree.data.toString());
}
}
// 求data所对应结点的层数,如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层
public int level(Object data) {
int leftLevel, rightLevel;
if (this == null)
return -1;
if (data == this.data)
return 1;
leftLevel = leftTree == null ? -1 : leftTree.level(data);
rightLevel = rightTree == null ? -1 : rightTree.level(data);
if (leftLevel < 0 && rightLevel < 0)
return -1;
return leftLevel > rightLevel ? leftLevel + 1 : rightLevel + 1;
}
// 求二叉树的结点总数
public static int nodes(BiTree tree) {
if (tree == null)
return 0;
else {
int left = nodes(tree.leftTree);
int right = nodes(tree.rightTree);
return left + right + 1;
}
}
// 求二叉树叶子节点的总数
public static int leaf(BiTree tree) {
if (tree == null)
return 0;
else {
int left = leaf(tree.leftTree);
int right = leaf(tree.rightTree);
if (tree.leftTree == null && tree.rightTree == null)
return left + right + 1;
else
return left + right;
}
}
// 求二叉树父节点个数
public static int fatherNodes(BiTree tree) {
if (tree == null || (tree.leftTree == null && tree.rightTree == null))
return 0;
else {
int left = fatherNodes(tree.leftTree);
int right = fatherNodes(tree.rightTree);
return left + right + 1;
}
}
// 求只有一个孩子结点的父节点个数
public static int oneChildFather(BiTree tree) {
int left, right;
if (tree == null || (tree.rightTree == null && tree.leftTree == null))
return 0;
else {
left = oneChildFather(tree.leftTree);
right = oneChildFather(tree.rightTree);
if ((tree.leftTree != null && tree.rightTree == null)
|| (tree.leftTree == null && tree.rightTree != null))
return left + right + 1;
else
return left + right;/* 加1是因为要算上根节点 */
}
}
// 求二叉树只拥有左孩子的父节点总数
public static int leftChildFather(BiTree tree) {
if (tree == null)
return 0;
else {
int left = leftChildFather(tree.leftTree);
int right = leftChildFather(tree.rightTree);
if ((tree.leftTree != null && tree.rightTree == null))
return left + right + 1;
else
return left + right;
}
}
// 求二叉树只拥有右孩子的结点总数
public static int rightChildFather(BiTree tree) {
if (tree == null || tree.rightTree == null)
return 0;
else {
int left = rightChildFather(tree.leftTree);
int right = rightChildFather(tree.rightTree);
if (tree.leftTree == null && tree.rightTree != null)
return left + right + 1;
else
return left + right;
}
}
// 计算有两个节点的父节点的个数
public static int doubleChildFather(BiTree tree) {
int left, right;
if (tree == null)
return 0;
else {
left = doubleChildFather(tree.leftTree);
right = doubleChildFather(tree.rightTree);
if (tree.leftTree != null && tree.rightTree != null)
return (left + right + 1);/* 加1是因为要算上根节点 */
else
return (left + right);
}
}
// 访问根节点
public void visit(Object data) {
System.out.print(data + " ");
}
// 将树中的每个节点的孩子对换位置
public void exChange() {
if (this == null)
return;
if (leftTree != null)
leftTree.exChange();
if (rightTree != null)
rightTree.exChange();
BiTree temp = leftTree;
leftTree = rightTree;
rightTree = temp;
}
//递归求所有结点的和
public static int getSumByRecursion(BiTree tree){
if(tree==null){
return 0;
}
else{
int left=getSumByRecursion(tree.leftTree);
int right=getSumByRecursion(tree.rightTree);
return Integer.parseInt(tree.data.toString())+left+right;
}
}
//非递归求二叉树中所有结点的和
public static int getSumByNoRecursion(BiTree tree){
Stack<BiTree> stack = new Stack<BiTree>();
int sum=0;
if(tree!=null){
stack.push(tree);
while(!stack.isEmpty()){
tree=stack.pop();
sum+=Integer.parseInt(tree.data.toString());
if(tree.leftTree!=null)
stack.push(tree.leftTree);
if(tree.rightTree!=null)
stack.push(tree.rightTree);
}
}
return sum;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BiTree e = new BiTree(5);
BiTree g = new BiTree(7);
BiTree h = new BiTree(8);
BiTree l = new BiTree(12);
BiTree m = new BiTree(13);
BiTree n = new BiTree(14);
BiTree k = new BiTree(11, n, null);
BiTree j = new BiTree(10, l, m);
BiTree i = new BiTree(9, j, k);
BiTree d = new BiTree(4, null, g);
BiTree f = new BiTree(6, h, i);
BiTree b = new BiTree(2, d, e);
BiTree c = new BiTree(3, f, null);
BiTree tree = new BiTree(1, b, c);
System.out.println("二叉树值最大的节点: ");
System.out.println(BiTree.getMaxNode(tree));
}
}