二叉樹深度遍歷java

❶ 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是相鄰的兩個整數，故有
,
由此即得：

注意：
的證明

❷ 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

❸ 急急急！！！要求用java實現二叉樹中序遍歷序列 具體要求如下

第一棵樹只有一個 1 節點，為什麼輸出序列有兩個 1？
第二棵樹只有一個 3 節點，為什麼輸出序列有兩個 3？
題目中的輸出序列是否不正確？

❹ 如何深度優先遍歷二叉樹 java

找一本數據結構的書，上面都有。或者搜索下，http://outofmemory.cn/code-snippet/4189/biinary-tree-java
http://dyygusi.iteye.com/blog/2162617

❺ java 實現二叉樹的層次遍歷

class TreeNode {
public TreeNode left;

public TreeNode right;

public int value;

public TreeNode(TreeNode left, TreeNode right, int value) {
this.left = left;
this.right = right;
this.value = value;
}
}
public class BinaryTree {

public static int getTreeHeight(TreeNode root) {
if (root == null)
return 0;
if (root.left == null && root.right == null)
return 1;
return 1 + Math
.max(getTreeHeight(root.left), getTreeHeight(root.right));
}

public static void recursePreOrder(TreeNode root) {
if (root == null)
return;
System.out.println(root.value);
if (root.left != null)
recursePreOrder(root.left);
if (root.right != null)
recursePreOrder(root.right);
}

public static void stackPreOrder(TreeNode root) {
Stack stack = new Stack();
if (root == null)
return;
stack.push(root);
System.out.println(root.value);
TreeNode temp = root.left;
while (temp != null) {
stack.push(temp);
System.out.println(temp.value);
temp = temp.left;
}
temp = (TreeNode) stack.pop();
while (temp != null) {
temp = temp.right;
while (temp != null) {
stack.push(temp);
System.out.println(temp.value);
temp = temp.left;
}
if (stack.empty())
break;
temp = (TreeNode) stack.pop();
}
}

public static void recurseInOrder(TreeNode root) {
if (root == null)
return;
if (root.left != null)
recurseInOrder(root.left);
System.out.println(root.value);
if (root.right != null)
recurseInOrder(root.right);
}

public static void stackInOrder(TreeNode root) {
Stack stack = new Stack();
if (root == null)
return;
else
stack.push(root);
TreeNode temp = root.left;
while (temp != null) {
stack.push(temp);
temp = temp.left;
}
temp = (TreeNode) stack.pop();
while (temp != null) {
System.out.println(temp.value);
temp = temp.right;
while (temp != null) {
stack.push(temp);
temp = temp.left;
}
if (stack.empty())
break;
temp = (TreeNode) stack.pop();
}
}

public static void main(String[] args) {
TreeNode node1 = new TreeNode(null, null, 1);
TreeNode node2 = new TreeNode(null, node1, 2);
TreeNode node3 = new TreeNode(null, null, 3);
TreeNode node4 = new TreeNode(node2, node3, 4);
TreeNode node5 = new TreeNode(null, null, 5);
TreeNode root = new TreeNode(node4, node5, 0);
System.out.println("Tree Height is " + getTreeHeight(root));
System.out.println("Recurse In Order Traverse");
recurseInOrder(root);
System.out.println("Stack In Order Traverse");
stackInOrder(root);
System.out.println("Recurse Pre Order Traverse");
recursePreOrder(root);
System.out.println("Stack Pre Order Traverse");
stackPreOrder(root);
}
}
可以做個參考

❻ 急求java實現二叉樹遍歷程序 多少分都行 啊

在JAVA中實現二叉樹，程序如下（轉載）

//********************************************************************
//filename: BinaryTreeTest.java
//purpose: test a binarytree with java
//date: 2002/12/18
//author: flyfan
//ver: 0.1
//********************************************************************

