数据结构-树的节点个数

曾经终败给现在 2022-05-18 00:11 96阅读 0赞

***【题目来自灰灰考研】***

（**2018北理813，****2018华科887**）

求二叉树的结点个数，如果根节点为空，则返回 0。

typedef struct Bintreenode\{

int data；

struct Bintreenode \*right；

struct Bintreenode \*left；

\} \*Bintreenode

#include<iostream>
    #include<cstdlib>
    #include<cstring>
    using namespace std;
    
    int count = 0;
    
    typedef struct TNode{
    	char data;
    	struct TNode *rChild;
    	struct TNode *lChild;
    }TNode;
    
    void CreateTree(TNode *&bt)
    {
    	//124##57###38#9###
    	/*
    		递归创建二叉树 
    	*/
    	char data;
    	cin>>data;
    	bt = (TNode *)malloc(sizeof(TNode));
    	if(data == '#')
    		bt = NULL;
    	else
    	{
    		bt->data = data;
    		CreateTree(bt->lChild);
    		CreateTree(bt->rChild);
    	}
    }
    
    TNode *CreateTree1()
    {
    	/*
    		第二种递归创建二叉树的方式 
    	*/
    	//124##57###38#9###
    	TNode *root;
    	char data;
    	cin>>data;
    	if(data == '#')
    		return NULL;
    	else
    	{
    		root = (TNode *)malloc(sizeof(TNode));
    		root->data = data;
    		root->lChild = CreateTree1();
    		root->rChild = CreateTree1();
    	 } 
    
    	return root;
    }
    
    void GetNodeNumber(TNode *root)
    {
    	/*
    		递归遍历二叉树的时候进行计数 
    	*/ 
    	if(!root)
    		return;
    	if(root != NULL)
    	{
    		count++;
    		GetNodeNumber(root->lChild);
    		GetNodeNumber(root->rChild);
    	}
    }
    
    void preOrderRecursionVisit(TNode *bt)
    {
    	/*
    		先序遍历二叉树 
    	*/ 
    	if(bt == NULL)
    		return;
    	else
    	{
    		cout<<bt->data<<" ";
    		preOrderRecursionVisit(bt->lChild);
    		preOrderRecursionVisit(bt->rChild);
    	}
    }
    
    int main()
    {
    	TNode *root;
    	CreateTree(root); 
    	//root = CreateTree1();
    	preOrderRecursionVisit(root);
    	cout<<endl; 
    	
    	GetNodeNumber(root);
    	cout<<"The Result is: "<<count<<endl; 
    }

**拓展问题1**：（**2017 华科887**）

求二叉树所有具有两个子女的结点个数，如果根节点为空，则返回 0。

其二叉树结点结构定义为：

typedef struct Bintreenode\{

int data；

struct Bintreenode \*right；

struct Bintreenode \*left；

\} \*Bintreenode；

同样的递归遍历思想，只要修改一下计数策略即可

void NodesNumHasTwoChildren(TNode *bt)
    {
    	/*
    		先序遍历二叉树 ,节点有两个孩子时计数 
    	*/ 
    	if(bt == NULL)
    		return;
    	else
    	{
    		if(bt->lChild && bt->rChild)
    			count1++;
    		NodesNumHasTwoChildren(bt->lChild);
    		NodesNumHasTwoChildren(bt->rChild);
    	}
    }

--------------------

**作业**：（**青蛙题精选**）

求二叉树所有具有单个子女的结点个数，如果根节点为空，则返回 0。

其二叉树结点结构定义为：

typedef struct Bintreenode\{

int data；

struct Bintreenode \*right；

struct Bintreenode \*left；

\} \*Bintreenode；

void NodesNumHasOneChildren(TNode *bt)
    {
    	/*
    		先序遍历二叉树 ,节点有一个孩子时计数 
    	*/ 
    	if(bt == NULL)
    		return;
    	else
    	{
    		if((bt->lChild && !bt->rChild) || (!bt->lChild && bt->rChild))
    			count2++;
    		NodesNumHasOneChildren(bt->lChild);
    		NodesNumHasOneChildren(bt->rChild);
    	}
    }