【1115】Counting Nodes in a BST (30分)【BST建树 DFS】

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;  
/*链表存储---递归建BST---DFS,传入的参数为结点和depth*/
/*若当前结点为NULL则更新maxdepth并return，数组sum存每层对应结点数*/
struct node{
	int data;
	struct node *left,*right;
};
void insert(node* &root,int data){
	if(root == NULL){//空树，说明查找失败，也即插入位置
		root=new node; //申请一个node结构体地址空间
		root->data=data;
		root->left=root->right=NULL;//初始无左右孩子
		return;
	}//一定要注意下面这个if是小于等于！！有等于情况
	if(data<=root->data) insert(root->left,data);//插在左子树
	else insert(root->right,data);//插在右子树
}
vector<int> num(1000);
int maxdepth=-1;

void dfs(node *root,int depth){
	if(root ==NULL){
		maxdepth=max(depth,maxdepth);
		return;
	}
	num[depth]++;//每访问一个结点就在这对应层的节点数加1
	dfs(root->left,depth+1);
	dfs(root->right,depth+1);
}

int main(){   
	int n,data;
	node* root=NULL;//定义头结点
	scanf("%d",&n);//结点个数
	for(int i=0;i<n;i++){
		scanf("%d",&data);
		insert(root,data);//将data插入树中
	}
	dfs(root,0);
	printf("%d + %d = %d",num[maxdepth-1] , num[maxdepth-2] , num[maxdepth-1]+num[maxdepth-2]);
	system("pause");
    return 0;   
}

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/103828632