java求二叉树深度

Ⅰ java中二叉树的深度怎么计算

若为空,则其深度为0,否则,其深度等于左子树和右子树的深度的最大值加1

Ⅱ 写一个求二叉树的深度的算法

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
char data;
struct node *left,*right;
}Node,*PNode;
PNode createBtree(PNode root)//创建二叉树，控制台下输入，基于先序遍历输入
{
char data;
scanf("%c",&data);
if (data==' ')
{
root=NULL;
return root;
}
root = (PNode)malloc(sizeof(Node));
root->data = data;
root->left = createBtree(root->left);
root->right = createBtree(root->right);

return root;
}

int depth(PNode root)//这就是你要的函数。
{
int ld,rd;
if (root==NULL)
{
return 0;
}
ld = 1+depth(root->left);
rd = 1+depth(root->right);
return ld>rd?ld:rd;
}
int main()
{
PNode root=NULL;
root = createBtree(root);
printf("%d",depth(root));
return 0;
}

为了测试，写了二叉树的建立程序；
如下输入可以看到结果
虚节点用空格输入的。例如你输入
先序遍历
234空格空格5空格6空格空格7空格空格回车就可以看到结果。
另外，本算法是从1开始算深度的，就是根节点是深度下。

Ⅲ 用java编写一个程序用递归算法计算二叉树的高度、叶子数

//************树的深度******************
public int depth(BinTreeNode p){
if(p == null)
return 0;
else if(depth(p.lChild)<(depth(p.rChild))){
return depth(p.rChild)+1;
}else{
return depth(p.lChild)+1;
}
}
public int depth(){
return depth(root);

}

Ⅳ 如何求二叉树深度

二叉树性质如下：
1
：在二叉树的第i层上至少有2^（i-1）个结点
2：深度为k的二叉树至多有2^(k-1)个结点
3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
4：具有n个结点的完全二叉树的深度是【log2n】+1（向下取整）
5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有：
如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是i/2
如果2i>n，则结点i无左孩子；如果2in，则其左孩子是2i
如果2i+1>n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1
二叉树深度算法如下：
深度为m的满二叉树有2^m-1个结点；
具有n个结点的完全二叉树的深度为[log2n]+1.（log2n是以2为底n的对数）

Ⅳ 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);
}
}
非递归的就麻烦了，得用到栈。我就偷个懒不做了...

Ⅵ 二叉树的性质有些啊怎么求它的深度

二叉树性质如下：

1 ：在二叉树的第i层上至少有2^（i-1）个结点

2：深度为k的二叉树至多有2^(k-1)个结点

3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1

4：具有n个结点的完全二叉树的深度是【log2n】+1（向下取整）

5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有：

如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是i/2

如果2i>n，则结点i无左孩子；如果2in，则其左孩子是2i

如果2i+1>n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1

二叉树深度算法如下：

深度为m的满二叉树有2^m-1个结点；

具有n个结点的完全二叉树的深度为[log2n]+1.（log2n是以2为底n的对数）

(6)java求二叉树深度扩展阅读：

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。具有n个节点的完全二叉树的深度为log2(n+1)。深度为k的完全二叉树，至少有2k-1个节点，至多有2k-1个节点。

二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。

Ⅶ 我想要找一份关于java数据结构二叉树的实例详解（所有基本操作，包括二叉树的高度和节点总数）

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数
//基于先序遍历算法创建二叉树
//要求输入先序序列，其中加入虚结点"#"以示空指针的位置
BinTree CreatBinTree(void){
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //读入#，返回空指针
else{
T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点
T->data=ch;
T->lchild=CreatBinTree(); //构造左子树
T->rchild=CreatBinTree(); //构造右子树
return(T);
}
}
//先序遍历
void Preorder(BinTree T){
if(T){
printf("%c",T->data); //访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild); //先序遍历右子树
}
}
//中序遍历
void Inorder(BinTree T){
if(T){
Inorder(T->lchild); //中序遍历左子树
printf("%c",T->data); //访问结点
Inorder(T->rchild); //中序遍历右子树
}
}
//后序遍历
void Postorder(BinTree T){
if(T){
Postorder(T->lchild); //后序遍历左子树
Postorder(T->rchild); //后序遍历右子树
printf("%c",T->data); //访问结点
}
}
//采用后序遍历求二叉树的深度、结点数及叶子数的递归算法
int TreeDepth(BinTree T){
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求结点数
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。
return(max+1);
}
else return(0);
}
//主函数
void main(){
BinTree root;
int i,depth;
printf("\n");
printf("Creat Bin_Tree； Input preorder:"); //输入完全二叉树的先序序列，
// 用#代表虚结点，如ABD###CE##F##
root=CreatBinTree(); //创建二叉树，返回根结点
do{ //从菜单中选择遍历方式，输入序号。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i); //输入菜单序号（0-4）
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍历
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍历
break;
case 4: depth=TreeDepth(root); //求树的深度及叶子数
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5: printf("LevePrint Bin_Tree: ");
Levelorder(root); //按层次遍历
break;
default: exit(1);
}
printf("\n");
}while(i!=0);
}
//按层遍历
Levelorder( BinTNode *root){
BinTNode * q[Max]; //定义BinTNode类型的队列 用于存放节点 队列长最大为20个元素
int front=0,rear=0; //初始化队列为空
BinTNode *p; //临时节点指针
if(root!=NULL){ //将根节点进队
rear=(rear+1)%Max;
q[rear]=root;
}
while(front!=rear){
front=(front+1)%Max;
p=q[front]; //删除队首的元素 让两个节点（左右节点）孤立
printf("%c",p->data); //输出队列首元素的值
if(p->left!=null){ //如果存在左孩子节点，则左孩子节点进入队列
rear=(rear+1)%Max;
q[rear]=p->left;
}
if(p->right!=null){ //如果存在右孩子节点，则右孩子节点进入队列
rear=(rear+1)%Max;
q[rear]=p->right;
}
}
}

