C语言版数据结构- C语言实现二叉树，含详细的源代码

• BinaryTree.h 头文件

#include 
#include 
//定义函数返回的类型
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//定义数据元素的类型为字符型
typedef int Status;
typedef char TElemType; 
//二叉树的二叉链表存储表示
typedef struct BiTNode {
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
Status CreateBiTree(BiTree &T) {
	TElemType ch;
	scanf("%c", &ch);
	if (ch == '#') {
		T = NULL;
	} else {
		if (!(T=(BiTNode*)malloc(sizeof(BiTNode)))) {
			exit(OVERFLOW);
		}
//		new
		T->data = ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
	return OK;
}
//返回二叉树的深度
int Depth(BiTree T) {
	int depthval;
	if(!T) {
		depthval = 0;
	} else {
		int depthLeft = Depth(T->lchild);
		int depthRight = Depth(T->rchild);
		depthval = 1 + (depthLeft > depthRight ? depthLeft : depthRight);
	}
	return depthval;
}
//输出结点的数据元素
Status PrintElement(TElemType e) {
	printf("%c", e);
	return OK;
}
//先序遍历二叉树的递归算法
Status PreOrderTraverse(BiTree T) {
	if(T) {
		PrintElement(T->data);
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
	return OK;
}
//中序遍历二叉树的递归算法
Status InOrderTraverse(BiTree T) {
	if(T) {
		InOrderTraverse(T->lchild);
		PrintElement(T->data);
		InOrderTraverse(T->rchild);
	}
	return OK;
}
//后序遍历二叉树的递归算法
Status PostOrderTraverse(BiTree T) {
	if(T) {
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		PrintElement(T->data);
	}
	return OK;
}

//返回叶子节点的个数
int leafNodeCount = 0;
int getLeafNodeCount(BiTree T) {
	if(T) {
		if(T->lchild == NULL && T->rchild == NULL) {
			leafNodeCount++;
		}
		getLeafNodeCount(T->lchild);
		getLeafNodeCount(T->rchild);
	}
	return leafNodeCount;
}
//输出节点的左孩子和右孩子
void LeftAndRightChild(BiTree T, TElemType e) {
	if(T) {
		if (T->data == e) {
			printf("%s%c%s", "左孩子: ", T->lchild==NULL ? ' ':T->lchild->data, " ; ");
			printf("%s%cn", "右孩子: ", T->rchild==NULL ? ' ':T->rchild->data);
		}
		LeftAndRightChild(T->lchild, e);
		LeftAndRightChild(T->rchild, e);
	}
}
//括号法输出二叉树
void outPut(BiTree T) {
	if (T) {
		printf("%c", T->data);	
		if (T->lchild==NULL && T->rchild==NULL) {
			return;
		}
		printf("%c", '(');
		outPut(T->lchild);
		printf("%c", ',');
		outPut(T->rchild);
		printf("%c", ')');						
	}
}

• exp 主程序

#include "BinaryTree.h"
int main() {
	BiTNode* T;
	CreateBiTree(T);
	printf("%s", "(1)以括号表示法输出二叉树T: ");
	outPut(T);
	printf("n%s", "(2)输出H结点的左、右孩子结点值: ");
	LeftAndRightChild(T, 'H');
	printf("%s%dn", "(3)输出二叉树T的叶子结点个数: ", getLeafNodeCount(T));
	printf("%s%d", "(4)输出二叉树T的深度: ",Depth(T));
	printf("n%s", "(5)输出对二叉树T的先序遍历序列: ");
	PreOrderTraverse(T);
	printf("n%s", "(6)输出对二叉树T的中序遍历序列: ");
	InOrderTraverse(T);
	printf("n%s", "(7)输出对二叉树T的后序遍历序列: ");
	PostOrderTraverse(T);
	return 0;
}