二叉樹的深度遍歷java

A. java中二叉樹的深度怎麼計算

若為空,則其深度為0,否則,其深度等於左子樹和右子樹的深度的最大值加1

B. 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

C. 二叉樹的層次遍歷演算法

二叉樹的層次遍歷演算法有如下三種方法：

給定一棵二叉樹，要求進行分層遍歷，每層的節點值單獨列印一行，下圖給出事例結構：

之後大家就可以自己畫圖了，下面給出程序代碼：

[cpp] view plain

void print_by_level_3(Tree T) {

vector<tree_node_t*> vec;

vec.push_back(T);

int cur = 0;

int end = 1;

while (cur < vec.size()) {

end = vec.size();

while (cur < end) {

cout << vec[cur]->data << " ";

if (vec[cur]->lchild)

vec.push_back(vec[cur]->lchild);

if (vec[cur]->rchild)

vec.push_back(vec[cur]->rchild);

cur++;

}

cout << endl;

}

}

最後給出完成代碼的測試用例：124##57##8##3#6##

[cpp] view plain

#include<iostream>

#include<vector>

#include<deque>

using namespace std;

typedef struct tree_node_s {

char data;

struct tree_node_s *lchild;

struct tree_node_s *rchild;

}tree_node_t, *Tree;

void create_tree(Tree *T) {

char c = getchar();

if (c == '#') {

*T = NULL;

} else {

*T = (tree_node_t*)malloc(sizeof(tree_node_t));

(*T)->data = c;

create_tree(&(*T)->lchild);

create_tree(&(*T)->rchild);

}

}

void print_tree(Tree T) {

if (T) {

cout << T->data << " ";

print_tree(T->lchild);

print_tree(T->rchild);

}

}

int print_at_level(Tree T, int level) {

if (!T || level < 0)

return 0;

if (0 == level) {

cout << T->data << " ";

return 1;

}

return print_at_level(T->lchild, level - 1) + print_at_level(T->rchild, level - 1);

}

void print_by_level_1(Tree T) {

int i = 0;

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

if (!print_at_level(T, i))

break;

}

cout << endl;

}

void print_by_level_2(Tree T) {

deque<tree_node_t*> q_first, q_second;

q_first.push_back(T);

while(!q_first.empty()) {

while (!q_first.empty()) {

tree_node_t *temp = q_first.front();

q_first.pop_front();

cout << temp->data << " ";

if (temp->lchild)

q_second.push_back(temp->lchild);

if (temp->rchild)

q_second.push_back(temp->rchild);

}

cout << endl;

q_first.swap(q_second);

}

}

void print_by_level_3(Tree T) {

vector<tree_node_t*> vec;

vec.push_back(T);

int cur = 0;

int end = 1;

while (cur < vec.size()) {

end = vec.size();

while (cur < end) {

cout << vec[cur]->data << " ";

if (vec[cur]->lchild)

vec.push_back(vec[cur]->lchild);

if (vec[cur]->rchild)

vec.push_back(vec[cur]->rchild);

cur++;

}

cout << endl;

}

}

int main(int argc, char *argv[]) {

Tree T = NULL;

create_tree(&T);

print_tree(T);

cout << endl;

print_by_level_3(T);

cin.get();

cin.get();

return 0;

}

D. java實現二叉樹的問題

/**
* 二叉樹測試二叉樹順序存儲在treeLine中，遞歸前序創建二叉樹。另外還有能
* 夠前序、中序、後序、按層遍歷二叉樹的方法以及一個返回遍歷結果asString的
* 方法。
*/

public class BitTree {
public static Node2 root;
public static String asString;

//事先存入的數組,符號#表示二叉樹結束。
public static final char[] treeLine = {'a','b','c','d','e','f','g',' ',' ','j',' ',' ','i','#'};

//用於標志二叉樹節點在數組中的存儲位置，以便在創建二叉樹時能夠找到節點對應的數據。
static int index;

//構造函數
public BitTree() {
System.out.print("測試二叉樹的順序表示為：");
System.out.println(treeLine);
this.index = 0;
root = this.setup(root);
}

//創建二叉樹的遞歸程序
private Node2 setup(Node2 current) {
if (index >= treeLine.length) return current;
if (treeLine[index] == '#') return current;
if (treeLine[index] == ' ') return current;
current = new Node2(treeLine[index]);
index = index * 2 + 1;
current.left = setup(current.left);
index ++;
current.right = setup(current.right);
index = index / 2 - 1;
return current;
}

//二叉樹是否為空。
public boolean isEmpty() {
if (root == null) return true;
return false;
}

//返回遍歷二叉樹所得到的字元串。
public String toString(int type) {
if (type == 0) {
asString = "前序遍歷：\t";
this.front(root);
}
if (type == 1) {
asString = "中序遍歷：\t";
this.middle(root);
}
if (type == 2) {
asString = "後序遍歷：\t";
this.rear(root);
}
if (type == 3) {
asString = "按層遍歷：\t";
this.level(root);
}
return asString;
}

//前序遍歷二叉樹的循環演算法，每到一個結點先輸出，再壓棧，然後訪問它的左子樹，
//出棧，訪問其右子樹，然後該次循環結束。
private void front(Node2 current) {
StackL stack = new StackL((Object)current);
do {
if (current == null) {
current = (Node2)stack.pop();
current = current.right;
} else {
asString += current.ch;
current = current.left;
}
if (!(current == null)) stack.push((Object)current);
} while (!(stack.isEmpty()));
}

//中序遍歷二叉樹
private void middle(Node2 current) {
if (current == null) return;
middle(current.left);
asString += current.ch;
middle(current.right);
}

//後序遍歷二叉樹的遞歸演算法
private void rear(Node2 current) {
if (current == null) return;
rear(current.left);
rear(current.right);
asString += current.ch;
}

}

/**
* 二叉樹所使用的節點類。包括一個值域兩個鏈域
*/

public class Node2 {
char ch;
Node2 left;
Node2 right;

//構造函數
public Node2(char c) {
this.ch = c;
this.left = null;
this.right = null;
}

//設置節點的值
public void setChar(char c) {
this.ch = c;
}

//返回節點的值
public char getChar() {
return ch;
}

//設置節點的左孩子
public void setLeft(Node2 left) {
this.left = left;
}

//設置節點的右孩子
public void setRight (Node2 right) {
this.right = right;
}

//如果是葉節點返回true
public boolean isLeaf() {
if ((this.left == null) && (this.right == null)) return true;
return false;
}
}

一個作業題，裡面有你要的東西。
主函數自己寫吧。當然其它地方也有要改的。