叶子节点的特征是无左孩子也无右孩子，还要注意与树只有一个节点的情况区分。

一、程序计算

int leaf(bitree t)
{
  if(!t)       
   return 0;      //空树,无叶子 
  else if(!t->lch && !t->rch)
           return 1;
        else 
           return (leaf(t->lch) + leaf(t->rch));
}

二、手动计算公式

利用“树中所有结点的度数之和再加1等于结点数”



则叶子节点数，即 为：

再讲完全二叉树节点数计算之前，我们先来看什么是完全二叉树
完全二叉树就是，树的高度差最多为1，且最后一层的节点都是紧凑靠左排列的。


满二叉树就是一种特殊的完全二叉树**，每层都是满的，除叶子结点外，每一层都有两个子节点**：

我们现在来看如何计算完全二叉树的节点个数呢？
如果是一个普通的二叉树，显然只要向下遍历一遍就行，时间复杂度为 O(N)
int countNodes(TreeNode* root)
{
	if(root == nullptr) 
		return 0 ;
	return 1 + countNodes(root->left) + countNodes(root->right);
}

那么如果是一个满二叉树，节点总数与高度呈指数关系，时间复杂度为O(logN)
int countNodes(TreeNode* root)
{
	int h = 0;
	while(root != nullptr)
	{
		root = root->left;
		h++;
	}
	return pow(2,h) - 1;
}

完全二叉树，比普通二叉树普通，但是又没有满二叉树那么特殊所以它分情况看用哪一种算法。
int coutNodes(TreeNode *root)
{
	TreeNode* l = root;
	TreeNode* r = root;
	int hleft = 0;
	int hright = 0;
	while(l != nullptr)
	{
		l = l->left;
		hleft++;
	}
	while(r != nullptr)
	{
		r = r->right;
		hright++;
	}
	//如果左右子树的高度相同，则是一颗满二叉树
	if(hleft == hright)
		return pow(2,hleft) - 1;
	
	else //按照普通二叉树的逻辑进行计算
		return 1 + countNodes(root->left) + countNodes(root->right);
}

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录
前言
1.树的一些定义
2.二叉树的一些性质
二叉树的特点
两种特殊的二叉树
二叉树的性质
3.前序，中序，后序遍历


前言
1.树的一些定义
节点的度：一个节点含有的子树的个数称为该节点的度；

树的度：一棵树中，最大的节点的度称为树的度；

叶子节点或终端节点：度为0的节点称为叶节点；

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；

根结点：一棵树中，没有双亲结点的结点；

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度：树中节点的最大层次；
非终端节点或分支节点：度不为0的节点；

兄弟节点：具有相同父节点的节点互称为兄弟节点；

堂兄弟节点：双亲在同一层的节点互为堂兄弟；

节点的祖先：从根到该节点所经分支上的所有节点；

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。

森林：由m（m>=0）棵互不相交的树的集合称为森林
2.二叉树的一些性质
二叉树的特点

每个结点最多有两棵子树，即二叉树不存在度大于 2 的结点。
二叉树的子树有左右之分，其子树的次序不能颠倒，因此二叉树是有序树。

两种特殊的二叉树
满二叉树: 一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k-1 ，则它就是满二叉树。

完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树
二叉树的性质

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^{i-1}(i>0)个结点
若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大结点数是2^k-1(k>=0)
对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1
具有n个结点的完全二叉树的深度k为$log_2(n+1)$上取整
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对

于序号为i的结点有：

若i>0，双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点

若2i+1<n，左孩子序号：2i+1，否则无左孩子

若2i+2<n，右孩子序号：2i+2，否则无右孩子


class TreeNode {
    String val;
    TreeNode left;
    TreeNode right;

    public TreeNode(String val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "val='" + val ;
    }
}


public static TreeNode great(){
        TreeNode A = new TreeNode("A");
        TreeNode B = new TreeNode("B");
        TreeNode C = new TreeNode("C");
        TreeNode D = new TreeNode("D");
        TreeNode E = new TreeNode("E");
        TreeNode F = new TreeNode("F");

        A.left = B;
        A.right = C;
        B.left = D;
        C.left = E;
        E.right = F;

        return A;
    }

3.前序，中序，后序遍历

NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点—>根的左子树—>根的右子树。
LNR：中序遍历(Inorder Traversal)——根的左子树—>根节点—>根的右子树。
LRN：后序遍历(Postorder Traversal)——根的左子树—>根的右子树—>根节点

