java代码判断二叉树 判断二叉树是否为镜像二叉树java

验证:二叉树的性质3:n0=n2+1 用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("输入节点数组有误");

}

}

}

java 判断两颗二叉树是否相等

java 判断两个二叉树是否完全相同

包括了创建二叉树,前序遍历输出(递归),比较二叉树是否相同。

[java] view plain copy

package com.yuxin.learn;

import java.util.LinkedList;

public class Main {

private static int[] a1 = { 1, 2, 3, 4, 5, 6 };

private static int[] a2 = { 1, 2, 5, 6, 7 };

private static int[] a3 = { 1, 2, 5, 6, 7 };

private static int[] a4 = { 1, 2, 5, 6, 7, 5, 6 };

private static class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int val) {

this.val = val;

this.left = null;

this.right = null;

}

}

public static TreeNode createTree(int a[]) {

int len = a.length;

// 将数组的值依次转为Node节点

LinkedListTreeNode list = new LinkedListTreeNode();

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

list.add(new TreeNode(a[i]));

}

for (int i = 0; i len / 2 - 1; i++) {

list.get(i).left = list.get(i * 2 + 1);

list.get(i).right = list.get(i * 2 + 2);

}

// 最后一个父节点可能没有右边孩子

int last = len / 2 - 1;

list.get(last).left = list.get(last * 2 + 1);

if (len % 2 == 1) {

list.get(last).right = list.get(last * 2 + 2);

}

return list.get(0);

}

//递归前序遍历输出二叉树

public static void preOder(TreeNode head){

System.out.print(head.val+" ");

if(head.left!=null) preOder(head.left);

if(head.right!=null) preOder(head.right);

}

//递归判断两个二叉树是否相同

public static boolean isSameTree(TreeNode head1, TreeNode head2) {

if ((head1 == null head2 != null) || (head1 != null)

(head2 == null) || (head1.val != head2.val))

return false;

if (head1.left == null head1.right == null head2.left == null

head2.right == null head1.val == head2.val)

return true;

return isSameTree(head1.left, head2.left)

isSameTree(head1.right, head2.right);

}

public static void main(String[] args) {

TreeNode head1 = createTree(a1);

System.out.println("Tree1:");

preOder(head1);

System.out.println();

TreeNode head2 = createTree(a2);

System.out.println("Tree2:");

preOder(head2);

System.out.println();

TreeNode head3 = createTree(a3);

System.out.println("Tree3:");

preOder(head3);

System.out.println();

TreeNode head4 = createTree(a4);

System.out.println("Tree4:");

preOder(head4);

System.out.println();

System.out.println("Tree1和Tree2相同吗?" + isSameTree(head1, head2));

System.out.println("Tree2和Tree3相同吗?" + isSameTree(head2, head3));

System.out.println("Tree3和Tree4相同吗?" + isSameTree(head3, head4));

}

}

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

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);


网站标题:java代码判断二叉树 判断二叉树是否为镜像二叉树java
本文链接:http://pwwzsj.com/article/ddcjdoc.html