欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

怎么计算一棵完全二叉树的节点个数

程序员文章站 2022-05-16 10:08:19
...

题目:已知一棵完全二叉树,求其节点的个数

要求:时间复杂度低于O(N),N为这棵树的节点个数

完全二叉树的概念就不多叙述了。

讲讲思路:题目的要求是时间复杂度低于O(N),所以遍历的方式就不用考虑了,根据完全二叉树的特点可以知道,从头节点head开始一直往左走可以可以到达完全二叉树的最底层,而就是可以计算出二叉树的高度H了,(默认给定的一定是完全二叉树,,,)

1)当头结点的右子节点作为头节点来计算他的高度h+1等于H的时候,说明head的左子树是一棵满二叉树,可以使用公式t = 2^level-1,也就是节点个数t等于2的层数次方-1。这个时候,发现右子树可以使用递归的方式计算,因为自问题与原问题是一致的。

2)当头结点的右子节点作为头节点来计算他的高度h+1不等于H的时候,说明head的右子树是一颗满二叉树。而左子树同(1),应该使用递归的方式解决。

下面看代码:

public class C08_CompleteTreeNodeNumber {
	public static class Node{
		public int value;
		public Node left;
		public Node right;
		public Node(int value){
			this.value = value;
		}
	}
	public static int nodeNum(Node head){
		if(head==null){
			return 0;
		}
		return process(1, head, totalHeigh(head, 1));
	}
	//当前节点的层数,当前节点,整颗二叉树的高度(这个是一直不变的)
	public static int process(int level,Node cur,int h){
		if(level==h){//到了最后一层
			return 1;
		}
		//如果右子树高度+1等于树的高度,递归计算右子树,而左子树是一个满二叉树,用公式计算
		if(totalHeigh(cur.right, level+1)==h){
			//位运算<<一定要括起来
			return (1<<(h-level)) + process(level+1, cur.right, h);
		}
		//如果右子树高度+1不等于树的高度,递归计算左子树,右子树是一颗满二叉树,用公式计算
		else {
			return (1<<(h-level-1)) + process(level+1, cur.left, h);
		}
	}
	public static int totalHeigh(Node cur,int level){
		while(cur!=null){
			level++;
			cur = cur.left;
		}
		return level-1;
	}
	public static void main(String[] args) {//test
		Node head = new Node(2);
		head.left = new Node(3);
		head.right = new Node(3);
		head.left.left = new Node(3);
		//head.left.right = new Node(3);
		//head.right.left = new Node(3);
		System.out.println(nodeNum(head));
	}
}

原文:https://blog.csdn.net/qq_38238041/article/details/79547490

相关标签: Java 二叉树