(10) Binary tree

Theoretical content transferred from ：https://blog.csdn.net/weixin_51983604/article/details/116451530
Trees
Tree is a kind of nonlinear data structure , It is from n（n>=0） Finite nodes make up a set with hierarchical relations . It's called a tree because it looks like an upside down tree , In other words, it is rooted in , And the leaves below .

There is a special node , It's called the root node , The root node has no precursor node . Except for the root node , The rest of the nodes are divided into m(m > 0) Disjoint sets T1、T2、…… 、Tm, And every set of them Ti(1 <= i <= m) It is also a subtree with a structure similar to that of a tree . The root node of each subtree has and only has one precursor , But there can be 0 One or more successors .

Thus we can see that , Trees are defined recursively .
Concept and structure of binary tree

A binary tree is a finite set of nodes , The collection is empty , Or it is composed of a root node and two binary trees called left subtree and right subtree .

Characteristics of binary trees ：

（1） Each node has at most two subtrees , In other words, the degree of nonexistence of binary tree is greater than 2 The node of .
（2） The subtree of a binary tree has left and right branches , The order of its subtrees cannot be reversed .

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
char str[100];
int treeIndex = 1;
char Nil = ' ';

typedef struct BiTNode
{
	char data;
	struct BiTNode * lchild;
	struct BiTNode * rchild;
}BiTNode, *BiTree;

bool StrAssign(char * T, char * chars)
{
	if (strlen(chars)>100)
	{
		return false;
	}
	else
	{
		T[0] = strlen(chars);
		// This is supposed to be <=, No <
		for (size_t i = 1; i <= T[0]; i++)
		{
			T[i] = *(chars + i - 1);
		}
		return true;
	}
}


bool InitBiTree(BiTree *T)
{
	*T = NULL;
	return true;
}


void DestroyBiTree(BiTree * T)
{
	if (*T)
	{
		if ((*T)->lchild)
		{
			// here (*T)->lchild Modified into &(*T)->lchild
			DestroyBiTree(&(*T)->lchild);
		}
		if ((*T)->rchild)
		{
			// here (*T)->lchild Modified into &(*T)->lchild
			DestroyBiTree(&(*T)->rchild);
		}
		free(*T);
		*T = NULL;
	}
}


void CreateBiTree(BiTree * T)
{
	char ch;
	ch = str[treeIndex++];
	if (ch == '#')
	{
		*T = NULL;
	}
	else
	{
		*T = (BiTree)malloc(sizeof(BiTNode));
		if (!*T)
		{
			return;
		}
		(*T)->data = ch;
		// here (*T)->lchild Modified into &(*T)->lchild
		CreateBiTree(&(*T)->lchild);
		CreateBiTree(&(*T)->rchild);
	}
}

bool BiTreeEmpty(BiTree T)
{
	if (T)
	{
		return false;
	}
	else
	{
		return true;
	}
}

int BiTreeDepth(BiTree T)
{
	int i, j;
	if (!T)
	{
		return 0;
	}
	if (T->lchild)
	{
		i = BiTreeDepth(T->lchild);
	}
	else
	{
		i = 0;
	}
	if (T->rchild)
	{
		j = BiTreeDepth(T->rchild);
	}
	else
	{
		j = 0;
	}
	return i > j ? i + i : j + 1;
}

char Root(BiTree T)
{
	if (BiTreeEmpty(T))
	{
		return Nil;
	}
	else
	{
		return T->data;
	}
}

char value(BiTree T)
{
	return T->data;
}

void Assign(BiTree T, char value)
{
	T->data = value;
}

void PreOrderTraverse(BiTree T)
{
	if (T == NULL)
	{
		return;
	}
	printf("%c", T->data);
	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rchild);
}

void InOrderTraverse(BiTree T)
{
	if (T == NULL)
	{
		return;
	}
	InOrderTraverse(T->lchild);
	printf("%c", T->data);
	InOrderTraverse(T->rchild);
}

void PostOrderTraverse(BiTree T)
{
	if (T == NULL)
	{
		return;
	}
	PostOrderTraverse(T->lchild);
	PostOrderTraverse(T->rchild);
	printf("%c", T->data);
}

int main()
{
	/*int i;*/
	BiTree T;
	char cl;
	InitBiTree(&T);
	StrAssign(str, "ABDH#K###E##CFI###G#J##");
	CreateBiTree(&T);
	printf("Empty = %d(1 = yes 0 = no)  Depth of tree  = %d\n", BiTreeEmpty(T), BiTreeDepth(T));
	cl = Root(T);
	printf(" The root of a binary tree is : %c\n", cl);

	printf("\n Preorder traversal binary tree :");
	PreOrderTraverse(T);
	printf("\n Middle order ergodic binary tree :");
	InOrderTraverse(T);
	printf("\n Post order traversal binary tree :");
	PostOrderTraverse(T);
	return 0;
}