C语言求树中的叶子结点数

有从上至下和从下至上两种方式可以统计树的节点数。

设叶子节点（度为0的节点）数为x：

从上至下时，度为n的节点有n个子节点，再加上根节点，总结点数量为1+4×1+3×2+2×3+1×4+0×n=21

从下至上时，节点数为度为0~4的所有节点数相加，总节点数量为1+2+3+4+n=10+n

所以有21=10+n，得n=11

#include <iostream>

#include <algorithm>

using namespace std;

struct Node{

    int lson;

    int rson;

    int val;

}node[10000<<2];

int N1,N2;

void dfs(int n)

{

    N1++;

    if (node[n]lson==node[n]rson&&node[n]lson==0)

        {

            N2++;

            return;

        }

    if (node[n]lson)

        dfs(node[n]lson);

    if (node[n]rson)

        dfs(node[n]rson);

}

这是在你知道头结点的情况下的， 把头节点的值压入dfs函数中就可以得到N1 ，N2 的值（因为开的是全局  初值为0）

如果不知道头节点  数据是随机给出的   那么要使用并查集来找到头节点 ，简单的说

开一个father数组  （下面代码里用fa[] 表示 ） 因为二叉树的性质，每个节点最多有两个儿子，但每个节点除了头节点必定有且只有一个父亲    头节点的父亲就是自己

开始时每个节点的初值都是自己，每次添加一个节点，把两个子节点的父亲修改

下面是代码：

int fa[10000<<4];

void init()

{

    for (int i=0;i<(10000<<4);i++)

        fa [ i ] = i ;

}

int findfa(int n)

{

    if (fa[n]==n)

        return n;

    else

        return findfa(fa[n]);

}

int main()

{

    int n,l,r,v;

    while (cin>>n>>l>>r>>v)

    {

        node[n]lson=l;

        node[n]rson=r;

        node[n]val =n;

        fa[l]=n;

        fa[r]=n;

    }

    int head = findfa(1);

    //head即为根节点

}

        // 获得根节点

        Element root = documentgetRootElement();

        // 遍历所有movie节点

        for (Iterator<Element> itemMovie = rootelementIterator(); itemMovie

                hasNext();) {

            // 得到movie节点

            Element movie = itemMovienext();

            // 遍历遍历movie下的所有节点

            for (Iterator<Element> itemInfo = movieelementIterator(); itemMovie

                    hasNext();) {

                // 得到movie下的所有节点

                Element info = itemInfonext();

                // 如果当前节点为 biao

                if (infogetName()equals("biao")) {

                    // 遍历当前biao

                    for (Iterator<Element> biaoInfo = infoelementIterator(); itemMovie

                            hasNext();) {

                        // 得到item中文本值

                        Systemoutprintln(biaoInfonext()getText());

                    }

                }

            }

1、首先要定义两个类：结点类和二叉树类。

2、二叉树类的组成：建立树的函数、遍历函数、删除函数。求结点数函数。

3、采用递归的思想，遇到标识符表示该结点为空，否则开辟空间创建新结点，同时调用递归开辟左结点和右结点。

4、前序遍历函数。

5、删除函数的思路：如果当前结点不为空，采用递归访问左结点和右结点、回收当前结点的空间。

6、求结点数函数的思路：如果当前结点为空，返回0、如果当前结点的左右孩子都为空，放回1。

7、求树高函数的思路：如果当前结点为空，返回0、递归访问左孩子和右孩子、比较左右孩子的高度，返回 较大值+1。

前九层的结点就有2^9-1=511个

而第九层的结点数是2^(9-1)=256

所以，第十层的叶子结点数是699-511=188个

现在来算第九层的叶子结点个数：

由于第十层的叶子结点是从第九层延伸的，所以应该去掉第九层中还有子树的结点。

因为第十层有188个，所以应该去掉第九层中的188 / 2=94个

所以，第九层的叶子结点个数是256-94=162，加上第十层有188个，最后结果是350个。

扩展资料：

二叉树性质

1、 在非空二叉树中，第i层的结点总数不超过

 , i>=1；

2、深度为h的二叉树最多有

 个结点(h>=1)，最少有h个结点；

3、对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

4、具有n个结点的完全二叉树的深度为

 （注：[ ]表示向下取整）

5、有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则 如果I>1，则其父结点的编号为I/2；

如果2I<=N，则其左孩子（即左子树的根结点）的编号为2I；若2I>N，则无左孩子；

如果2I+1<=N，则其右孩子的结点编号为2I+1；若2I+1>N，则无右孩子。

6、给定N个节点，能构成h(N)种不同的二叉树。

h(N)为卡特兰数的第N项。h(n)=C(2n，n)/(n+1)。

7、设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i

参考资料来源：百度百科-二叉树

叶子节点：没有孩子节点的节点

也就是说，当我们明白了叶子节点的定义后，只需要遍历一遍二叉树，把符合这种条件（左孩子节点和右孩子节点都为NULL的节点）的节点统计出来就可以了。

于是，实际上这个问题也就转化成了如何遍历二叉树？很显然，遍历二叉树是可以有多种方式的，如：前序遍历（递归/非递归）、中序遍历（递归/非递归）、后序遍历（递归/非递归）、层次遍历等等。

下面我将给出使用递归前序遍历以及层次遍历两种思路实现的求解叶子节点的示例代码吧，仅供参考。其他几种实现方式思路类似，可自行尝试。示例代码如下：

package cnzifangskytreequestions;

import orgjunitTest;

import cnzifangskyqueueLinkQueue;

import cnzifangskytreeBinaryTreeNode;

/

  求二叉树中叶子节点的个数

  @author Administrator

 

 /

public class Question2 {

/

  通过递归前序遍历获取叶子节点个数

  @param root

  @return

 /

public int getNumberOfLeavesByPreOrder(BinaryTreeNode root){

if(root == null){

return 0;

}else{

if(rootgetLeft() == null && rootgetRight() == null){ //叶子节点

return 1;

}else{

return getNumberOfLeavesByPreOrder(rootgetLeft()) + getNumberOfLeavesByPreOrder(rootgetRight());

}

}

}

/

  使用层次遍历获取二叉树叶子节点个数

  

  @时间复杂度 O(n)

  @param root

 /

public int getNumberOfLeavesByQueue(BinaryTreeNode root){

int count = 0; //叶子节点总数

LinkQueue<BinaryTreeNode> queue = new LinkQueue<>();

if(root != null){

queueenQueue(root);

}

while (!queueisEmpty()) {

BinaryTreeNode temp = (BinaryTreeNode) queuedeQueue();

//叶子节点：左孩子节点和右孩子节点都为NULL的节点

if(tempgetLeft() == null && tempgetRight() == null){

count++;

}else{

if(tempgetLeft() != null){

queueenQueue(tempgetLeft());

}

if(tempgetRight() != null){

queueenQueue(tempgetRight());

}

}

}

return count;

}

/

  测试用例

 /

@Test

public void testMethods(){

/

  使用队列构造一个供测试使用的二叉树

      1

    2    3

  4  5  6  7

    8 9  

 /

LinkQueue<BinaryTreeNode> queue = new LinkQueue<BinaryTreeNode>();

BinaryTreeNode root = new BinaryTreeNode(1); //根节点

queueenQueue(root);

BinaryTreeNode temp = null;

for(int i=2;i<10;i=i+2){

BinaryTreeNode tmpNode1 = new BinaryTreeNode(i);

BinaryTreeNode tmpNode2 = new BinaryTreeNode(i+1);

temp = (BinaryTreeNode) queuedeQueue();

tempsetLeft(tmpNode1);

tempsetRight(tmpNode2);

if(i != 4)

queueenQueue(tmpNode1);

queueenQueue(tmpNode2);

}

Systemoutprintln("叶子节点个数是：" + getNumberOfLeavesByPreOrder(root));

Systemoutprintln("叶子节点个数是：" + getNumberOfLeavesByQueue(root));

}

}

测试代码输出如下：

叶子节点个数是：5

叶子节点个数是：5

附：

二叉树节点BinaryTreeNode的定义：

package cnzifangskytree;

public class BinaryTreeNode {

private int data; // 数据

private BinaryTreeNode left; //左孩子节点

private BinaryTreeNode right; //右孩子节点

public BinaryTreeNode(int data) {

thisdata = data;

}

public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right) {

thisdata = data;

thisleft = left;

thisright = right;

}

public int getData() {

return data;

}

public void setData(int data) {

thisdata = data;

}

public BinaryTreeNode getLeft() {

return left;

}

public void setLeft(BinaryTreeNode left) {

thisleft = left;

}

public BinaryTreeNode getRight() {

return right;

}

public void setRight(BinaryTreeNode right) {

thisright = right;

}

}

