普通二叉树的C语言实现

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

typedef struct {
	BiTree base;
	BiTree top;
	int stacksize;
}SqStack;


typedef struct {
	BiNode* data;
	int front;
	int rear;
}SqQueue;

void CreatBiTree(BiTree* T)  // Function CreatBiTree create position for every node, so pass in the pointer.
{							 // Also, lchild & rchild are both pointer, for the function can be valid with T and its children here needs a pointer points at BiTree rather than a single struct.
	char ch = ' ';
	printf("Print pre-order-traverse:\n");
	scanf_s("%c", &ch, 8);  
	setvbuf(stdin, NULL, _IOFBF, 512);
	if (ch == '#') { *T = NULL; }  //'#' means the current node is an empty node. 
	else{
		*T = (BiNode*)malloc(sizeof(BiNode));
		if (!*T)
		{
			printf("ERROR!\n");
		}
		else 
		{
			(*T)->data = ch;
			CreatBiTree(&(*T)->lchild);  // Pay attention: pass in the address here.
			CreatBiTree(&(*T)->rchild);  
		}
	}
}

void PreOrderTraverse(BiTree T)  // Traverse order: root, leftchild, rightchild
{
	if (T == NULL) 
	{
		printf("");
	}
	else
	{
		printf("%c ", T->data);
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
}



void InOrderTraverse(BiTree T)  // Traverse order: leftchild, root, rightchild
{
	if (T == NULL)
	{
		printf("");
	}
	else
	{
		InOrderTraverse(T->lchild);
		printf("%c ", T->data);
		InOrderTraverse(T->rchild);
	}
}


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

int Depth(BiTree T)
{
	int m, n;
	if (T == NULL) 
	{
		return 0;
	}
	else
	{
		m = Depth(T->lchild);
		n = Depth(T->rchild);
		if (m > n) {return m + 1;}
		else{return n + 1;}
	}
		
}


int NodeCount(BiTree T)
{
	if (T == NULL) { return 0; }
	else { return (NodeCount(T->lchild) + NodeCount(T->rchild) + 1); }
}


int LeafCount(BiTree T)
{
	if (T == NULL) 
	{
		return 0;
	}
	else
	{
		if (T->lchild == NULL && T->rchild == NULL)
		{
			return 1;
		}
		else
		{
			return (LeafCount(T->lchild) + LeafCount(T->rchild));
		}
	}
}

void Init_sq(SqStack* sta)  // Functio Init spares memory for pointer base and top.
{
	sta->base = (BiTree)malloc(100 * sizeof(BiTree));
	if (!sta->base) { printf("error!"); }
	sta->top = sta->base = NULL;
	sta->stacksize = 100;
}


void Push(BiTree T, SqStack* sta)
{
	if (sta->top - sta->base == sta->stacksize) { printf("ERROR! Stack is full.\n"); }
	else 
	{
		sta->top->data = T->data;  // Here 'sta->top = T' doesn't work because this will change the position of pointer top.
		sta->top->rchild = T->rchild;
		sta->top->lchild = T->lchild;
		sta->top++;
	}
}


BiTree Pop(BiTree T, SqStack* sta)
{ 
	if (sta->base == sta->top) { printf("ERROR!"); return NULL; }
	else
	{
		sta->top--;
		T = sta->top;
		return T;
	}
}


int StackEmpty(SqStack* sta)
{
	if (sta->base == sta->top) { return 0; }
	else { return 1; }
}

void StackTraverseInOrder(BiTree T, SqStack* sta)
{
	BiTree p = (BiNode*)malloc(sizeof(BiNode));
	BiTree q = (BiNode*)malloc(sizeof(BiNode));
	p = T; q = T;
	sta->top = sta->base = T;
	while (p || StackEmpty(sta) == 1)
	{
		if (p)
		{
			Push(p, sta);  // Q1: Why sta->base changes after this step? A1: When the value of a pointer changes, the pointer's position changes.
			p = p->lchild;
		}
		else
		{
			q = Pop(q, sta);
			printf("%c ", q->data);
			p = q->rchild;
		}
	}
}

SqQueue* Initial(SqQueue* que)
{
	que->front = que->rear = 0;
	que->data = (BiNode*)malloc(100 * sizeof(BiNode));
	if (!que->data) { printf("ERROR!"); }
	return que;
}


void EnQueue(SqQueue* que, BiNode* T)
{
	// The method of using less than one spatial element is used to distinguish empty queues from full queues.
	if ((que->rear + 1) % MAXSIZE == que->front) { printf("Queue is full. Fail to insert.\n"); }
	else {
		que->data[que->rear] = *T;
		que->rear = (que->rear + 1) % MAXSIZE;  // Make queue a circle.
	}
}


BiTree DeQueue(SqQueue* que, BiTree T)
{
	if (que->front == que->rear) { printf("Queue is empty.\n"); }
	*T = que->data[que->front];
	que->front = (que->front + 1) % MAXSIZE;
	return T;
}


int QueueEmpty(SqQueue* que)
{
	if (que->front == que->rear) { return 0; }
	else { return 1; }
}


void LevelOrder(BiTree T, SqQueue* que)
{
	BiTree new = (BiTree)malloc(sizeof(BiTree));
	Initial(que);
	EnQueue(que, T);
	while (QueueEmpty(que) != 0)
	{
		new = DeQueue(que, new);
		printf("%c ", new->data);
		if (new->lchild != NULL)
		{
			EnQueue(que, new->lchild);
		}
		if (new->rchild != NULL)
		{
			EnQueue(que, new->rchild);
		}
	}
}

int main() {
	int d;
	int num;
	int leaf;
	BiTree BT = (BiNode*)malloc(sizeof(BiNode));
	SqStack* sqs = (SqStack*)malloc(sizeof(SqStack));
	SqQueue* sqq = (SqQueue*)malloc(sizeof(SqQueue));
	if (BT)
	{
		CreatBiTree(&BT);
	}
	printf("PreOrderTraverse: ");
	PreOrderTraverse(BT);
	printf("\n");
	printf("InOrderTraverse: ");
	InOrderTraverse(BT);
	printf("\n");
	printf("AfOrderTraverse: ");
	AfOrderTraverse(BT);
	printf("\n");
	d = Depth(BT);
	printf("The depth of binary tree is: %d\n", d);
	num = NodeCount(BT);
	printf("Total node: %d\n", num);
	leaf = LeafCount(BT);
	printf("Total leaves: %d\n", leaf);
	printf("----------------------------\n");
	Init_sq(sqs);
	printf("InOrderTraverse with stack: ");
	StackTraverseInOrder(BT, sqs);
	printf("\nLevelOrder: ");
	LevelOrder(BT, sqq);
	return 0;
}