Binary tree

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
#include <iostream>
#include <stack>
#include <queue>

using namespace std;

#define END '#'

typedef char T;

typedef struct BtNode {
    
	struct BtNode* leftchild;
	struct BtNode* rightchild;
	T data;
}BtNode,*BTree;

struct BtNode * BuyNode()
{
    
	struct BtNode *s = (struct BtNode*)malloc(sizeof(*s));
	if (NULL == s) exit(0);
	memset(s, 0, sizeof(*s));
	return s;
}

bool Is_BSTree(BTree root, int min, int max)// Judge BST Trees 
{
    
	if (root == NULL)
		return true;
	if (root->data <= min&&root->data >= max)
		return false;
	return Is_BSTree(root->leftchild, min, root->data) &&
		Is_BSTree(root->rightchild, root->data, max);
}

bool Is_Full_BinaryTree(BTree root)// Judging the full binary tree 
{
    
	if (root == NULL)
		return false;
	queue<BTree> q;
	q.push(root);
	int num = 1;
	while (!q.empty())
	{
    
		int i = 0;
		for (; i < num&&!q.empty(); i++)
		{
    
			while (!q.empty())
			{
    
				root = q.front();
				q.pop();
				
				if (root->leftchild != NULL)
					q.push(root->leftchild);
				
				if (root->rightchild != NULL)
					q.push(root->rightchild);
			}	
		}

		if (i < num)
			return false;
		else num *= 2;
	}
	return true;
}

bool Is_Complete_BinaryTree(BTree root)// Judging a complete binary tree 
{
    
	if (root == NULL)
		return true;
	queue<BTree> q;
	q.push(root);

	while (!root)
	{
    	
		if (!q.front())
		{
    
			q.push(root->leftchild);
			q.push(root->rightchild);
		}
		q.pop();
	}
	while (!q.empty())
	{
    
		if (q.front() == NULL)
			return false;
		q.pop();
	}
	return true;
}

int Deep(BtNode* root)// depth 
{
    
	if (!root)
		return 0;
	return 1 + max(Deep(root->leftchild), Deep(root->rightchild));
}

int NodeSum(BTree root, int& A)// Number of nodes 
{
    
	if (root != NULL)
	{
    
		NodeSum(root->leftchild,A);
		A++;
		NodeSum(root->rightchild,A);
	}
	return A;
}

BTree Common_Ancestor(BTree root, BTree p, BTree q)// Specify the common ancestor of the node 
{
    
	if (root == NULL)
		return NULL;
	if (p == NULL || q == NULL)
		return root;
	BTree left = Common_Ancestor(root->leftchild, p, q);
	BTree right = Common_Ancestor(root->rightchild, p, q);

	if (left == NULL)
		return right;
	if (right == NULL)
		return left;
	if (left && right)
		return root;

	return NULL;
}

BTree FindParent(BTree root, BTree child)// Given a binary tree , Find the parent node of the pointing node 
{
    
	if (root == NULL || child == NULL || root == child)
		return NULL;
	if (root->leftchild == child || root->rightchild == child)
		return root;
	else {
    
		BTree p = FindParent(root->leftchild, child);
		if (p == NULL)
			p = FindParent(root->rightchild, child);
		return p;
	}

}

BTree FindNumArr(BTree root, T a)// Query array in binary tree , Return address exists , There is no return NULL
{
    
	stack<BTree> s;
	BTree p = root;
	while (p || !s.empty())
	{
    
		if (p)
		{
    
			s.push(p);
			p = p->leftchild;
		}
		else
		{
    
			p = s.top();
			if (p->data == a)
				return p;
			s.pop();
			p = p->rightchild;
		}
	}
	return NULL;
}

void GetKNode(BTree root, int k)// For the first K The node of the layer 
{
    
	if (root == NULL || k < 0)
		return;
	if (k == 0)
		cout << root->data << " ";
	GetKNode(root->leftchild, k - 1);
	GetKNode(root->rightchild, k - 1);
}

void Level(BTree root)// Level traversal 
{
    
	if (root == NULL)
		return;
	queue<BTree> q;
	q.push(root);
	while (!q.empty())
	{
    
		BTree Node = q.front();
		cout << Node->data << " ";
		q.pop();
		if (Node->leftchild != NULL)
			q.push(Node->leftchild);
		if (Node->rightchild != NULL)
			q.push(Node->rightchild);
	}
}

void InOrder(BTree p)// In the sequence traversal （ recursive ）
{
    
	if (p != NULL)
	{
    
		InOrder(p->leftchild);
		cout << p->data << " ";
		InOrder(p->rightchild);
	}

}