//    先序遍历
    public static void preOrderTraversal(TreeNode root){
        if(root == null){
            return ;
        }
        System.out.print(root.val);
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }
//    中序遍历
    public static void inOrderTraversal(TreeNode root){
        if(root == null){
            return;
        }
        inOrderTraversal(root.left);
        System.out.print(root.val);
        inOrderTraversal(root.right);
    }

//    后序遍历
    public static void postOrderTraversal(TreeNode root){
        if(root == null){
            return;
        }
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val);
    }


对上面所创造的二叉树三种遍历的结果如图：

众所周知，树在计算机领域是一种重要的非线性数据结构，直观的看，它还是数据元素按分支关系组织起来的结构呢，那下面小编跟大家带来聊聊一种名叫二叉树的数据结构，一起来看看二叉树层次又是如何计算的呢?
那么何为二叉树呢?是这样的，树是有很多种,
其中每个节点最多只能有两个子节点的叫二叉树，二叉树的子节点又分为左节点和右节点，如果呢，二叉树的所有叶子节点全部都在最后一层, 并且结点总数=2^n-1,
n为层数, 则我们称之为满二叉数，如果该二叉树的所有叶子节点(没有子节点的节点)都在最后一层或者倒数第二层, 而且最后一层的叶子节点在左边连续,
倒数第二层的叶子节点在右边连续, 我们就称之为完全二叉树。
计算二叉树层次示例如下：import java.util.LinkedList;
import java.util.List;
public class BinaryTreeDeep
{
public static void main(String[] args)
{
Tree tree1 = new Tree("1");
Tree tree2 = new Tree("2");
Tree tree3 = new Tree("3");
Tree tree4 = new Tree("4");
Tree tree5 = new Tree("5");
Tree tree7 = new Tree("7");
Tree tree8 = new Tree("8");
Tree tree9 = new Tree("9");
Tree tree10 = new Tree("10");
tree1.setLeft(tree2);
tree1.setRight(tree3);
tree2.setLeft(tree4);
tree3.setRight(tree5);
tree5.setLeft(tree7);
tree7.setLeft(tree8);
tree8.setRight(tree9);
tree4.setRight(tree10);
/*
1
2    3
4         5
10         7
8
9
*/
int deep = getDeep(tree1);
System.out.println("深度(递归)是" + deep);
int deep1 = getDeep1(tree1);
System.out.println("深度(非递归)是" + deep1);
System.out.println("层次遍历是：");
levelTraversal(tree1);
}
private static int getDeep(Tree root)
{
if (null == root)
{
return 0;
}
if (null == root.getLeft() && null == root.getRight())
{
return 1; //如果只有他自己就是1
}
int left = 0;
int right = 0;
if (null != root.getLeft())
{
left = getDeep(root.getLeft());
}
if (null != root.getRight())
{
right = getDeep(root.getRight());
}
int deep = Math.max(left, right) + 1;
return deep;
}
private static int getDeep1(Tree root)
{
if (null == root)
{
return 0;
}
List  nodes = new LinkedList  ();
((LinkedList  ) nodes)
.offer(root);
int current = 0;
int deep = 0;
int levelNodeSize = 0;
while (nodes.size() > 0)
{
levelNodeSize = nodes.size(); //当前层节点的个数
current = 0;
while (current 
{
Tree tmp = ((LinkedList  ) nodes)
.poll();
if (null != tmp.getLeft())
{
((LinkedList  ) nodes)
.offer(tmp.getLeft());
}
if (null != tmp.getRight())
{
((LinkedList  ) nodes)
.offer(tmp.getRight());
}
current++;
}
deep++;
}
return deep;
}
private static void levelTraversal(Tree root)
{
List  nodes = new LinkedList  ();
((LinkedList  ) nodes)
.offer(root);
while (!nodes.isEmpty())
{
Tree tmp = ((LinkedList  ) nodes)
.poll();
System.out.print(tmp.getRoot() + " ");
if (null != tmp.getLeft())
{
((LinkedList  ) nodes)
.offer(tmp.getLeft());
}
if (null != tmp.getRight())
{
((LinkedList  ) nodes)
.offer(tmp.getRight());
}
}
System.out.println("");
}
}
class Tree
{
private String root;
private Tree left;
private Tree right;
public Tree(String root)
{
this.root = root;
}
public String getRoot()
{
return root;
}
public void setRoot(String root)
{
this.root = root;
}
public Tree getLeft()
{
return left;
}
public void setLeft(Tree left)
{
this.left = left;
}
public Tree getRight()
{
return right;
}
public void setRight(Tree right)
{
this.right = right;
}
}
那么以上就是有关二叉树的所有内容了，如果还想了解更多java一些知识问答那么记得关注本站消息哦，更多精彩内容等你来了解。