队列LinkQueue的定义：

package cnzifangskyqueue;

import cnzifangskylinkedlistSinglyNode;

/

  基于单链表实现的队列

  @author zifangsky

  @param <K>

 /

public class LinkQueue<K extends Object>{

private SinglyNode<> frontNode; //队首节点

private SinglyNode<> rearNode; //队尾节点

public LinkQueue() {

frontNode = null;

rearNode = null;

}

/

  返回队列是否为空

  @时间复杂度 O(1)

  @return

 /

public boolean isEmpty(){

return (frontNode == null);

}

/

  返回存储在队列的元素个数

  @时间复杂度 O(n)

  @return

 /

public int size(){

int length = 0;

SinglyNode<> currentNode = frontNode;

while (currentNode != null) {

length++;

currentNode = currentNodegetNext();

}

return length;

}

/

  入队：在链表表尾插入数据

  @时间复杂度 O(1)

  @param data

 /

public void enQueue(K data){

SinglyNode<K> newNode = new SinglyNode<K>(data);

if(rearNode != null){

rearNodesetNext(newNode);

}

rearNode = newNode;

if(frontNode == null){

frontNode = rearNode;

}

}

/

  出队：删除表头节点

  @时间复杂度 O(1)

  @return

 /

public Object deQueue(){

if(isEmpty()){

throw new RuntimeException("Queue Empty!");

}else{

Object result = frontNodegetData();

if(frontNode == rearNode){

frontNode = null;

rearNode = null;

}else{

frontNode = frontNodegetNext();

}

return result;

}

}

}

单链表节点SinglyNode的定义：

package cnzifangskylinkedlist;

/

  单链表的定义

  @author zifangsky

  @param <K>

 /

public class SinglyNode<K extends Object> {

private K data; // 数据

private SinglyNode<> next; // 该节点的下个节点

public SinglyNode(K data) {

thisdata = data;

}

public SinglyNode(K data, SinglyNode<> next) {

thisdata = data;

thisnext = next;

}

public K getData() {

return data;

}

public void setData(K data) {

thisdata = data;

}

public SinglyNode<> getNext() {

return next;

}

public void setNext(SinglyNode<> next) {

thisnext = next;

}

@Override

public String toString() {

return "SinglyNode [data=" + data + "]";

}

}

以上就是关于C语言求树中的叶子结点数全部的内容，包括:C语言求树中的叶子结点数、C++ 编写一算法，求出一棵二叉树中所有结点数和叶子结点数，假定分别用变参N1和N2统计所有结点数、java解析xml时如何获得一个节点下相同叶子节点的值，dom方式等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！