public class BinaryTreeTest
{
public static void main(String args[])
{
BinaryTreeTest b=new BinaryTreeTest();
int data[]={12,11,34,45,67,89,56,43,22,98};
BinaryTree root =new BinaryTree(data[0]);

System.out.print("二叉樹的中的數據： ");
for(int i=1;i{
root.insertTree(root,data[i]);
System.out.print(data[i-1]+";");
}

System.out.println(data[data.length-1]);

int key=Integer.parseInt(args[0]);

if(b.searchkey(root,key))
{
System.out.println("找到了:"+key);
}
else
{
System.out.println("沒有找到："+key);
}
}

public boolean searchkey(BinaryTree root, int key)
{
boolean bl=false;
if(root==null)
{
bl=false;
return bl;
}
else if(root.data==key)
{
bl=true;
return bl;
}
else if(key>=root.data)
{
return searchkey(root.rightpoiter,key);
}
return searchkey(root.leftpoiter,key);
}
}

class BinaryTree
{
int data;
BinaryTree leftpoiter;
BinaryTree rightpoiter;

BinaryTree(int data)
{
this.data=data;
leftpoiter=null;
rightpoiter=null;
}

public void insertTree(BinaryTree root, int data)
{
if(data>=root.data)
{
if(root.rightpoiter==null)
{
root.rightpoiter=new BinaryTree(data);
}
else
{
insertTree(root.rightpoiter,data);
}
}
else
{
if(root.leftpoiter==null)
{
root.leftpoiter=new BinaryTree(data);
}
else
{
insertTree(root.leftpoiter,data);
}
}
}
}
//end

❼ 怎樣用JAVA實現二叉樹的建立，遍歷和節點刪除

回答：smile2me
學妹
6月13日 13:32 //BinaryTree.h

/* 二叉樹的二叉鏈表結點定義 */
typedef char datatype;
typedef struct BiTNode
{
datatype data;
struct BiTNode * LChild , * RChild ;
} BiTNode , * BiTree ;

//數葉子結點的數目
/*
Author: WadeFelix RenV
*/
#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"
int countLeaf( BiTree BT )
{
if( BT == NULL ) return 0;
if( BT->LChild==NULL && BT->RChild==NULL ) return 1;
return(countLeaf(BT->LChild)+countLeaf(BT->RChild));
}

//數非葉子結點的數目

int countNotLeaf( BiTree BT )
{
if( BT == NULL ) return 0;
if( BT->LChild==NULL && BT->RChild==NULL ) return 0;
return(1+countNotLeaf(BT->LChild)+countNotLeaf(BT->RChild));
}

//判斷是否是排序二叉樹
#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"
int isPaiXu( BiTree BT )
{
if( BT == NULL )return 1;
if( BT->LChild && (BT->LChild->data > BT->data) )return 0;
if( BT->RChild && (BT->RChild->data < BT->data) )return 0;

return( isPaiXu(BT->LChild)&&isPaiXu(BT->RChild) );
}

❽ 用JAVA語言實現二叉樹的層次遍歷的非遞歸演算法及查找演算法。

先序非遞歸演算法
【思路】
假設：T是要遍歷樹的根指針，若T != NULL
對於非遞歸演算法，引入棧模擬遞歸工作棧，初始時棧為空。
問題：如何用棧來保存信息，使得在先序遍歷過左子樹後，能利用棧頂信息獲取T的右子樹的根指針？
方法1：訪問T->data後，將T入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為T，出棧，再先序遍歷T的右子樹。
方法2：訪問T->data後，將T->rchild入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為T->rchild，出棧，遍歷以該指針為根的子樹。
【演算法1】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{ // 基於方法一
InitStack(S);
while ( T!=NULL || !StackEmpty(S)){
while ( T != NULL ){
Visit(T->data) ;
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S,T);
T = T->rchild;
}
}
}
【演算法2】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{ // 基於方法二
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Visit(T->data);
Push(S, T->rchild);
T = T->lchild;
}
if ( !StackEmpty(S) ){
Pop(S,T);
}
}
}
進一步考慮：對於處理流程中的循環體的直到型、當型+直到型的實現。

中序非遞歸演算法
【思路】
T是要遍歷樹的根指針，中序遍歷要求在遍歷完左子樹後，訪問根，再遍歷右子樹。
問題：如何用棧來保存信息，使得在中序遍歷過左子樹後，能利用棧頂信息獲取T指針？
方法：先將T入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為T，出棧，訪問T->data，再中序遍歷T的右子樹。
【演算法】
void InOrder(BiTree T, Status ( *Visit ) (ElemType e))
{
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S, T);
Visit(T->data);
T = T->rchild;
}
}
}
進一步考慮：對於處理流程中的循環體的直到型、當型+直到型的實現。

