精华内容
下载资源
问答
  • 在一棵二叉树中,度为0的节点个数
    千次阅读
    2021-04-06 18:32:56

    首先我们要在结点类里加一个bool类型的函数用于判断该结点度是否为1👇

    	//判断结点度是否为1
    	bool isAlone() {
    		if (leftchild == NULL && rightchild != NULL) {
    			return true;
    		}
    		else if(leftchild != NULL && rightchild == NULL){
    			return true;
    		}
    		else {
    			return false;
    		}
    	}

    随后我们再到二叉树类里编写我们的算法

     

    递归算法和上一篇blog里的求二叉树深度(递归+非递归)非常类似👇

    //递归统计二叉树度为1的节点个数
    	int CaculateAlone1(BinaryTreeNode<T>* treeNode) {
    		int count = 0;
    		if (treeNode != NULL) {
    			if (treeNode->isAlone()) {
    				count++;
    			}
    			count += CaculateAlone1(treeNode->getLeft());
    			count += CaculateAlone1(treeNode->getRight());
    		}
    		return count;
    	}

    非递归也和求深度差不多,核心也是借助队列先进先出的特点进行操作👇

    //非递归统计二叉树度为1的节点个数
    	int CaculateAlone2(BinaryTreeNode<T>* treeNode) {
    		int count = 0;
    		if (treeNode != NULL) {
    			queue<BinaryTreeNode<T>*> q;
    			q.push(treeNode);
    			while (!q.empty()) {
    				for (int size = q.size(); size > 0; size--) {
    					BinaryTreeNode<T>* p = q.front();
    					q.pop();
    					if (p->isAlone()) {
    						count++;
    					}
    					if (p->getLeft()) {
    						q.push(p->getLeft());
    					}
    					if (p->getRight()) {
    						q.push(p->getRight());
    					}
    				}
    			}
    		}
    		return count;
    	}

    最后附上完整代码👇

    #include<iostream>
    #include<queue>
    using namespace std;
    
    //结点类
    template<class T>
    class BinaryTreeNode {
    	//友元类声明
    	template<class T>
    	friend class BinaryTree;
    private:
    	T data;
    	BinaryTreeNode<T>* leftchild;
    	BinaryTreeNode<T>* rightchild;
    public:
    	//构造函数
    	BinaryTreeNode() {
    		leftchild = NULL;
    		rightchild = NULL;
    	}
    	BinaryTreeNode(const T& dataValue) {
    		data = dataValue;
    		leftchild = NULL;
    		rightchild = NULL;
    	}
    	BinaryTreeNode(const T& dataValue, BinaryTreeNode<T>* leftchildValue, BinaryTreeNode<T>* rightchildValue) {
    		data = dataValue;
    		leftchild = leftchildValue;
    		rightchild = rightchildValue;
    	}
    	//析构函数
    	~BinaryTreeNode() {
    		leftchild = NULL;
    		rightchild = NULL;
    	}
    	//取左结点
    	BinaryTreeNode<T>* getLeft() {
    		return leftchild;
    	}
    	//取右结点
    	BinaryTreeNode<T>* getRight() {
    		return rightchild;
    	}
    	//判断结点度是否为1
    	bool isAlone() {
    		if (leftchild == NULL && rightchild != NULL) {
    			return true;
    		}
    		else if(leftchild != NULL && rightchild == NULL){
    			return true;
    		}
    		else {
    			return false;
    		}
    	}
    };
    
    //二叉树类
    template<class T>
    class BinaryTree {
    private:
    	BinaryTreeNode<T>* root;
    public:
    	//构造函数
    	BinaryTree() {
    		root = NULL;
    		cout << "Now start to construct the BinaryTree" << endl;
    		CreateNode(root);
    	}
    	//析构函数
    	~BinaryTree() {
    		root = NULL;
    	}
    	//前序构建二叉树
    	void CreateNode(BinaryTreeNode<T>* &treeNode) {
    		cout << "Please enter a value or '#' to stop:";
    		T dataValue;
    		cin >> dataValue;
    		treeNode = new BinaryTreeNode<T>(dataValue);
    		if (treeNode->data == '#') {
    			delete treeNode;
    			treeNode = NULL;
    		}
    		else {
    			CreateNode(treeNode->leftchild);
    			CreateNode(treeNode->rightchild);
    		}
    	}
    	//取根节点
    	BinaryTreeNode<T>* getRoot() {
    		return root;
    	}
    	//递归统计二叉树度为1的节点个数
    	int CaculateAlone1(BinaryTreeNode<T>* treeNode) {
    		int count = 0;
    		if (treeNode != NULL) {
    			if (treeNode->isAlone()) {
    				count++;
    			}
    			count += CaculateAlone1(treeNode->getLeft());
    			count += CaculateAlone1(treeNode->getRight());
    		}
    		return count;
    	}
    	//非递归统计二叉树度为1的节点个数
    	int CaculateAlone2(BinaryTreeNode<T>* treeNode) {
    		int count = 0;
    		if (treeNode != NULL) {
    			queue<BinaryTreeNode<T>*> q;
    			q.push(treeNode);
    			while (!q.empty()) {
    				for (int size = q.size(); size > 0; size--) {
    					BinaryTreeNode<T>* p = q.front();
    					q.pop();
    					if (p->isAlone()) {
    						count++;
    					}
    					if (p->getLeft()) {
    						q.push(p->getLeft());
    					}
    					if (p->getRight()) {
    						q.push(p->getRight());
    					}
    				}
    			}
    		}
    		return count;
    	}
    };
    int main() {
    	//前序构建二叉树
    	BinaryTree<char> test;
    	//统计二叉树度为1的节点个数
    	cout << endl << "递归求得度为1的节点个数:";
    	cout << test.CaculateAlone1(test.getRoot());
    	cout << endl << "非递归求得度为1的节点个数:";
    	cout << test.CaculateAlone2(test.getRoot());
    }

     

    更多相关内容
  • 在二叉树中查找度为2的节点个数返回,可供参考
  • 建立一棵二叉树,利用递归求二叉树节点个数 2.实现代码 class BinaryTreeNode(object): # 创建二叉树结点的函数 def __init__(self): self.data = '#' self.LChild = None self.RChild = None class BinaryTree...
  • // // queue_.cpp // LinkQueue // // Created by ljpc on 2018/5/30. ...// #include "queue_.h" ...void creatLinkQueue(LinkQueue*...// 创建一个循环队列指针que { que->front = (Node*)malloc(sizeof(Node)); que.
    //
    //  binary_tree.cpp
    //  BinaryTreeApp
    //
    //  Created by ljpc on 2018/5/3.
    //  Copyright © 2018年 ljpc. All rights reserved.
    //
    
    #include "binary_tree.h"
    
    int GetTreeDepth(BiTreeNode* root)
    // 计算该二叉树的深度
    // 参数:二叉树根节点root
    // 返回:二叉树的深度
    {
        // 请在这里补充代码,完成本关任务
        /********** Begin *********/
        int a,b;
        if(root==NULL)
        {
            return 0;
        }
        else 
        {
            a=GetTreeDepth(root->right);
            b=GetTreeDepth(root->left);
            if(a>b)
            {
                return a+1;
            }
            else
            {
                return b+1;
            }
        }
        /********** End **********/
    }
    
    int GetNodeNumber(BiTreeNode* root)
    // 计算该二叉树的总节点个数
    // 参数:二叉树根节点root
    // 返回:二叉树的总节点个数
    {
        // 请在这里补充代码,完成本关任务
        /********** Begin *********/
        if(root!=NULL)
        {
            return GetNodeNumber(root->left)+GetNodeNumber(root->right)+1;
        }
        else
        { 
            return 0;
        }
        /********** End **********/
    }
    
    int GetLeafNodeNumber(BiTreeNode* root)
    // 计算该二叉树的叶子节点个数
    // 参数:二叉树根节点root
    // 返回:二叉树的叶子节点个数
    {
        // 请在这里补充代码,完成本关任务
        /********** Begin *********/
        if(root==NULL)
        {
            return 0;
        }
        else if(root->left==NULL&&root->right==NULL)
        {
            return 1;
        }
        else
        {
            return GetLeafNodeNumber(root->left)+GetLeafNodeNumber(root->right); 
        }
        /********** End **********/
    }

    任务描述

    本关任务:给定一棵二叉树,计算该二叉树的深度、总节点个数和叶子节点个数。

    相关知识

    为了完成本关任务,你需要掌握:1.二叉树深度概念,2.二叉树节点,3.二叉树叶子节点概念。

    二叉树深度概念

    二叉树的深度指的是二叉树中最大的结点层数。例如:图1所示的二叉树最大的节点层数为3,所以该二叉树深度为3

    二叉树节点

    二叉树的节点包含一个数据元素及两个指向子树的分支,例如:图1所示的二叉树的总节点个数为6

    二叉树叶子节点概念

    叶子节点是度为0的节点,二叉树节点的度为子树的个数。例如:图1所示的二叉树叶子节点为CDF,个数为3

    编程要求

    本关的编程任务是补全右侧代码片段GetTreeDepthGetNodeNumberGetLeafNodeNumberBeginEnd中间的代码,具体要求如下:

    • GetTreeDepth中计算该二叉树的深度,返回深度值。
    • GetNodeNumber中计算该二叉树的总的节点个数,返回节点个数。
    • GetLeafNodeNumber中计算该二叉树的叶子节点个数,返回叶子节点个数。

    测试说明

    平台将自动编译补全后的代码,并生成若干组测试数据,接着根据程序的输出判断程序是否正确。

    以下是平台的测试样例:

    测试输入:ABC##D##EF###
    预期输出:
    3
    6
    3

    测试输入:ABCD###E#F##G##
    预期输出:
    4
    7
    3

     

    展开全文
  • 度为0节点个数:n0 度为1节点个数:n1 度为2的节点个数:n2 即:n0 + n1 + n2 = n 该二叉树包含的边总数:n-1 度为0节点的边的条0 度为1节点的边的条1 度为2的节点的边的条:2 即:n - 1 = n1 +...

    在这里插入图片描述
    二叉树:节点的度最大为2
    假设一个二叉树包含的节点总数为:n
    度为0的节点个数:n0
    度为1的节点个数:n1
    度为2的节点个数:n2
    即:n0 + n1 + n2 = n
    该二叉树包含的边总数为:n - 1
    度为0的节点的边的条数:0
    度为1的节点的边的条数:1
    度为2的节点的边的条数:2
    即:n - 1 = n1 + 2 n2
    n0 + n1 + n2 -1 = n1 + 2 n2
    得:n0 = n2 + 1

    展开全文
  • 主要介绍了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法,涉及C++二叉树的定义、遍历、统计相关操作技巧,需要的朋友可以参考下
  • 二叉树中度为1的结点个数

    千次阅读 2021-11-20 18:23:12
    若用二叉链表作为二叉树的存储表示,设计算法求二叉树中度为1的结点个数。 利用二叉树结构上的递归特性,用递归的方法实现。 分为4种情况: 若某结点有左子树和右子树,则以此结点根的二叉树中度为1的结点个数...

    若用二叉链表作为二叉树的存储表示,设计算法求二叉树中度为1的结点个数。

       利用二叉树结构上的递归特性,用递归的方法实现。

    分为4种情况:

    1. 若某结点有左子树和右子树,则以此结点为根的二叉树中度为1的结点个数

       =左子树的度为1的结点个数+右子树的度为1的结点个数。            

    1. 若该结点只有左子树,则以该结点为根的二叉树中度为1的结点个数= 1+左

       子树中度为1的结点个数。(+1是因为要算上以此结点为根的结点)。

    1. 若该结点只有右子树,则以该结点为根的二叉树中度为1的结点个数= 1+右   

       子树中度为1的结点个数。(+1是因为要算上以此结点为根的结点)。

    1. 若该结点没有子树,则以此结点为根的二叉树度为1的结点个数=0。

     该算法使用二叉链表来存储二叉树。

      算法设计了两个函数:

    1. 函数CreateBiTree()用来先序创建一颗二叉树;
    2. 函数Num()用来求二叉树中度为1的结点的个数;
    3. 主函数main()

     

    /********
    date:2021-11-20
    author:sy
    version:1.0
    Description:求二叉树中度为1的结点个数 
    *********/
    #include<stdio.h>
    #include<stdlib.h>
    typedef char datatype;
    /*定义二叉树的二叉链表结点的结构*/ 
    typedef struct  BiTNode
    {
    	datatype data;            //数据域 
    	struct BiTNode *lchild;   //左孩子指针 
    	struct BiTNode *rchild;   //右孩子指针 
    }BiTNode,*BiTree;
    /*先序创建二叉树*/
    void CreateBiTree(BiTree *T)
    {
    	char ch;
    	ch=getchar();
    	if(ch=='#')
    	{
    		(*T)=NULL; 
    	}
    	else
    	{
    		(*T)=(BiTree)malloc(sizeof(BiTNode)); //为二叉树申请结点 
    		(*T)->data=ch;                 //生成根结点 
    		CreateBiTree(&(*T)->lchild);   //构造左子树 
    		CreateBiTree(&(*T)->rchild);   //构造右子树 
    	 } 
     } 
     /*求二叉树中度为1的结点个数*/ 
    int Num(BiTree T)
    {
    	if(T==NULL)
    	{
    		return 0;
    	}
    	if(T->lchild != NULL && T->rchild != NULL)      /*某结点有左右子树*/ 
    	{
    		return Num(T->lchild) + Num(T->rchild);
    	}
    	else if(T->lchild != NULL && T->rchild == NULL)  /*某结点只有左子树*/
    	{
    		return 1 + Num(T->lchild);
    	}
    	else if(T->lchild == NULL && T->rchild != NULL)   /*某结点只有右子树*/
    	{
    		return 1 + Num(T->rchild);
     	} 
    	return 0;
    }
    int main()
    {
    	BiTree T=NULL;
    	printf("\n 创建一棵二叉树:\n");
    	CreateBiTree(&T); 
    	printf("\n 二叉树中度为1的结点个数为:%d\n",Num(T));
    }
    

    运行结果

     

    展开全文
  • 统计二叉树中度为01,2的节点个数

    万次阅读 多人点赞 2018-11-19 20:01:49
    int NumsDegree_0(BiTree T) { if(T) { if(T-&gt;left == NULL &amp;&amp; T-&gt;right == NULL) return 1; else return NumsDegree_0(T-&gt;left)+NumsDegree_0(T-&gt;right);...
  • 统计二叉树中度为0,1和2的结点个数

    千次阅读 2020-04-30 16:49:28
    Description 给定先序序列,按照该序列创建对应的二叉树,并输出该...行,三整数分别代表该二叉树度为0,1和2的结点个数 Sample Input ABD^^^CE^^F^^ Sample Output 3 1 2 #include<stdio.h> #include...
  • 二叉树节点数为N N=n0+n1+n2 N=n22+n11+n0*0+1 解得:n0=n2+1
  • 文章目录实验五 树的应用--二叉树的遍历、实验目的:1、了解二叉树的逻辑结构和物理结构;2、掌握二叉树数据类型定义;3、熟练掌握二叉树在链式存储结构上的遍历操作;二、实验要求:三、实验任务:四、代码如下五...
  • 数据结构 - 统计二叉树度为0/1/2的结点个数(递归) 文章目录数据结构 - 统计二叉树度为0/1/2的结点个数(递归)0. 变量/函数声明树的结构体函数声明1. 统计结点统计度为0的结点数统计度为1的结点数统计度2的结...
  • 掌握了二叉树的先序遍历递归算法、中序遍历递归算法和后序遍历递归算法的实现流程后,我们稍微开拓一下视野,来看一下该如何求出二叉树中度为0度为1度为2的结点的个数. 设计算法之前,我们要弄清什么是...
  • 二叉树每层度为1节点数

    千次阅读 2022-03-29 15:21:38
    编写程序统计一棵非空二叉树中每层度为1的结点的数目,二叉树结点个数不超过100。 输入格式: 输入为一个字符串,表示带空指针信息的二叉树先根序列。其中空指针信息用#表示,二叉树结点a-z, A-Z的字母。 输出格式:...
  • 计算二叉树结点度为0,1,2的结点个数

    千次阅读 2021-11-28 09:41:01
    【问题描述】首先利用二叉树的前序遍历建立一棵二叉树,分别用3递归函数统计度为0度为1度为2的结点个数,并输出结果,这3函数可以定义为二叉树的成员函数 【输入形式】假设二叉树的结点字符型,输入“#”...
  • 设:节点个数为n,叶子节点个数为n0n_0n0​,度为1节点个数为n1n_1n1​,度为2的节点个数为n2n_2n2​,边的个数b。 n = n0n_0n0​ + n1n_1n1​ + n2n_2n2​ b = n - 1 可得 b = n0n_0n0​ + n1n_1n1​ + n2n_...
  • 输入的第行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成, 下面是n-1行,每行有两整数,第一个数表示父节点的编号,第二个数表示子节点的编号 输出描述: 输出树的高度,为一个整数
  • 计算二叉树中度为2的结点个数

    千次阅读 2020-09-22 15:01:36
    int Node2(BiTree T) ... return 0; else if(T->lchild&&T->rchild) return Node2(T->lchild)+Node2(T->rchild)+1; else return Node2(T->lchild)+Node2(T->rchild); }
  • c代码-求二叉树的叶子节点和高度
  • 文章目录完全二叉树节点个数1.三种解法迭代法--层序遍历递归法--后序遍历递归法--完全二叉树性质2.总结 完全二叉树节点个数 leetcode链接 1.三种解法 迭代法–层序遍历 直接层序遍历遍历所有节点,然后统计个数...
  • 完全二叉树节点计算基本是几类,要么是求完全二叉树中的叶子节点个数或者度为1或者2的节点的个数。 其实这些问题根本上一一类问题,求解方法也是基本相同的。 先把题列出来: 一棵完全二叉树具有1000结点,...
  • 设总节点个数为n,叶子节点个数为n0度为1节点个数为n1,度为2的节点个数为n2,则必有 n0+n1+n2 = n …(①) (1) 对于二叉树有: n0 = n2+1…(②) (什么呢?下面证明一下) 【注】(1)这规律是所有...
  • 1-5 统计二叉树度为1的结点个数 (10 分)

    万次阅读 多人点赞 2018-12-12 16:59:44
    本题要求实现一个函数,可统计二叉树中度为1的结点个数。 函数接口定义: int NodeCount ( BiTree T); T是二叉树树根指针,函数NodeCount返回二叉树中度为1的结点个数,若树空,返回0。 裁判测试程序样例: ...
  • 参考资料 http://blog.csdn.net/u013227200/article/details/37992463
  • 设叶子节点个数为n0度为1节点个数为n1,度为2的节点个数为n2,必有 n0+n1+n2 = n (1) 对于二叉树有: n0 = n2+1 (2) 由上面两式 ==&gt; n0 = (n+1-n1)/2 ,n2 = (n-1-n1)/2 (3) 由完全二叉树的性质可知:...
  • 数据结构 统计二叉树中度为0,1和2的结点个数

    万次阅读 多人点赞 2018-04-08 22:13:05
    Description 给定先序序列,按照该序列创建对应的...行,三整数分别代表该二叉树度为0,1和2的结点个数 Sample Input ABD^^^CE^^F^^ Sample Output 3 1 2 递归遍历寻找 理解递归的思想 就很好理解程...
  • 二叉树求解节点个数、求二叉树中节点总数二、求二叉树中度为0节点个数三、求二叉树中度为1节点个数四、求二叉树中度为2的节点个数五、求二叉树第k层节点个数六、结果展示 以此树例: 、求二叉树中节点...
  • 一个二叉树有100个子节点数为2的节点,100个子节点数为1节点,那么个子节点数为0节点(叶节点)的个数: A. 101 B. 100 C. 200 D. 300 E. 99 F. 1  正确答案(A) 解法: 来源:牛客网:链接:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 84,107
精华内容 33,642
关键字:

在一棵二叉树中,度为0的节点个数