java二叉树测试（二叉查找树java）

• 1、验证:二叉树的性质3:n0=n2+1 用java验证
• 2、求数据结构（JAVA版）实验树和二叉树题目答案
• 3、java一个关于二叉树的简单编程题
• 4、java判断一个二叉树是不是合法的二分查找树
• 5、java实现二叉树的问题

用java验证二叉树性质 ： n0 = n2 + 1

代码如下

package org.link.tree;

/**

* 树节点

* @author link

*

*/

class TreeNode

{

int data;

TreeNode lchild ; // 左子节点

TreeNode rchild ; // 右子节点

public int getData()

{

return data;

}

public TreeNode getLchild()

{

return lchild;

}

public TreeNode getRchild()

{

return rchild;

}

public void setNode(int data,TreeNode lc,TreeNode rc){

this.data = data;

lchild = lc;

rchild = rc;

}

public TreeNode(){

}

}

class Counter{

public static int count=0;

}

public class TreeTest

{

static int n0; // 0度节点

static int n2; // 2度节点

/**

* 根据传入参数创建二叉树

* @param root

* @param a

* @param i

* @return

*/

public static TreeNode createTree(TreeNode root, int[]a, int i)

{

if(i a.length)

{

if(a[i] == 0)

{

root = null;

}

else

{

TreeNode tl = new TreeNode();

TreeNode tr = new TreeNode();

root.setNode(a[i],createTree(tl,a,++(Counter.count)),createTree(tr,a,++(Counter.count)));

}

}

return root;

}

/**

* 遍历二叉树，记录n0 和 n2

* @param root

*/

public static void traverse(TreeNode root)

{

int degree = 0;

if(root != null)

{

if(root.getLchild() != null)

degree++;

if(root.getRchild() != null)

degree++;

if(degree == 0){

n0++;

}else if(degree == 2){

n2++;

}

traverse(root.getLchild());

traverse(root.getRchild());

}else{

}

}

public static void main(String[] args)

{

int[] a = {1,2,3,0,0,4,0,0,5,0,0}; // 这是你传入的任意二叉树数组

TreeNode root = new TreeNode();

root = createTree(root,a,Counter.count);

traverse(root);

System.out.println(“n0:” + n0 + “,n2:” + n2);

// 验证n0=n2+1

if(n0 == n2 + 1){

System.out.println(“n0=n2+1”);

}else{

System.out.println(“输入节点数组有误”);

}

}

}

/**

* @param args

之前在大学的时候写的一个二叉树算法，运行应该没有问题，就看适不适合你的项目了 */