後序非遞歸演算法
【思路】
T是要遍歷樹的根指針，後序遍歷要求在遍歷完左右子樹後，再訪問根。需要判斷根結點的左右子樹是否均遍歷過。
可採用標記法，結點入棧時，配一個標志tag一同入棧(0：遍歷左子樹前的現場保護，1：遍歷右子樹前的現場保護)。
首先將T和tag(為0)入棧，遍歷左子樹；返回後，修改棧頂tag為1，遍歷右子樹；最後訪問根結點。 [Page]
typedef struct stackElement{
Bitree data;
char tag;
}stackElemType;
【演算法】
void PostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T,0);
T = T->lchild;
}
while ( !StackEmpty(S) && GetTopTag(S)==1){
Pop(S, T);
Visit(T->data);
}
if ( !StackEmpty(S) ){
SetTopTag(S, 1); // 設置棧頂標記
T = GetTopPointer(S); // 取棧頂保存的指針
T = T->rchild;
}else break;
}
}

❾ 怎樣使用java對二叉樹進行層次遍歷

publicclassBinaryTree{

intdata;//根節點數據
BinaryTreeleft;//左子樹
BinaryTreeright;//右子樹

publicBinaryTree(intdata)//實例化二叉樹類
{
this.data=data;
left=null;
right=null;
}

publicvoidinsert(BinaryTreeroot,intdata){//向二叉樹中插入子節點
if(data>root.data)//二叉樹的左節點都比根節點小
{
if(root.right==null){
root.right=newBinaryTree(data);
}else{
this.insert(root.right,data);
}
}else{//二叉樹的右節點都比根節點大
if(root.left==null){
root.left=newBinaryTree(data);
}else{
this.insert(root.left,data);
}
}
}
}
當建立好二叉樹類後可以創建二叉樹實例，並實現二叉樹的先根遍歷，中根遍歷，後根遍歷，代碼如下：
packagepackage2;
publicclassBinaryTreePreorder{

publicstaticvoidpreOrder(BinaryTreeroot){//先根遍歷
if(root!=null){
System.out.print(root.data+"-");
preOrder(root.left);
preOrder(root.right);
}
}

publicstaticvoidinOrder(BinaryTreeroot){//中根遍歷

if(root!=null){
inOrder(root.left);
System.out.print(root.data+"--");
inOrder(root.right);
}
}

publicstaticvoidpostOrder(BinaryTreeroot){//後根遍歷

if(root!=null){
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data+"---");
}
}

publicstaticvoidmain(String[]str){
int[]array={12,76,35,22,16,48,90,46,9,40};
BinaryTreeroot=newBinaryTree(array[0]);//創建二叉樹
for(inti=1;i<array.length;i++){
root.insert(root,array[i]);//向二叉樹中插入數據
}
System.out.println("先根遍歷：");
preOrder(root);
System.out.println();
System.out.println("中根遍歷：");
inOrder(root);
System.out.println();
System.out.println("後根遍歷：");
postOrder(root);

❿ 二叉樹的java實現與幾種遍歷

二叉樹的定義

二叉樹(binary tree)是結點的有限集合，這個集合或者空，或者由一個根及兩個互不相交的稱為這個根的左子樹或右子樹構成.

從定義可以看出，二叉樹包括：1.空樹 2.只有一個根節點 3.只有左子樹 4.只有右子樹 5.左右子樹都存在 有且僅有這5種表現形式

二叉樹的遍歷分為三種：前序遍歷 中序遍歷 後序遍歷

• 前序遍歷：按照「根左右」,先遍歷根節點，再遍歷左子樹 ，再遍歷右子樹

• 中序遍歷：按照「左根右「,先遍歷左子樹，再遍歷根節點，最後遍歷右子樹

• 後續遍歷：按照「左右根」，先遍歷左子樹，再遍歷右子樹，最後遍歷根節點

其中前，後，中指的是每次遍歷時候的根節點被遍歷的順序

具體實現看下圖：