「java求二叉树高度」java求二叉树的深度
今天给各位分享java求二叉树高度的知识，其中也会对java求二叉树的深度进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
- 1、以二叉链表为存储结构,写出求二叉树高度和宽度的算法
- 2、用java怎么构造一个二叉树呢？
- 3、java构建二叉树算法
- 4、求Java实现二叉树！！！
- 5、求数据结构（JAVA版）实验树和二叉树题目答案
- 6、怎么计算二叉树高度？
以二叉链表为存储结构,写出求二叉树高度和宽度的算法
原题：
以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法。所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。
标准答案：
①求树的高度
思想：对非空二叉树，其深度等于左子树的最大深度加1。
Int
Depth(BinTree
*T)
{
int
dep1,dep2;
if(T==Null)
return(0);
else
{
dep1=Depth(T-lchild);
dep2=Depth(T-rchild);
if(dep1dep2)
return(dep1+1);
else
return(dep2+1);
}
②求树的宽度
思想：按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。
int
Width(BinTree
*T)
{
int
front=-1,rear=-1;/*
队列初始化*／
int
flag=0,count=0,p;
/*
p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值。*／if(T!=Null)
{
rear++;
q[rear]=T;
flag=1;
p=rear;
}
while(frontp)
{
front++;
T=q[front];
if(T-lchild!=Null)
{
rear++;
q[rear]=T-lchild;
count++;
}
if(T-rchild!=Null)
{
rear++;
q[rear]=T-rchild;
count++;
}
if(front==p)
/*
当前层已遍历完毕*/
{
if(flagcount)
flag=count;
count=0;
p=rear;
/*
p指向下一层最右边的结点*/
}
}
/*
endwhile*/
return(flag);
}
用java怎么构造一个二叉树呢？
java构造二叉树，可以通过链表来构造，如下代码：
public class BinTree {
public final static int MAX=40;
BinTree []elements = new BinTree[MAX];//层次遍历时保存各个节点
int front;//层次遍历时队首
int rear;//层次遍历时队尾
private Object data; //数据元数
private BinTree left,right; //指向左,右孩子结点的链
public BinTree()
{
}
public BinTree(Object data)
{ //构造有值结点
this.data = data;
left = right = null;
}
public BinTree(Object data,BinTree left,BinTree right)
{ //构造有值结点
this.data = data;
this.left = left;
this.right = right;
}
public String toString()
{
return data.toString();
}
//前序遍历二叉树
public static void preOrder(BinTree parent){
if(parent == null)
return;
System.out.print(parent.data+" ");
preOrder(parent.left);
preOrder(parent.right);
}
//中序遍历二叉树
public void inOrder(BinTree parent){
if(parent == null)
return;
inOrder(parent.left);
System.out.print(parent.data+" ");
inOrder(parent.right);
}
//后序遍历二叉树
public void postOrder(BinTree parent){
if(parent == null)
return;
postOrder(parent.left);
postOrder(parent.right);
System.out.print(parent.data+" ");
}
// 层次遍历二叉树
public void LayerOrder(BinTree parent)
{
elements[0]=parent;
front=0;rear=1;
while(frontrear)
{
try
{
if(elements[front].data!=null)
{
System.out.print(elements[front].data + " ");
if(elements[front].left!=null)
elements[rear++]=elements[front].left;
if(elements[front].right!=null)
elements[rear++]=elements[front].right;
front++;
}
}catch(Exception e){break;}
}
}
//返回树的叶节点个数
public int leaves()
{
if(this == null)
return 0;
if(left == nullright == null)
return 1;
return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());
}
//结果返回树的高度
public int height()
{
int heightOfTree;
if(this == null)
return -1;
int leftHeight = (left == null ? 0 : left.height());
int rightHeight = (right == null ? 0 : right.height());
heightOfTree = leftHeightrightHeight?rightHeight:leftHeight;
return 1 + heightOfTree;
}
//如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层
public int level(Object object)
{
int levelInTree;
if(this == null)
return -1;
if(object == data)
return 1;//规定根节点为第一层
int leftLevel = (left == null?-1:left.level(object));
int rightLevel = (right == null?-1:right.level(object));
if(leftLevel0rightLevel0)
return -1;
levelInTree = leftLevelrightLevel?rightLevel:leftLevel;
return 1+levelInTree;
}
//将树中的每个节点的孩子对换位置
public void reflect()
{
if(this == null)
return;
if(left != null)
left.reflect();
if(right != null)
right.reflect();
BinTree temp = left;
left = right;
right = temp;
}
// 将树中的所有节点移走,并输出移走的节点
public void defoliate()
{
if(this == null)
return;
//若本节点是叶节点，则将其移走
if(left==nullright == null)
{
System.out.print(this + " ");
data = null;
return;
}
//移走左子树若其存在
if(left!=null){
left.defoliate();
left = null;
}
//移走本节点，放在中间表示中跟移走...
String innerNode += this + " ";
data = null;
//移走右子树若其存在
if(right!=null){
right.defoliate();
right = null;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BinTree e = new BinTree("E");
BinTree g = new BinTree("G");
BinTree h = new BinTree("H");
BinTree i = new BinTree("I");
BinTree d = new BinTree("D",null,g);
BinTree f = new BinTree("F",h,i);
BinTree b = new BinTree("B",d,e);
BinTree c = new BinTree("C",f,null);
BinTree tree = new BinTree("A",b,c);
System.out.println("前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍历二叉树结果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("后序遍历二叉树结果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的层次: "+tree.level("F"));
System.out.println("这棵二叉树的高度: "+tree.height());
System.out.println("--------------------------------------");
tree.reflect();
System.out.println("交换每个节点的孩子节点后......");
System.out.println("前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍历二叉树结果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("后序遍历二叉树结果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的层次: "+tree.level("F"));
System.out.println("这棵二叉树的高度: "+tree.height());
}
java构建二叉树算法
//******************************************************************************************************//
//*****本程序包括简单的二叉树类的实现和前序,中序,后序,层次遍历二叉树算法,*******//
//******以及确定二叉树的高度,制定对象在树中的所处层次以及将树中的左右***********//
//******孩子节点对换位置,返回叶子节点个数删除叶子节点,并输出所删除的叶子节点**//
//*******************************CopyRight By phoenix*******************************************//
//************************************Jan 12,2008*************************************************//
//****************************************************************************************************//
public class BinTree {
public final static int MAX=40;
private Object data; //数据元数
private BinTree left,right; //指向左,右孩子结点的链
BinTree []elements = new BinTree[MAX];//层次遍历时保存各个节点
int front;//层次遍历时队首
int rear;//层次遍历时队尾
public BinTree()
{
}
public BinTree(Object data)
{ //构造有值结点
this.data = data;
left = right = null;
}
public BinTree(Object data,BinTree left,BinTree right)
{ //构造有值结点
this.data = data;
this.left = left;
this.right = right;
}
public String toString()
{
return data.toString();
}//前序遍历二叉树
public static void preOrder(BinTree parent){
if(parent == null)
return;
System.out.print(parent.data+" ");
preOrder(parent.left);
preOrder(parent.right);
}//中序遍历二叉树
public void inOrder(BinTree parent){
if(parent == null)
return;
inOrder(parent.left);
System.out.print(parent.data+" ");
inOrder(parent.right);
}//后序遍历二叉树
public void postOrder(BinTree parent){
if(parent == null)
return;
postOrder(parent.left);
postOrder(parent.right);
System.out.print(parent.data+" ");
}// 层次遍历二叉树
public void LayerOrder(BinTree parent)
{
elements[0]=parent;
front=0;rear=1;
while(frontrear)
{
try
{
if(elements[front].data!=null)
{
System.out.print(elements[front].data + " ");
if(elements[front].left!=null)
elements[rear++]=elements[front].left;
if(elements[front].right!=null)
elements[rear++]=elements[front].right;
front++;
}
}catch(Exception e){break;}
}
}//返回树的叶节点个数
public int leaves()
{
if(this == null)
return 0;
if(left == nullright == null)
return 1;
return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());
}//结果返回树的高度
public int height()
{
int heightOfTree;
if(this == null)
return -1;
int leftHeight = (left == null ? 0 : left.height());
int rightHeight = (right == null ? 0 : right.height());
heightOfTree = leftHeightrightHeight?rightHeight:leftHeight;
return 1 + heightOfTree;
}
//如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层
public int level(Object object)
{
int levelInTree;
if(this == null)
return -1;
if(object == data)
return 1;//规定根节点为第一层
int leftLevel = (left == null?-1:left.level(object));
int rightLevel = (right == null?-1:right.level(object));
if(leftLevel0rightLevel0)
return -1;
levelInTree = leftLevelrightLevel?rightLevel:leftLevel;
return 1+levelInTree;
}
//将树中的每个节点的孩子对换位置
public void reflect()
{
if(this == null)
return;
if(left != null)
left.reflect();
if(right != null)
right.reflect();
BinTree temp = left;
left = right;
right = temp;
}// 将树中的所有节点移走,并输出移走的节点
public void defoliate()
{
String innerNode = "";
if(this == null)
return;
//若本节点是叶节点，则将其移走
if(left==nullright == null)
{
System.out.print(this + " ");
data = null;
return;
}
//移走左子树若其存在
if(left!=null){
left.defoliate();
left = null;
}
//移走本节点，放在中间表示中跟移走...
innerNode += this + " ";
data = null;
//移走右子树若其存在
if(right!=null){
right.defoliate();
right = null;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BinTree e = new BinTree("E");
BinTree g = new BinTree("G");
BinTree h = new BinTree("H");
BinTree i = new BinTree("I");
BinTree d = new BinTree("D",null,g);
BinTree f = new BinTree("F",h,i);
BinTree b = new BinTree("B",d,e);
BinTree c = new BinTree("C",f,null);
BinTree tree = new BinTree("A",b,c);
System.out.println("前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍历二叉树结果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("后序遍历二叉树结果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的层次: "+tree.level("F"));
System.out.println("这棵二叉树的高度: "+tree.height());
System.out.println("--------------------------------------");
tree.reflect();
System.out.println("交换每个节点的孩子节点后......");
System.out.println("前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍历二叉树结果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("后序遍历二叉树结果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的层次: "+tree.level("F"));
System.out.println("这棵二叉树的高度: "+tree.height());
}
求Java实现二叉树！！！
blic class TreeNode1 { //二叉树的结点类
public String data; //数据元数
public TreeNode1 left,right; //指向左,右孩子结点的链
public TreeNode1(){
this("?");
}
public TreeNode1(String d){ //构造有值结点
data = d;
left = right = null;
}
public void preorder(TreeNode1 p){ //先根次序遍历二叉树
if(p!=null){
System.out.print(p.data+" ");
preorder(p.left);
preorder(p.right);
}
}
public void inorder(TreeNode1 p){ //中根次序遍历二叉树
if(p!=null){
inorder(p.left);
System.out.print(p.data+" ");
inorder(p.right);
}
}
public void postorder(TreeNode1 p){ //后根次序遍历二叉树
if(p!=null){
postorder(p.left);
postorder(p.right);
System.out.print(p.data+" ");
}
}
}
求数据结构（JAVA版）实验树和二叉树题目答案
/**
* @param args
之前在大学的时候写的一个二叉树算法，运行应该没有问题，就看适不适合你的项目了 */
public static void main(String[] args) {
BiTree e = new BiTree(5);
BiTree g = new BiTree(7);
BiTree h = new BiTree(8);
BiTree l = new BiTree(12);
BiTree m = new BiTree(13);
BiTree n = new BiTree(14);
BiTree k = new BiTree(11, n, null);
BiTree j = new BiTree(10, l, m);
BiTree i = new BiTree(9, j, k);
BiTree d = new BiTree(4, null, g);
BiTree f = new BiTree(6, h, i);
BiTree b = new BiTree(2, d, e);
BiTree c = new BiTree(3, f, null);
BiTree tree = new BiTree(1, b, c);
System.out.println("递归前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("非递归前序遍历二叉树结果: ");
tree.iterativePreOrder(tree);
System.out.println();
System.out.println("递归中序遍历二叉树的结果为:");
tree.inOrder(tree);
System.out.println();
System.out.println("非递归中序遍历二叉树的结果为:");
tree.iterativeInOrder(tree);
System.out.println();
System.out.println("递归后序遍历二叉树的结果为:");
tree.postOrder(tree);
System.out.println();
System.out.println("非递归后序遍历二叉树的结果为:");
tree.iterativePostOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("递归求二叉树中所有结点的和为:"+getSumByRecursion(tree));
System.out.println("非递归求二叉树中所有结点的和为:"+getSumByNoRecursion(tree));
System.out.println("二叉树中,每个节点所在的层数为:");
for (int p = 1; p = 14; p++)
System.out.println(p + "所在的层为:" + tree.level(p));
System.out.println("二叉树的高度为:" + height(tree));
System.out.println("二叉树中节点总数为:" + nodes(tree));
System.out.println("二叉树中叶子节点总数为:" + leaf(tree));
System.out.println("二叉树中父节点总数为:" + fatherNodes(tree));
System.out.println("二叉树中只拥有一个孩子的父节点数:" + oneChildFather(tree));
System.out.println("二叉树中只拥有左孩子的父节点总数:" + leftChildFather(tree));
System.out.println("二叉树中只拥有右孩子的父节点总数:" + rightChildFather(tree));
System.out.println("二叉树中同时拥有两个孩子的父节点个数为:" + doubleChildFather(tree));
System.out.println("--------------------------------------");
tree.exChange();
System.out.println("交换每个节点的左右孩子节点后......");
System.out.println("递归前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("非递归前序遍历二叉树结果: ");
tree.iterativePreOrder(tree);
System.out.println();
System.out.println("递归中序遍历二叉树的结果为:");
tree.inOrder(tree);
System.out.println();
System.out.println("非递归中序遍历二叉树的结果为:");
tree.iterativeInOrder(tree);
System.out.println();
System.out.println("递归后序遍历二叉树的结果为:");
tree.postOrder(tree);
System.out.println();
System.out.println("非递归后序遍历二叉树的结果为:");
tree.iterativePostOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("递归求二叉树中所有结点的和为:"+getSumByRecursion(tree));
System.out.println("非递归求二叉树中所有结点的和为:"+getSumByNoRecursion(tree));
System.out.println("二叉树中,每个节点所在的层数为:");
for (int p = 1; p = 14; p++)
System.out.println(p + "所在的层为:" + tree.level(p));
System.out.println("二叉树的高度为:" + height(tree));
System.out.println("二叉树中节点总数为:" + nodes(tree));
System.out.println("二叉树中叶子节点总数为:" + leaf(tree));
System.out.println("二叉树中父节点总数为:" + fatherNodes(tree));
System.out.println("二叉树中只拥有一个孩子的父节点数:" + oneChildFather(tree));
System.out.println("二叉树中只拥有左孩子的父节点总数:" + leftChildFather(tree));
System.out.println("二叉树中只拥有右孩子的父节点总数:" + rightChildFather(tree));
System.out.println("二叉树中同时拥有两个孩子的父节点个数为:" + doubleChildFather(tree));
}
}
怎么计算二叉树高度？
分析二叉树的深度（高度）和它的左、右子树深度之间的关系。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。
int Depth (BiTree T ){ // 返回二叉树的深度
if ( !T ) depthval = 0;
else {
depthLeft = Depth( T-lchild );
depthRight= Depth( T-rchild );
depthval = 1 + (depthLeft depthRight ?
depthLeft : depthRight);
}
return depthval;
}
扩展资料：
一棵深度为k，且有2^k-1个结点的二叉树，称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树。具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子结点，至多有2k-1个结点。
二叉树的深度是从根节点开始（其深度为1）自顶向下逐层累加的；而二叉树高度是从叶节点开始（其高度为1）自底向上逐层累加的。虽然树的深度和高度一样，但是具体到树的某个节点，其深度和高度是不一样的。
参考资料来源：百度百科—二叉树
java求二叉树高度的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于java求二叉树的深度、java求二叉树高度的信息别忘了在本站进行查找喔。
发布于：2022-11-27，除非注明，否则均为原创文章，转载请注明出处。