#pragma once
typedef struct MYTREE {
	char data;
	struct MYTREE* lChild;
	struct MYTREE* rChild;
}MyTree;
class Tree
{
public:
	Tree();
	~Tree();
	void CreateTree();
	void TraverseTree(MyTree *root);
	void GetLeafNode(MyTree *root,int &num);
	int GetTreeDepth(MyTree *root);
	void GetTreeNode(MyTree *root, int &num);
};

#include "Tree.h"
#include <iostream>
#include<algorithm>//max,min
using namespace std;
Tree::Tree()
{
}
Tree::~Tree()
{
}
void Tree::CreateTree()
{
	MyTree t1 = {'A',nullptr,nullptr};
	MyTree t2 = { 'B',nullptr,nullptr };
	MyTree t3 = { 'C',nullptr,nullptr };
	MyTree t4 = { 'D',nullptr,nullptr };
	MyTree t5 = { 'E',nullptr,nullptr };
	MyTree t6 = { 'F',nullptr,nullptr };
	MyTree t7 = { 'G',nullptr,nullptr };
	MyTree t8 = { 'H',nullptr,nullptr };
	t1.lChild = &t2;
	t1.rChild = &t6;
	t2.rChild = &t3;
	t3.lChild = &t4;
	t3.rChild = &t5;
	t6.rChild = &t7;
	t7.lChild = &t8;
	TraverseTree(&t1);
	cout << endl;
	int leafNum = 0;
	GetLeafNode(&t1,leafNum);
	cout << "leaf num: " << leafNum << endl;
	int treeDepth = GetTreeDepth(&t1);
	cout << "depth:" << treeDepth << endl;
	int nodeNum = 0;
	GetTreeNode(&t1,nodeNum);
	cout << "node num; " << nodeNum << endl;
}
void Tree::TraverseTree(MyTree *root)
{
	if (root == nullptr)
	{
		return;
	}
	TraverseTree(root->lChild);
	cout << root->data;
	TraverseTree(root->rChild);
}
void Tree::GetLeafNode(MyTree *root,int &num)
{
	if (root == nullptr)
	{
		return ;
	}
	if (root->lChild == nullptr && root->rChild == nullptr)
	{
		num++;
	}
	GetLeafNode(root->lChild,num);
	GetLeafNode(root->rChild,num);
}
int Tree::GetTreeDepth(MyTree * root)
{
	int num = 0;
	if (root == nullptr)
	{
		return num;
	}
	int lNum = GetTreeDepth(root->lChild);
	int rNum = GetTreeDepth(root->rChild);
	return max(lNum,rNum)+1;
}
void Tree::GetTreeNode(MyTree * root, int & num)
{
	if (root == nullptr)
	{
		return;
	}
	++num;
	GetTreeNode(root->lChild,num);
	GetTreeNode(root->rChild,num);
}

#include <iostream>
#include "Tree.h"
using namespace std;
void test() {
	Tree t;
	t.CreateTree();
}
int main()
{
	test();
	return 0;
}