Ⅷ Java数据结构二叉树深度递归调用算法求内部算法过程详解

二叉树

1

2
3
4
5
6
7
这个二叉树的深度是3，树的深度是最大结点所在的层，这里是3.
应该计算所有结点层数，选择最大的那个。
根据上面的二叉树代码，递归过程是：
f
(1)=f
(2)+1
>
f
(3)
+1
?
f(2)
+
1
:
f(3)
+1
f(2)
跟f(3)计算类似上面，要计算左右结点，然后取大者
所以计算顺序是f(4.left)
=
0,
f(4.right)
=
0
f
(4)
=
f(4.right)
+
1
=
1
然后计算f(5.left)
=
0,f(5.right)
=
0
f
(5)
=
f(5.right)
+
1
=1
f(2)
=
f(5)
+
1
=2
f(1.left)
计算完毕，计算f(1.right)
f(3)
跟计算f(2)的过程一样。
得到f(3)
=
f(7)
+1
=
2
f(1)
=
f(3)
+
1
=3
12345if(depleft>depright){ return depleft+1;}else{ return depright+1;}
只有left大于right的时候采取left
+1，相等是取right

Ⅸ 二叉树的深度算法怎么算啊

二叉树的深度算法：
一、递归实现基本思想：
为了求得树的深度，可以先求左右子树的深度，取二者较大者加1即是树的深度，递归返回的条件是若节点为空，返回0
算法：
1
int
FindTreeDeep(BinTree
BT){
2
int
deep=0;
3
if(BT){
4
int
lchilddeep=FindTreeDeep(BT->lchild);
5
int
rchilddeep=FindTreeDeep(BT->rchild);
6
deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;
7
}
8
return
deep;
9
}
二、非递归实现基本思想：
受后续遍历二叉树思想的启发，想到可以利用后续遍历的方法来求二叉树的深度，在每一次输出的地方替换成算栈S的大小，遍历结束后最大的栈S长度即是栈的深度。
算法的执行步骤如下：
（1）当树非空时，将指针p指向根节点，p为当前节点指针。
（2）将p压入栈S中，0压入栈tag中，并令p执行其左孩子。
（3）重复步骤（2），直到p为空。
（4）如果tag栈中的栈顶元素为1，跳至步骤（6）。从右子树返回
（5）如果tag栈中的栈顶元素为0，跳至步骤（7）。从左子树返回
（6）比较treedeep与栈的深度，取较大的赋给treedeep，对栈S和栈tag出栈操作，p指向NULL，并跳至步骤（8）。
（7）将p指向栈S栈顶元素的右孩子，弹出栈tag，并把1压入栈tag。（另外一种方法，直接修改栈tag栈顶的值为1也可以）
（8）循环（2）~（7），直到栈为空并且p为空
（9）返回treedeep，结束遍历
1
int
TreeDeep(BinTree
BT
){
2
int
treedeep=0;
3
stack
S;
4
stack
tag;
5
BinTree
p=BT;
6
while(p!=NULL||!isEmpty(S)){
7
while(p!=NULL){
8
push(S,p);
9
push(tag,0);
10
p=p->lchild;
11
}
12
if(Top(tag)==1){
13
deeptree=deeptree>S.length?deeptree:S.length;
14
pop(S);
15
pop(tag);
16
p=NULL;
17
}else{
18
p=Top(S);
19
p=p->rchild;
20
pop(tag);
21
push(tag,1);
22
}
23
}
24
return
deeptree;
25
}

Ⅹ 二叉树的深度是什么

想知道二叉树的深度就要先要判断节点，以下是计算二叉树的详细步骤：

1、一颗树只有一个节点，它的深度是1；

2、二叉树的根节点只有左子树而没有右子树，那么可以判断，二叉树的深度应该是其左子树的深度加1；

3、二叉树的根节点只有右子树而没有左子树，那么可以判断，那么二叉树的深度应该是其右树的深度加1；

4、二叉树的根节点既有右子树又有左子树，那么可以判断，那么二叉树的深度应该是其左右子树的深度较大值加1。

(10)java求二叉树深度扩展阅读：

从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子节点位于第L+1层。

由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根结点删除，则该树就变成了一片森林，森林中的树由原来根结点的各棵子树构成。