二叉查找樹java
Ⅰ 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如何創建一顆二叉樹
計算機科學中，二叉樹是每個結點最多有兩個子樹的有序樹。通常子樹的根被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。
二叉樹的每個結點至多隻有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的 i -1次方個結點；深度為k的二叉樹至多有2^(k) -1個結點；對任何一棵二叉樹T，如果其終端結點數(即葉子結點數)為n0，度為2的結點數為n2，則n0 = n2 + 1。
樹是由一個或多個結點組成的有限集合，其中：
⒈必有一個特定的稱為根(ROOT)的結點；
二叉樹
⒉剩下的結點被分成n>=0個互不相交的集合T1、T2、......Tn，而且， 這些集合的每一個又都是樹。樹T1、T2、......Tn被稱作根的子樹(Subtree)。
樹的遞歸定義如下：（1）至少有一個結點（稱為根）（2）其它是互不相交的子樹
1.樹的度——也即是寬度，簡單地說，就是結點的分支數。以組成該樹各結點中最大的度作為該樹的度，如上圖的樹，其度為2;樹中度為零的結點稱為葉結點或終端結點。樹中度不為零的結點稱為分枝結點或非終端結點。除根結點外的分枝結點統稱為內部結點。
2.樹的深度——組成該樹各結點的最大層次。
3.森林——指若干棵互不相交的樹的集合，如上圖，去掉根結點A，其原來的二棵子樹T1、T2、T3的集合{T1,T2,T3}就為森林；
4.有序樹——指樹中同層結點從左到右有次序排列，它們之間的次序不能互換，這樣的樹稱為有序樹，否則稱為無序樹。
樹的表示
樹的表示方法有許多，常用的方法是用括弧：先將根結點放入一對圓括弧中，然後把它的子樹由左至右的順序放入括弧中，而對子樹也採用同樣的方法處理；同層子樹與它的根結點用圓括弧括起來，同層子樹之間用逗號隔開，最後用閉括弧括起來。如右圖可寫成如下形式：
二叉樹
(a( b(d,e), c( f( ,g(h,i) ), )))
Ⅲ java構建二叉樹演算法
//******************************************************************************************************//
//*****本程序包括簡單的二叉樹類的實現和前序,中序,後序,層次遍歷二叉樹演算法,*******//
//******以及確定二叉樹的高度,制定對象在樹中的所處層次以及將樹中的左右***********//
//******孩子節點對換位置,返回葉子節點個數刪除葉子節點,並輸出所刪除的葉子節點**//
//*******************************CopyRight By phoenix*******************************************//
//************************************Jan 12,2008*************************************************//
//****************************************************************************************************//
public class BinTree {
public final static int MAX=40;
private Object data; //數據元數
private BinTree left,right; //指向左,右孩子結點的鏈
BinTree []elements = new BinTree[MAX];//層次遍歷時保存各個節點
int front;//層次遍歷時隊首
int rear;//層次遍歷時隊尾
public BinTree()
{
}
public BinTree(Object data)
{ //構造有值結點
this.data = data;
left = right = null;
}
public BinTree(Object data,BinTree left,BinTree right)
{ //構造有值結點
this.data = data;
this.left = left;
this.right = right;
}
public String toString()
{
return data.toString();
}//前序遍歷二叉樹
public static void preOrder(BinTree parent){
if(parent == null)
return;
System.out.print(parent.data+" ");
preOrder(parent.left);
preOrder(parent.right);
}//中序遍歷二叉樹
public void inOrder(BinTree parent){
if(parent == null)
return;
inOrder(parent.left);
System.out.print(parent.data+" ");
inOrder(parent.right);
}//後序遍歷二叉樹
public void postOrder(BinTree parent){
if(parent == null)
return;
postOrder(parent.left);
postOrder(parent.right);
System.out.print(parent.data+" ");
}// 層次遍歷二叉樹
public void LayerOrder(BinTree parent)
{
elements[0]=parent;
front=0;rear=1;
while(front<rear)
{
try
{
if(elements[front].data!=null)
{
System.out.print(elements[front].data + " ");
if(elements[front].left!=null)
elements[rear++]=elements[front].left;
if(elements[front].right!=null)
elements[rear++]=elements[front].right;
front++;
}
}catch(Exception e){break;}
}
}//返回樹的葉節點個數
public int leaves()
{
if(this == null)
return 0;
if(left == null&&right == null)
return 1;
return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());
}//結果返回樹的高度
public int height()
{
int heightOfTree;
if(this == null)
return -1;
int leftHeight = (left == null ? 0 : left.height());
int rightHeight = (right == null ? 0 : right.height());
heightOfTree = leftHeight<rightHeight?rightHeight:leftHeight;
return 1 + heightOfTree;
}
//如果對象不在樹中,結果返回-1;否則結果返回該對象在樹中所處的層次,規定根節點為第一層
public int level(Object object)
{
int levelInTree;
if(this == null)
return -1;
if(object == data)
return 1;//規定根節點為第一層
int leftLevel = (left == null?-1:left.level(object));
int rightLevel = (right == null?-1:right.level(object));
if(leftLevel<0&&rightLevel<0)
return -1;
levelInTree = leftLevel<rightLevel?rightLevel:leftLevel;
return 1+levelInTree;
}
//將樹中的每個節點的孩子對換位置
public void reflect()
{
if(this == null)
return;
if(left != null)
left.reflect();
if(right != null)
right.reflect();
BinTree temp = left;
left = right;
right = temp;
}// 將樹中的所有節點移走,並輸出移走的節點
public void defoliate()
{
String innerNode = "";
if(this == null)
return;
//若本節點是葉節點，則將其移走
if(left==null&&right == null)
{
System.out.print(this + " ");
data = null;
return;
}
//移走左子樹若其存在
if(left!=null){
left.defoliate();
left = null;
}
//移走本節點，放在中間表示中跟移走...
innerNode += this + " ";
data = null;
//移走右子樹若其存在
if(right!=null){
right.defoliate();
right = null;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BinTree e = new BinTree("E");
BinTree g = new BinTree("G");
BinTree h = new BinTree("H");
BinTree i = new BinTree("I");
BinTree d = new BinTree("D",null,g);
BinTree f = new BinTree("F",h,i);
BinTree b = new BinTree("B",d,e);
BinTree c = new BinTree("C",f,null);
BinTree tree = new BinTree("A",b,c);
System.out.println("前序遍歷二叉樹結果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍歷二叉樹結果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("後序遍歷二叉樹結果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("層次遍歷二叉樹結果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的層次: "+tree.level("F"));
System.out.println("這棵二叉樹的高度: "+tree.height());
System.out.println("--------------------------------------");
tree.reflect();
System.out.println("交換每個節點的孩子節點後......");
System.out.println("前序遍歷二叉樹結果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍歷二叉樹結果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("後序遍歷二叉樹結果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("層次遍歷二叉樹結果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的層次: "+tree.level("F"));
System.out.println("這棵二叉樹的高度: "+tree.height());
}
Ⅳ java中什麼叫二插數
二叉樹是每個結點最多有兩個子樹的有序樹。通常子樹的根被稱作「左子樹「和「右子樹」。二叉樹常被用作二叉查找樹和二叉堆。二叉樹的每個結點至多隻有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的（i-1）次方個結點；深度為k的二叉樹至多有2^(k) − 1個結點；對任何一棵二叉樹T，如果其終端結點數(即葉子結點數)為n0，度為2的結點數為n2，則n0 = n2 + 1。
Ⅳ 在用java寫二叉搜索樹的時候，「Key extends Comparable<Key>「怎麼理解
現在Comparable改成泛型了，以後新寫的代碼最好要在後面的<>給出類型
Key extends Comparable<Key>
為了兼容以前的代碼，所以像Key extends Comparable也能用，大概就相當於Key extends Comparable<Object>吧
比如還有Class，以前Class c=String.class;以後最好寫成Class<String> c=String.class;了，或者Class<> c=String.class;
Ⅵ java 由字元串構成的二叉樹
java構造二叉樹，可以通過鏈表來構造，如下代碼：
public class BinTree {public final static int MAX=40;BinTree []elements = new BinTree[MAX];//層次遍歷時保存各個節點 int front;//層次遍歷時隊首 int rear;//層次遍歷時隊尾private Object data; //數據元數private BinTree left,right; //指向左,右孩子結點的鏈public BinTree(){}public BinTree(Object data){ //構造有值結點 this.data = data; left = right = null;}public BinTree(Object data,BinTree left,BinTree right){ //構造有值結點 this.data = data; this.left = left; this.right = right;}public String toString(){ return data.toString();}//前序遍歷二叉樹public static void preOrder(BinTree parent){ if(parent == null) return; System.out.print(parent.data+" "); preOrder(parent.left); preOrder(parent.right);}//中序遍歷二叉樹public void inOrder(BinTree parent){ if(parent == null) return; inOrder(parent.left); System.out.print(parent.data+" "); inOrder(parent.right);}//後序遍歷二叉樹public void postOrder(BinTree parent){ if(parent == null) return; postOrder(parent.left); postOrder(parent.right); System.out.print(parent.data+" ");}// 層次遍歷二叉樹 public void LayerOrder(BinTree parent){ elements[0]=parent; front=0;rear=1; while(front<rear) { try { if(elements[front].data!=null) { System.out.print(elements[front].data + " "); if(elements[front].left!=null) elements[rear++]=elements[front].left; if(elements[front].right!=null) elements[rear++]=elements[front].right; front++; } }catch(Exception e){break;} }}//返回樹的葉節點個數public int leaves(){ if(this == null) return 0; if(left == null&&right == null) return 1; return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());}//結果返回樹的高度public int height(){ int heightOfTree; if(this == null) return -1; int leftHeight = (left == null ? 0 : left.height()); int rightHeight = (right == null ? 0 : right.height()); heightOfTree = leftHeight<rightHeight?rightHeight:leftHeight; return 1 + heightOfTree;}//如果對象不在樹中,結果返回-1;否則結果返回該對象在樹中所處的層次,規定根節點為第一層public int level(Object object){ int levelInTree; if(this == null) return -1; if(object == data) return 1;//規定根節點為第一層 int leftLevel = (left == null?-1:left.level(object)); int rightLevel = (right == null?-1:right.level(object)); if(leftLevel<0&&rightLevel<0) return -1; levelInTree = leftLevel<rightLevel?rightLevel:leftLevel; return 1+levelInTree; }//將樹中的每個節點的孩子對換位置public void reflect(){ if(this == null) return; if(left != null) left.reflect(); if(right != null) right.reflect(); BinTree temp = left; left = right; right = temp;}// 將樹中的所有節點移走,並輸出移走的節點public void defoliate(){ if(this == null) return; //若本節點是葉節點，則將其移走 if(left==null&&right == null) { System.out.print(this + " "); data = null; return; } //移走左子樹若其存在 if(left!=null){ left.defoliate(); left = null; } //移走本節點，放在中間表示中跟移走... String innerNode += this + " "; data = null; //移走右子樹若其存在 if(right!=null){ right.defoliate(); right = null; }} /*** @param args*/public static void main(String[] args) { // TODO Auto-generated method stub BinTree e = new BinTree("E"); BinTree g = new BinTree("G"); BinTree h = new BinTree("H"); BinTree i = new BinTree("I"); BinTree d = new BinTree("D",null,g); BinTree f = new BinTree("F",h,i); BinTree b = new BinTree("B",d,e); BinTree c = new BinTree("C",f,null); BinTree tree = new BinTree("A",b,c); System.out.println("前序遍歷二叉樹結果: "); tree.preOrder(tree); System.out.println(); System.out.println("中序遍歷二叉樹結果: "); tree.inOrder(tree); System.out.println(); System.out.println("後序遍歷二叉樹結果: "); tree.postOrder(tree); System.out.println(); System.out.println("層次遍歷二叉樹結果: "); tree.LayerOrder(tree); System.out.println(); System.out.println("F所在的層次: "+tree.level("F")); System.out.println("這棵二叉樹的高度: "+tree.height()); System.out.println("--------------------------------------"); tree.reflect(); System.out.println("交換每個節點的孩子節點後......"); System.out.println("前序遍歷二叉樹結果: "); tree.preOrder(tree); System.out.println(); System.out.println("中序遍歷二叉樹結果: "); tree.inOrder(tree); System.out.println(); System.out.println("後序遍歷二叉樹結果: "); tree.postOrder(tree); System.out.println(); System.out.println("層次遍歷二叉樹結果: "); tree.LayerOrder(tree); System.out.println(); System.out.println("F所在的層次: "+tree.level("F")); System.out.println("這棵二叉樹的高度: "+tree.height());
Ⅶ java數據結構二叉樹查找結點操作，遞歸調用求詳細講解
這是先序遍歷樹的代碼，什麼是先序遍歷呢，一種按照根-左子樹-右子樹的順序遍歷樹就是先序遍歷。
CBTType TreeFindNode(CBTType treeNode,String data){
CBTType ptr;
if(treeNode==null){//輸入根節點為空時
return null;
}else{
if(treeNode.data.equals(data)){//根節點等於要查找的數據時
return treeNode;
}else{
if((ptr=TreeFindNode(treeNode.left,data))!=null){//從左子樹查找，為什麼可以用TreeFindNode表示呢？
return ptr;
}else if((ptr=TreeFindNode(treeNode.right,data))!=null){//從右子樹查找
return ptr;
}else{
return null;
}
}
}
}
從左子樹查找，為什麼可以用TreeFindNode表示呢？因為，左子樹也可以按照先序遍歷的順序查找的，所以當然可以用TreeFindNode表示，如果你想左子樹用中序遍歷查找，那麼就不可以用TreeFindNode表示。
上述例子的查找過程：
1 --根（2，4，5）--左（3，6，7）--右
2--根（4）--左（5）--右
4--根
5--根
返回
Ⅷ 用java怎麼構造一個二叉樹呢
二叉樹的相關操作，包括創建，中序、先序、後序（遞歸和非遞歸），其中重點的是java在先序創建二叉樹和後序非遞歸遍歷的的實現。
package com.algorithm.tree;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;
public class Tree<T> {
private Node<T> root;
public Tree() {
}
public Tree(Node<T> root) {
this.root = root;
}
//創建二叉樹
public void buildTree() {
Scanner scn = null;
try {
scn = new Scanner(new File("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
root = createTree(root,scn);
}
//先序遍歷創建二叉樹
private Node<T> createTree(Node<T> node,Scanner scn) {
String temp = scn.next();
if (temp.trim().equals("#")) {
return null;
} else {
node = new Node<T>((T)temp);
node.setLeft(createTree(node.getLeft(), scn));
node.setRight(createTree(node.getRight(), scn));
return node;
}
}
//中序遍歷(遞歸)
public void inOrderTraverse() {
inOrderTraverse(root);
}
public void inOrderTraverse(Node<T> node) {
if (node != null) {
inOrderTraverse(node.getLeft());
System.out.println(node.getValue());
inOrderTraverse(node.getRight());
}
}
//中序遍歷(非遞歸)
public void nrInOrderTraverse() {
Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
node = stack.pop();
System.out.println(node.getValue());
node = node.getRight();
}
}
//先序遍歷(遞歸)
public void preOrderTraverse() {
preOrderTraverse(root);
}
public void preOrderTraverse(Node<T> node) {
if (node != null) {
System.out.println(node.getValue());
preOrderTraverse(node.getLeft());
preOrderTraverse(node.getRight());
}
}
//先序遍歷（非遞歸）
public void nrPreOrderTraverse() {
Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
System.out.println(node.getValue());
stack.push(node);
node = node.getLeft();
}
node = stack.pop();
node = node.getRight();
}
}
//後序遍歷(遞歸)
public void postOrderTraverse() {
postOrderTraverse(root);
}
public void postOrderTraverse(Node<T> node) {
if (node != null) {
postOrderTraverse(node.getLeft());
postOrderTraverse(node.getRight());
System.out.println(node.getValue());
}
}
//後續遍歷(非遞歸)
public void nrPostOrderTraverse() {
Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;
Node<T> preNode = null;//表示最近一次訪問的節點
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
node = stack.peek();
if (node.getRight() == null || node.getRight() == preNode) {
System.out.println(node.getValue());
node = stack.pop();
preNode = node;
node = null;
} else {
node = node.getRight();
}
}
}
//按層次遍歷
public void levelTraverse() {
levelTraverse(root);
}
public void levelTraverse(Node<T> node) {
Queue<Node<T>> queue = new LinkedBlockingQueue<Node<T>>();
queue.add(node);
while (!queue.isEmpty()) {
Node<T> temp = queue.poll();
if (temp != null) {
System.out.println(temp.getValue());
queue.add(temp.getLeft());
queue.add(temp.getRight());
}
}
}
}
//樹的節點
class Node<T> {
private Node<T> left;
private Node<T> right;
private T value;
public Node() {
}
public Node(Node<T> left,Node<T> right,T value) {
this.left = left;
this.right = right;
this.value = value;
}
public Node(T value) {
this(null,null,value);
}
public Node<T> getLeft() {
return left;
}
public void setLeft(Node<T> left) {
this.left = left;
}
public Node<T> getRight() {
return right;
}
public void setRight(Node<T> right) {
this.right = right;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
}
測試代碼：
package com.algorithm.tree;
public class TreeTest {
/**
* @param args
*/
public static void main(String[] args) {
Tree<Integer> tree = new Tree<Integer>();
tree.buildTree();
System.out.println("中序遍歷");
tree.inOrderTraverse();
tree.nrInOrderTraverse();
System.out.println("後續遍歷");
//tree.nrPostOrderTraverse();
tree.postOrderTraverse();
tree.nrPostOrderTraverse();
System.out.println("先序遍歷");
tree.preOrderTraverse();
tree.nrPreOrderTraverse();
//
}
}
Ⅸ 用JAVA寫二叉樹
/**
* [Tree2.java] Create on 2008-10-20 下午03:03:24
* Copyright (c) 2008 by iTrusChina.
*/
/**
* @author WangXuanmin
* @version 0.10
*/
public class Tree2Bef {
private StringBuffer bef=new StringBuffer();
//傳入中序遍歷和後序遍歷,返回前序遍歷字串
public String getBef(String mid, String beh) {
//若節點存在則向bef中添加該節點,繼續查詢該節點的左子樹和右子樹
if (root(mid, beh) != -1) {
int rootindex=root(mid, beh);
char root=mid.charAt(rootindex);
bef.append(root);
System.out.println(bef.toString());
String mleft, mright;
mleft = mid.substring(0,rootindex);
mright = mid.substring(rootindex+1);
getBef(mleft,beh);
getBef(mright,beh);
}
//所有節點查詢完畢,返回前序遍歷值
return bef.toString();
}
//從中序遍歷中根據後序遍歷查找節點索引值index
private int root(String mid, String beh) {
char[] midc = mid.toCharArray();
char[] behc = beh.toCharArray();
for (int i = behc.length-1; i > -1; i--) {
for (int j = 0; j < midc.length; j++) {
if (behc[i] == midc[j])
return j;
}
}
return -1;
}
public static void main(String[] args) {
Tree2Bef tree=new Tree2Bef();
String mid="84925163A7B";
String bef="894526AB731";
System.out.println(tree.getBef(mid,bef));
}
}
樹結構如圖:
1
|-------|
2 3
|---| |---|
4 5 6 7
|-| |-|
8 9 A B