void FroOrder(BTree p)// The former sequence traversal （ recursive ）
{
    
	if (p != NULL)
	{
    
		cout << p->data << " ";
		FroOrder(p->leftchild);
		FroOrder(p->rightchild);
	}

}

void PostOrder(BTree p)// After the sequence traversal （ recursive ）
{
    
	if (p != NULL)
	{
    
		PostOrder(p->leftchild);
		PostOrder(p->rightchild);
		cout << p->data << " ";

	}

}

void FroOrder2(BTree root)// The first sequence traversal （ Non recursive ）
{
    
	stack<BTree> s;
	BTree p = root;
	while (p != NULL || !s.empty())
	{
    
		if(p != NULL)
		{
    		
			cout << p->data << " ";
			s.push(p);
			p = p->leftchild;
		}
		else
		{
    
			p = s.top();
			//cout << p->data << " ";
			s.pop();
			p = p->rightchild;
		}
	}
}

void InOrder2(BTree root)// In the sequence traversal （ Non recursive ）
{
    
	stack<BTree> s;
	BTree p = root;
	while (p || !s.empty())
	{
    
		if (p)
		{
    
			s.push(p);
			p = p->leftchild;
		}
		else
		{
    
			p = s.top();
			cout << p->data << " ";
			s.pop();
			p = p->rightchild;
		}
	}
}

void PostOrder2(BTree root)// After the sequence traversal （ Non recursive ）
{
    
	stack<BTree> s;
	BTree p ;	
	BTree tmp = NULL;
	s.push(root);
	while (!s.empty())
	{
    
		p = s.top();
		if ((p->leftchild == NULL && p->rightchild == NULL) ||
			(tmp == NULL && (tmp->leftchild == NULL || tmp->rightchild == NULL)))
		{
    
			cout << p->data << " ";
			s.pop();
			tmp = p;
		}
		else {
    
			if (p->rightchild)
				s.push(p->rightchild);
			if (p->leftchild)
				s.push(p->leftchild);
		}
	}
}

BtNode* Creatree1()// Establish a binary tree in the order of precedence 
{
    
	char tmp;
	BtNode* s = NULL;
	cin >> tmp;
	if (tmp != END)
	{
    
		s = BuyNode();
		s->data = tmp;
		s->leftchild = Creatree1();
		s->rightchild = Creatree1();
	}
	return s;
}

BtNode* Creatree2(char *ar)
{
    
	BTree s = NULL;
	if (*ar != END)
	{
    
		s = BuyNode();
		s->data = *ar;
		s->leftchild = Creatree2(++ar);
		s->rightchild = Creatree2(++ar);
	}
	return s;
}

BtNode* CreatrPI(T* pstr,T* istr,int size)// The first and middle order traversal builds a binary tree 
{
    
	if (pstr == NULL || istr == NULL)
		return NULL;

	BtNode* root = new BtNode;
	int index = 0;
	root->data = pstr[index];
	for (; index < size; index++)
	{
    
		if (istr[index] == root->data)
			break;
	}
	root->leftchild = CreatrPI(pstr + 1, istr, index);
	root->rightchild = CreatrPI(pstr + index+1, istr+index+1, size - index - 1);

	return root;
}

BtNode* CreatrLI(T*lstr,T*istr,int size)// After traversing the middle order, restore the binary tree 
{
    
	if (lstr == NULL || istr == NULL)
		return NULL;

	int index = size - 1;
	BtNode* root = new BtNode;
	root->data = lstr[index];

	for (; index>0; index--)
	{
    
		if (istr[index] == root->data)
			break;
	}

	root->leftchild = CreatrLI(lstr, istr, index);
	root->rightchild = CreatrLI(lstr + index, istr + index + 1, size - index);

	return root;
}


int main()
{
    
	//char *pstr = "ABCDEFGH";
	//char *istr = "CBEDFAGH";
	//char *lstr = "CEFDBHGA";
	BTree root = NULL;
	root = Creatree1();
	int a = 0;
	//printf("%x\n", (unsigned int)root);
	//(unsigned int)FindNumArr(root, 'D')
	//printf("%x\n",(unsigned int)FindNumArr(root, 'B'));
	
	printf("%d\n", Deep(root));
	
	//root = Creatree2("ABC##DE##F##G#H##");
	//GetKNode(root,1);
	//int len = sizeof(pstr) / sizeof(pstr[0]);
	//root = CreatrLI(pstr, istr, len);
	//PostOrder2(root);
	//FroOrder(root);
	//InOrder2(root);

	return 0;
}