小算法:求一棵二叉树的高度以及求一个节点的左右子树的高度

  • 时间:
  • 来源:互联网
  • 文章标签:

求一棵二叉树的高度以及求一个节点的左右子树的高度

前言:
最近在学习平衡二叉排序树时,在计算二树的高度时笔者学到了一种相当精妙的算法,在此分享一下。

问题:
在这里插入图片描述
根据如上图构建一棵二叉树,并求出它的高度。以及写两个方法,传一个节点,可以分别求出它左右子树的高度。

求树的高度
我们只需在树的节点类中写如下方法:
返回的是以当前节点为根节点的树的高度

public int height() {
		return Math.max(left==null?0:left.height(),right==null?0:right.height())+1;
	}

求树的左子树的高度
以当前节点为根节点的左子树的高度

//返回左子树的高度
	public int leftHeight() {
		if(left==null) {
			return 0;
		}
		return left.height();
	}

求树的右子树的高度
以当前节点为根节点的右子树的高度

//返回左子树的右高度
	public int rightHeight() {
		if(right==null) {
			return 0;
		}
		return right.height();
	}

写出这三种方法后,我们创建这棵树,并将方法放入代码

package Day05;

public class TreeHeight {
	public static void main(String[] args) {
		BinaryTree binaryTree=new BinaryTree();
		Node n4=new Node(4);
		Node n3=new Node(3);
		Node n6=new Node(6);
		Node n5=new Node(5);
		Node n7=new Node(7);
		Node n8=new Node(8);
		binaryTree.setRoot(n4);
		n4.setLeft(n3);
		n4.setRight(n6);
		n6.setLeft(n5);
		n6.setRight(n7);
		n7.setRight(n8);
		
		System.out.println("树的总高度:"+binaryTree.height());
		System.out.println("节点4的左子树高度:"+n4.leftHeight());
		System.out.println("节点4的右子树高度:"+n4.rightHeight());
	}
}
class BinaryTree{
	Node root;
	public void setRoot(Node root) {
		this.root=root;
	}
	
	public int height() {
		if(root==null) {
			return 0;
		}else {
			return root.height();
		}
	}
}
class Node{
	int value;
	Node left;
	Node right;
	public Node getLeft() {
		return left;
	}
	public void setLeft(Node left) {
		this.left = left;
	}
	public Node getRight() {
		return right;
	}
	public void setRight(Node right) {
		this.right = right;
	}
	public Node(int value) {
		this.value = value;
	}
	
	public int height() {
		return Math.max(left==null?0:left.height(),right==null?0:right.height())+1;
	}
	//返回左子树的高度
	public int leftHeight() {
		if(left==null) {
			return 0;
		}
		return left.height();
	}
		//返回左子树的右高度
	public int rightHeight() {
		if(right==null) {
			return 0;
		}
		return right.height();
	}
}

运行结果:
在这里插入图片描述

本文链接http://www.taodudu.cc/news/show-1781825.html