public static void main(String[] args) {

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(“递归前序遍历二叉树结果: “);

tree.preOrder(tree);

System.out.println();

System.out.println(“非递归前序遍历二叉树结果: “);

tree.iterativePreOrder(tree);

System.out.println();

System.out.println(“递归中序遍历二叉树的结果为:”);

tree.inOrder(tree);

System.out.println();

System.out.println(“非递归中序遍历二叉树的结果为:”);

tree.iterativeInOrder(tree);

System.out.println();

System.out.println(“递归后序遍历二叉树的结果为:”);

tree.postOrder(tree);

System.out.println();

System.out.println(“非递归后序遍历二叉树的结果为:”);

tree.iterativePostOrder(tree);

System.out.println();

System.out.println(“层次遍历二叉树结果: “);

tree.LayerOrder(tree);

System.out.println();

System.out.println(“递归求二叉树中所有结点的和为:”+getSumByRecursion(tree));

System.out.println(“非递归求二叉树中所有结点的和为:”+getSumByNoRecursion(tree));

System.out.println(“二叉树中,每个节点所在的层数为:”);

for (int p = 1; p = 14; p++)

System.out.println(p + “所在的层为:” + tree.level(p));

System.out.println(“二叉树的高度为:” + height(tree));

System.out.println(“二叉树中节点总数为:” + nodes(tree));

System.out.println(“二叉树中叶子节点总数为:” + leaf(tree));

System.out.println(“二叉树中父节点总数为:” + fatherNodes(tree));

System.out.println(“二叉树中只拥有一个孩子的父节点数:” + oneChildFather(tree));

System.out.println(“二叉树中只拥有左孩子的父节点总数:” + leftChildFather(tree));

System.out.println(“二叉树中只拥有右孩子的父节点总数:” + rightChildFather(tree));

System.out.println(“二叉树中同时拥有两个孩子的父节点个数为:” + doubleChildFather(tree));

System.out.println(“————————————–“);

tree.exChange();

System.out.println(“交换每个节点的左右孩子节点后……”);

System.out.println(“递归前序遍历二叉树结果: “);

tree.preOrder(tree);

System.out.println();

System.out.println(“非递归前序遍历二叉树结果: “);

tree.iterativePreOrder(tree);

System.out.println();

System.out.println(“递归中序遍历二叉树的结果为:”);

tree.inOrder(tree);

System.out.println();

System.out.println(“非递归中序遍历二叉树的结果为:”);

tree.iterativeInOrder(tree);

System.out.println();

System.out.println(“递归后序遍历二叉树的结果为:”);

tree.postOrder(tree);

System.out.println();

System.out.println(“非递归后序遍历二叉树的结果为:”);

tree.iterativePostOrder(tree);

System.out.println();

System.out.println(“层次遍历二叉树结果: “);

tree.LayerOrder(tree);

System.out.println();

System.out.println(“递归求二叉树中所有结点的和为:”+getSumByRecursion(tree));

System.out.println(“非递归求二叉树中所有结点的和为:”+getSumByNoRecursion(tree));

System.out.println(“二叉树中,每个节点所在的层数为:”);

for (int p = 1; p = 14; p++)

System.out.println(p + “所在的层为:” + tree.level(p));

System.out.println(“二叉树的高度为:” + height(tree));

System.out.println(“二叉树中节点总数为:” + nodes(tree));

System.out.println(“二叉树中叶子节点总数为:” + leaf(tree));

System.out.println(“二叉树中父节点总数为:” + fatherNodes(tree));

System.out.println(“二叉树中只拥有一个孩子的父节点数:” + oneChildFather(tree));

System.out.println(“二叉树中只拥有左孩子的父节点总数:” + leftChildFather(tree));

System.out.println(“二叉树中只拥有右孩子的父节点总数:” + rightChildFather(tree));

System.out.println(“二叉树中同时拥有两个孩子的父节点个数为:” + doubleChildFather(tree));

}

}

定义一个结点类：

public class Node {

private int value;

private Node leftNode;

private Node rightNode;

public Node getRightNode() {

return rightNode;

}

public void setRightNode(Node rightNode) {

this.rightNode = rightNode;

}

public int getValue() {

return value;

}

public void setValue(int value) {

this.value = value;

}

public Node getLeftNode() {

return leftNode;

}

public void setLeftNode(Node leftNode) {

this.leftNode = leftNode;

}

}

初始化结点树：

public void initNodeTree()

