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;

}

一個作業題，裡面有你要的東西。

主函數自己寫吧。當然其它地方也有要改的。

原創文章，作者：MX145，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/126310.html

java二叉樹測試（二叉查找樹java）

相關推薦

發表回復