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）棵互不相交的樹構成一片森林。如果把一棵非空的樹的根結點刪除，則該樹就變成了一片森林，森林中的樹由原來根結點的各棵子樹構成。