{

int nodeNumber;

HashMapString, Integer map = new HashMapString, Integer();

Node nodeTree = new Node();

Scanner reader = new Scanner(System.in);

nodeNumber = reader.nextInt();

for(int i = 0; i nodeNumber; i++) {

int value = reader.nextInt();

String str = reader.next();

map.put(str, value);

}

if (map.containsKey(“#”)) {

int value = map.get(“#”);

nodeTree.setValue(value);

setChildNode(map, value, nodeTree);

}

preTraversal(nodeTree);

}

private void setChildNode(HashMapString, Integer map, int nodeValue, Node parentNode) {

int value = 0;

if (map.containsKey(“L” + nodeValue)) {

value = map.get(“L” + nodeValue);

Node leftNode = new Node();

leftNode.setValue(value);

parentNode.setLeftNode(leftNode);

setChildNode(map, value, leftNode);

}

if (map.containsKey(“R” + nodeValue)) {

value = map.get(“R” + nodeValue);

Node rightNode = new Node();

rightNode.setValue(value);

parentNode.setRightNode(rightNode);

setChildNode(map, value, rightNode);

}

}

前序遍历该结点树：

public void preTraversal(Node nodeTree) {

if (nodeTree != null) {

System.out.print(nodeTree.getValue() + “\t”);

preTraversal(nodeTree.getLeftNode());

preTraversal(nodeTree.getRightNode());

}

}

java判断一个二叉树是不是合法的二分查找树

/* 判断一个二叉树是不是合法的二分查找树的简单的递给方法，学习

* 采用自顶向下的遍历方式，对于每个节点，检查顶部传来的范围要求，

* 要求是指：对于左子树，父节点的值就是最大值，对于右子树，父节点的值就是最小值

*/

public boolean isValidBST(TreeNode root) {

//初始的时候，对根节点没有范围要求

return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);

}

public boolean isValidBST(TreeNode root, long minVal, long maxVal) {

if (root == null) return true;

//检查是否满足根节点的范围要求

if (root.val = maxVal || root.val = minVal)

return false;

//修改对子节点的要求，对于左子树，本节点的值就是最大值，对于右子树，本节点的值就是最小值

return isValidBST(root.left, minVal, root.val) isValidBST(root.right, root.val, maxVal);

/**

* 二叉树测试二叉树顺序存储在treeLine中，递归前序创建二叉树。另外还有能

* 够前序、中序、后序、按层遍历二叉树的方法以及一个返回遍历结果asString的

* 方法。

*/

public class BitTree {

public static Node2 root;

public static String asString;

//事先存入的数组,符号#表示二叉树结束。

public static final char[] treeLine = {‘a’,’b’,’c’,’d’,’e’,’f’,’g’,’ ‘,’ ‘,’j’,’ ‘,’ ‘,’i’,’#’};

//用于标志二叉树节点在数组中的存储位置，以便在创建二叉树时能够找到节点对应的数据。

static int index;

//构造函数

public BitTree() {

System.out.print(“测试二叉树的顺序表示为：”);

System.out.println(treeLine);

this.index = 0;

root = this.setup(root);

}

//创建二叉树的递归程序

private Node2 setup(Node2 current) {

if (index = treeLine.length) return current;

if (treeLine[index] == ‘#’) return current;

if (treeLine[index] == ‘ ‘) return current;

current = new Node2(treeLine[index]);

index = index * 2 + 1;

current.left = setup(current.left);

index ++;

current.right = setup(current.right);

index = index / 2 – 1;

return current;

}

//二叉树是否为空。

public boolean isEmpty() {

if (root == null) return true;

return false;

}

//返回遍历二叉树所得到的字符串。

public String toString(int type) {

if (type == 0) {

asString = “前序遍历：\t”;

this.front(root);

}

if (type == 1) {

asString = “中序遍历：\t”;

this.middle(root);

}

if (type == 2) {

asString = “后序遍历：\t”;

this.rear(root);

}

if (type == 3) {

asString = “按层遍历：\t”;

this.level(root);

}

return asString;

}

//前序遍历二叉树的循环算法，每到一个结点先输出，再压栈，然后访问它的左子树，

//出栈，访问其右子树，然后该次循环结束。

private void front(Node2 current) {

StackL stack = new StackL((Object)current);

do {

if (current == null) {

current = (Node2)stack.pop();

current = current.right;

} else {

asString += current.ch;

current = current.left;

}

if (!(current == null)) stack.push((Object)current);

} while (!(stack.isEmpty()));

}

//中序遍历二叉树

private void middle(Node2 current) {

if (current == null) return;

middle(current.left);

asString += current.ch;

middle(current.right);

}

//后序遍历二叉树的递归算法

private void rear(Node2 current) {

if (current == null) return;

rear(current.left);

rear(current.right);

asString += current.ch;

}

}

/**

* 二叉树所使用的节点类。包括一个值域两个链域

*/

public class Node2 {

char ch;

Node2 left;

Node2 right;

//构造函数

public Node2(char c) {

this.ch = c;

this.left = null;

this.right = null;

}

//设置节点的值

public void setChar(char c) {

this.ch = c;

}

//返回节点的值

public char getChar() {

return ch;

}

//设置节点的左孩子

public void setLeft(Node2 left) {

this.left = left;

}

//设置节点的右孩子

public void setRight (Node2 right) {

this.right = right;

}

//如果是叶节点返回true

public boolean isLeaf() {

if ((this.left == null) (this.right == null)) return true;

return false;

}

}

一个作业题，里面有你要的东西。

主函数自己写吧。当然其它地方也有要改的。