二叉树深度遍历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种表现形式

二叉树的遍历分为三种：前序遍历 中序遍历 后序遍历

• 前序遍历：按照“根左右”,先遍历根节点，再遍历左子树 ，再遍历右子树

• 中序遍历：按照“左根右“,先遍历左子树，再遍历根节点，最后遍历右子树

• 后续遍历：按照“左右根”，先遍历左子树，再遍历右子树，最后遍历根节点

其中前，后，中指的是每次遍历时候的根节点被遍历的顺序

具体实现看下图：