（10）二叉树

理论内容转自：https://blog.csdn.net/weixin_51983604/article/details/116451530
树
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根在上，而叶在下的。

有一个特殊的结点，称为根结点，根节点没有前驱结点。除根节点外，其余结点被分成m(m > 0)个互不相交的集合T1、T2、…… 、Tm，其中每一个集合Ti(1 <= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，但可以有0个或多个后继。

由此可知，树是递归定义的。
二叉树概念及结构

一棵二叉树是结点的一个有限集合，该集合为空，或者是由一个根节点加上两棵称为左子树和右子树的二叉树组成。

二叉树的特点：

（1）每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
（2）二叉树的子树有左右之分，其子树的次序不能颠倒。

#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);
		//这里应该是<=，不是<
		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)
		{
			//这里(*T)->lchild修改成&(*T)->lchild
			DestroyBiTree(&(*T)->lchild);
		}
		if ((*T)->rchild)
		{
			//这里(*T)->lchild修改成&(*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;
		//这里(*T)->lchild修改成&(*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) 树的深度 = %d\n", BiTreeEmpty(T), BiTreeDepth(T));
	cl = Root(T);
	printf("二叉树的根为: %c\n", cl);

	printf("\n前序遍历二叉树:");
	PreOrderTraverse(T);
	printf("\n中序遍历二叉树:");
	InOrderTraverse(T);
	printf("\n后序遍历二叉树:");
	PostOrderTraverse(T);
	return 0;
}