C语言树总结

#include 
#include 
 typedef struct BitNode {
	int data;//数据域
	struct BitNode* lchild;//左孩子指针
	struct BitNode* rchild;//右孩子指针
	//struct BitNode* parent;//三叉链表
}BitNode,*BiTree;//二叉树二叉链表链式存储
 
 
 int visit(BiTree A) {
	 return A->data;
 }
 void PreOrder(BiTree T) {
	 if (T!= NULL) {
		 visit(T);
		 PreOrder(T->lchild);
		 PreOrder(T->rchild);
	 }
 }//先序遍历根左右
 void InOrder(BiTree T) {
	 if (T != NULL) {
		 InOrder(T->lchild);
		 visit(T);
		 InOrder(T->rchild);
	 }
 }//中序遍历左根右
 void PostOrder(BiTree T) {
	 if (T != NULL) {
		 PostOrder(T->lchild);
		 PostOrder(T->rchild);
		 visit(T);
	 }
 }//后序遍历左右根
 //时间复杂度O(n)
 void LevelOrder(BiTree T) {
	 //InitQueue(Q);初始化辅助队列
	 BiTree p;//队头元素
	// InQueue(Q, T);根节点入队
	
 }//层次遍历
 
 typedef struct ThreadNode {
	 int data;//数据域
	 struct ThreadNode* lchild, * rchild;//左右孩子指针
	 struct ThreadNode* ltag, * rtag;//左右线索标志ltag为0 lchild指左孩子为1指前驱
 }ThreadNode,*ThreadTree;//线索二叉树
 void InThread(ThreadTree p, ThreadTree pre) {//pre为P的前驱pre为刚访问过的结点p为正在访问的结点
	 if (p != NULL) {
		 InThread(p->lchild, pre);
		 //visit(p);
		 if (p->lchild == NULL) {
			 p->lchild = pre;
			 p->ltag = 1;
		 }
		 if (pre != NULL && pre->rchild == NULL) {
			 pre->rchild = p;
			 pre->rtag = 1;
		 }
		 pre = p;
		 InThread(p->rchild, pre);
	 }
 }//中序遍历的二叉树线索化
 void CreatInThread(ThreadTree T) {
	 ThreadTree pre = NULL;
	 if (T != NULL) {
		 InThread(T, pre);
		 pre->lchild = NULL;
		 pre->ltag = 1;
	 }
 }//建立中序线索二叉树
 ThreadNode* Firstnode(ThreadNode* p){
	 while (p->ltag == 0)
		 p = p->lchild;
	 return p;
 }//找以p为根结点的树的中序序列中第一个结点
 ThreadNode* Nextnode(ThreadNode* p) {
	 if (p->ltag == 1) {
		 return p->lchild;
	 }
	 else {
		 return Firstnode(p->lchild);
	 }
 }//求p在中序序列中的后继
 void Inorder(ThreadNode* T) {
	 for (ThreadNode* p = Firstnode(T); p != NULL; p = Nextnode(p)) {
		 visit(p);
	 }
 }//中序遍历
#define Max_Tree_Size 100
 typedef struct PTNode {
	 int data;//数据域
	 int parent;//双亲位置域
 }PTNode;
 typedef struct PTree {
	 PTNode nodes[Max_Tree_Size];
	 int node;//结点数
 }PTree;//树的双亲表示法根结点位置为0 parent置-1
 typedef struct CBNode {
	 int data;//数据域
	 struct CBNodde* firstchild, * rightbrother;//结点第一个孩子指针，右兄弟指针
 }CBNode,*CBTree;//孩子兄弟表示法用于树森林转化为二叉树
 
 typedef struct BSTNode {
	 int key;//数据域
	 struct BSTNode* lchild, * rchild;//左孩子指针，右孩子指针
 }BSTNode,*BSTree;//排序二叉树
 BSTNode* BST_Search(BSTree T, int key) {
	 while (T != NULL && T->key != key) {
		 if (T->key > key) {
			 T = T->lchild;
		 }
		 else {
			 T = T->rchild;
		 }
	 }
	 return T;
 }//非递归查找操作空间复杂度O（1）
 BSTNode* BST_Search(BSTree T, int key) {
	 if (T == NULL) {
		 return NULL;
	 }
	 else if (T->key == key)
		 return T;
	 else if (T->key > key)
		 return BST_Search(T->lchild, key);
	 else
		 return BST_Search(T->rchild, key);
 }//递归查找操作空间复杂度O(h)
 bool BST_Insert(BSTree T, int k) {
	 if (T->key == k)
		 return false;
	 else if (T->key > k) {
		 return BST_Insert(T->lchild, k);
	 }
	 else if (T->key < k) {
		 return BST_Insert(T->rchild, k);
	 }
	 else {
		 T = (BSTNode*)malloc(sizeof(BSTNode));
		 T->key = k;
		 T->lchild = T->rchild = NULL;
		 return true;
	 }
 }//二叉排序树插入操作
 void Creat_BST(BSTree T, int str[], int n) {//T为根结点 str为要插入二叉树中的数值数组 n为数据个数
	 T = NULL;
	 int i = 0;
	 while (i < n) {
		 BST_Insert(T, str[i]);
		 i++;
	 }
 }//二叉排序树的构造将二叉排序树中序遍历可得到递增序列