java树的深度
1. java中二叉树的深度怎么计算
若为空,则其深度为0,否则,其深度等于左子树和右子树的深度的最大值加1
2. 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) ), )))
3. 什么是树的遍历java
树遍历方法:有先序遍历、中序遍历、后序遍历以及广度优先遍历四种遍历树的方法
Demo:
publicclassThreeLinkBinTree<E>{
publicstaticclassTreeNode{
Objectdata;
TreeNodeleft;
TreeNoderight;
TreeNodeparent;
publicTreeNode(){
}
publicTreeNode(Objectdata){
this.data=data;
}
publicTreeNode(Objectdata,TreeNodeleft,TreeNoderight,TreeNodeparent){
this.data=data;
this.left=left;
this.right=right;
this.parent=parent;
}
}
privateTreeNoderoot;
//以默认的构造器创建二叉树
publicThreeLinkBinTree(){
this.root=newTreeNode();
}
//以指定根元素创建二叉树
publicThreeLinkBinTree(Edata){
this.root=newTreeNode(data);
}
/**
*为指定节点添加子节点
*
*@paramparent需要添加子节点的父节点的索引
*@paramdata新子节点的数据
*@paramisLeft是否为左节点
*@return新增的节点
*/
publicTreeNodeaddNode(TreeNodeparent,Edata,booleanisLeft){
if(parent==null){
thrownewRuntimeException(parent+"节点为null，无法添加子节点");
}
if(isLeft&&parent.left!=null){
thrownewRuntimeException(parent+"节点已有左子节点，无法添加左子节点");
}
if(!isLeft&&parent.right!=null){
thrownewRuntimeException(parent+"节点已有右子节点，无法添加右子节点");
}
TreeNodenewNode=newTreeNode(data);
if(isLeft){
//让父节点的left引用指向新节点
parent.left=newNode;
}else{
//让父节点的left引用指向新节点
parent.right=newNode;
}
//让新节点的parent引用到parent节点
newNode.parent=parent;
returnnewNode;
}
//判断二叉树是否为空
publicbooleanempty(){
//根据元素判断二叉树是否为空
returnroot.data==null;
}
//返回根节点
publicTreeNoderoot(){
if(empty()){
thrownewRuntimeException("树为空，无法访问根节点");
}
returnroot;
}
//返回指定节点（非根节点）的父节点
publicEparent(TreeNodenode){
if(node==null){
thrownewRuntimeException("节点为null，无法访问其父节点");
}
return(E)node.parent.data;
}
//返回指定节点（非叶子）的左子节点，当左子节点不存在时返回null
publicEleftChild(TreeNodeparent){
if(parent==null){
thrownewRuntimeException(parent+"节点为null，无法添加子节点");
}
returnparent.left==null?null:(E)parent.left.data;
}
//返回指定节点（非叶子）的右子节点，当右子节点不存在时返回null
publicErightChild(TreeNodeparent){
if(parent==null){
thrownewRuntimeException(parent+"节点为null，无法添加子节点");
}
returnparent.right==null?null:(E)parent.right.data;
}
//返回该二叉树的深度
publicintdeep(){
//获取该树的深度
returndeep(root);
}
//这是一个递归方法：每一棵子树的深度为其所有子树的最大深度+1
privateintdeep(TreeNodenode){
if(node==null){
return0;
}
//没有子树
if(node.left==null&&node.right==null){
return1;
}else{
intleftDeep=deep(node.left);
intrightDeep=deep(node.right);
//记录其所有左、右子树中较大的深度
intmax=leftDeep>rightDeep?leftDeep:rightDeep;
//返回其左右子树中较大的深度+1
returnmax+1;
}
}
//实现先序遍历
//1、访问根节点
//2、递归遍历左子树
//3、递归遍历右子树
publicList<TreeNode>preIterator(){
returnpreIterator(root);
}
privateList<TreeNode>preIterator(TreeNodenode){
List<TreeNode>list=newArrayList<TreeNode>();
//处理根节点
list.add(node);
//递归处理左子树
if(node.left!=null){
list.addAll(preIterator(node.left));
}
//递归处理右子树
if(node.right!=null){
list.addAll(preIterator(node.right));
}
returnlist;
}
//实现中序遍历
//1、递归遍历左子树
//2、访问根节点
//3、递归遍历右子树
publicList<TreeNode>inIterator(){
returninIterator(root);
}
privateList<TreeNode>inIterator(TreeNodenode){
List<TreeNode>list=newArrayList<TreeNode>();
//递归处理左子树
if(node.left!=null){
list.addAll(inIterator(node.left));
}
//处理根节点
list.add(node);
//递归处理右子树
if(node.right!=null){
list.addAll(inIterator(node.right));
}
returnlist;
}
//实现后序遍历
//1、递归遍历左子树
//2、递归遍历右子树
//3、访问根节点
publicList<TreeNode>postIterator(){
returnpostIterator(root);
}
privateList<TreeNode>postIterator(TreeNodenode){
List<TreeNode>list=newArrayList<TreeNode>();
//递归处理左子树
if(node.left!=null){
list.addAll(postIterator(node.left));
}
//递归处理右子树
if(node.right!=null){
list.addAll(postIterator(node.right));
}
//处理根节点
list.add(node);
returnlist;
}
//实现广度优先遍历
//广度优先遍历又称为按层遍历，整个遍历算法先遍历二叉树的第一层（根节点），再遍历根节点的两个子节点（第二层），以此类推
publicList<TreeNode>breadthFirst(){
Queue<TreeNode>queue=newArrayDeque<TreeNode>();
List<TreeNode>list=newArrayList<TreeNode>();
if(root!=null){
//将根元素加入“队列”
queue.offer(root);
}
while(!queue.isEmpty()){
//将该队列的“队尾”的元素添加到List中
list.add(queue.peek());
TreeNodep=queue.poll();
//如果左子节点不为null，将它加入“队列”
if(p.left!=null){
queue.offer(p.left);
}
//如果右子节点不为null，将它加入“队列”
if(p.right!=null){
queue.offer(p.right);
}
}
returnlist;
}
}
4. java问题
只要加到比较方法之中就可以
如：比较方法如下
for(int i=0;i<100;i++)
for(int j=i;j<100;j++){
if(array[i]>array[j]){
int temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
把：：
比较次数compare_count、交换次数exchange_count、探测次数probe_count）加到里面就可以
for(int i=0,compare_count=0;i<100;i++)
for(int j=i;j<100;j++){
if(array[i]>array[j]){
compare_count++;
int temp=array[i];
array[i]=array[j];
array[j]=temp;
exchange_count++;
}
}
就可以了
各种排序方法的综合比较
一、时间性能
按平均的时间性能来分，有三类排序方法：
时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；
时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此；
时间复杂度为O(n)的排序方法只有，基数排序。
当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。
简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
二、空间性能
指的是排序过程中所需的辅助空间大小。
1. 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；
2. 快速排序为O(logn )，为栈所需的辅助空间;
3. 归并排序所需辅助空间最多，其空间复杂度为O(n );
4.链式基数排序需附设队列首尾指针，则空间复杂度为O(rd )。
三、排序方法的稳定性能
1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。
2. 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。
3. 对于不稳定的排序方法，只要能举出一个实例说明即可。
4. 快速排序和堆排序是不稳定的排序方法。
四、关于“排序方法的时间复杂度的下限”
本章讨论的各种排序方法，除基数排序外，其它方法都是基于“比较关键字”进行排序的排序方法，可以证明，这类排序法可能达到的最快的时间复杂度为O(n logn )。(基数排序不是基于“比较关键字”的排序方法,所以它不受这个限制)。
可以用一棵判定树来描述这类基于“比较关键字”进行排序的排序方法。
例如，对三个关键字进行排序的判定树如下：
描述排序的判定树有两个特点：
1.树上的每一次“比较”都是必要的;
2.树上的叶子结点包含所有可能情况。
则由上图所示“判定树的深度为4”可以推出“至多进行三次比较”即可完成对三个关键字的排序。反过来说，由此判定树可见，考虑最坏情况，“至少要进行三次比较”才能完成对三个关键字的排序。
对三个关键字进行排序的判定树深度是唯一的。即无论按什么先后顺序去进行比较，所得判定树的深度都是3。
当关键字的个数超过3之后，不同的排序方法其判定树的深度不同。例如，对4个关键字进行排序时，直接插入的判定树的深度为6, 而折半插入的判定树的深度为5。
可以证明，对4个关键字进行排序，至少需进行5次比较。因为，4个关键字排序的结果有4!=24种可能，即排序的判定树上必须有24个叶子结点，其深度的最小值为6。
一般情况下，对n个关键字进行排序，可能得到的结果有n! 种，由于含n! 个叶子结点的二叉树的深度不小于 , 则对n个关键字进行排序的比较次数至少是
。利用斯蒂林近似公式
所以，基于“比较关键字”进行排序的排序方法，可能达到的最快的时间复杂度为O(n logn )。
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：
1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；
2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；
3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；
4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；
5）、重复第3、4步，直到I=J；
例如：待排序的数组A的值分别是：（初始关键数据X：=49）
A[1] A[2] A[3] A[4] A[5] A[6] A[7]：
49 38 65 97 76 13 27
进行第一次交换后： 27 38 65 97 76 13 49
( 按照算法的第三步从后面开始找
进行第二次交换后： 27 38 49 97 76 13 65
( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时I：=3 )
进行第三次交换后： 27 38 13 97 76 49 65
( 按照算法的第五步将又一次执行算法的第三步从后开始找
进行第四次交换后： 27 38 13 49 76 97 65
( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 )
此时再执行第三不的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。
快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：
初始状态 {49 38 65 97 76 13 27}
进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}
分别对前后两部分进行快速排序 {13} 27 {38}
结束 结束 {49 65} 76 {97}
49 {65} 结束
结束
图6 快速排序全过程
1）、设有N（假设N=10）个数，存放在S数组中；
2）、在S[1。。N]中任取一个元素作为比较基准，例如取T=S[1]，起目的就是在定出T应在排序结果中的位置K，这个K的位置在：S[1。。K-1]<=S[K]<=S[K+1..N]，即在S[K]以前的数都小于S[K]，在S[K]以后的数都大于S[K]；
3）、利用分治思想（即大化小的策略）可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。 1 2 3 4 5 6 7 8 9 10
如具体数据如下，那么第一躺快速排序的过程是：
数组下标：
45 36 18 53 72 30 48 93 15 36
5） 36 36 18 15 30 45 48 93 72 534） 36 36 18 15 45 30 48 93 72 533） 36 36 18 15 72 30 48 93 45 532） 36 36 18 45 72 30 48 93 15 53
program kuaisu(input,output);
const n=10;
var
s:array[1..10] of integer;
k,l,m:integer;
procere qsort(lx,rx:integer);
var
I,j,t:integer;
Begin
I:lx;j:rx;t:s[I];
Repeat
While (s[j]>t) and (j>I) do
Begin
k:=k+1;
j:=j-1
end;
if I<j then
begin
s[I]:=s[j];I:=I+1;l:=l+1;
while (s[I]<t) and (I<j) do
begin
k:=k+1;
I:=I+1
End;
If I<j then
begin
S[j]:=s[I];j:=j-1;l:=l+1;
End;
End;
Until I=j;
S[I]:=t;I:=I+1;j:=j-1;l:=l+1;
If lx<j then qsort(lx,j);
If I<rx then qsort(I,rx)
End;{过程qsort结束}
Begin
Writeln('input 10 integer num:');
For m:=1 to n do read(s[m]);
K:=0;l:=0;
Qsort(l,n);
Writeln('排序后结果是：')；
For m:=1 to n do write(s[m]:4)
End.
通过一躺排序将45放到应该放的位置K，这里K=6，那么再对S[1。。5]和S[6。。10]分别进行快速排序。程序代码如下：<49,两者交换，此时J:=6>
5. java，求二叉树的深度的算法实现
用递归很简单了。
BTNode类就自己定义吧，属性为名字，和左右孩子以及set、get方法
前序遍历：
protected static void preorder(BTNode node) {
if (node != null) {
visit(node);//随便写点打印p的名字之类的语句
preorder(node.getLeft());
preorder(node.getRight());
}
}
中序：
protected static void inorder(BTNode node) {
if (node != null) {
inorder(node.getLeft());
visit(node);
inorder(node.getRight());
}
}
后序：
protected static void postorder(BTNode node) {
if (node != null) {
postorder(node.getLeft());
postorder(node.getRight());
visit(node);
}
}
非递归的就麻烦了，得用到栈。我就偷个懒不做了...
6. java二叉树遍历问题
二叉树具有以下重要性质：
性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。
证明：用数学归纳法证明：
归纳基础：i=1时，有2i-1=20=1。因为第1层上只有一个根结点，所以命题成立。
归纳假设：假设对所有的j(1≤j<i)命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。
归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2×2i-2=2i-1个结点，故命题成立。
性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。
证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为：
20+21+…+2k-1=2k-1
故命题正确。
性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。
证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数之和：
n=no+n1+n2 (式子1)
另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：
nl+2n2
树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：
n=n1+2n2+1 (式子2)
由式子1和式子2得到：
no=n2+1
满二叉树和完全二叉树是二叉树的两种特殊情形。
1、满二叉树(FullBinaryTree)
一棵深度为k且有2k-1个结点的二又树称为满二叉树。
满二叉树的特点：
（1） 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。
（2） 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。
图(a)是一个深度为4的满二叉树。
2、完全二叉树(Complete BinaryTree)
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
特点：
（1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
（2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
（3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。
如图(c)中，结点F没有左孩子而有右孩子L，故它不是一棵完全二叉树。
图(b)是一棵完全二叉树。
性质4 具有n个结点的完全二叉树的深度为
证明：设所求完全二叉树的深度为k。由完全二叉树定义可得：
深度为k得完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。
由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数：
n>2k-1-1。
另一方面，由性质2可得：
n≤2k-1，
即：2k-1-l<n≤2k-1
由此可推出：2k-1≤n<2k，取对数后有：
k-1≤lgn<k
又因k-1和k是相邻的两个整数，故有
,
由此即得：
注意：
的证明
7. 在线等，计算机高手，java深度搜索树代码
有一本书，是讲JAVA数据结构的，里面有很多树的讲解和例子，二叉树什么的，还有树的遍历，都有例子，建议去看一下