数据结构之树（C语言实现）

enum Status{ERROR = 0,OK = 1};

//二叉树
//--------------------------------------------------------------------------------
//二叉树的链式存储

//第一种结构
typedef struct BinaryNode BinaryNode,*BinaryTree;
struct BinaryNode{
	GenericPointer pData;
	BinaryNode* pLeft;
	BinaryNode* pRight;
}
//第二种结构（添加双亲指针）
typedef struct BinaryNode BinaryNode,*BinaryTree;
struct BinaryNode{
	GenericPointer pData;
	BinaryNode* pLeft;
	BinaryNode* pRight;
	BinaryNode* pParent;
}

//--------------------------------------------------------------------------------
//二叉树的遍历

//前序遍历
Status TraverseInPreorder(BinaryTree pRoot,Status(*visit)()){
	if(pRoot == NULL){
		return OK;
	}
	else{
		if(visit(pRoot->pData)==ERROR){
			return ERROR;
		}
		TraverseInPreorder(pRoot->pLeft,visit);
		TraverseInPreorder(pRoot->pRight,visit);
	}
	return OK;
}
//中序遍历
Status TraverseInOrder(BinaryTree pRoot,Status(*visit)()){
	if(pRoot == NULL){
		return OK;
	}
	else{
		TraverseInOrder(pRoot->pLeft,visit);
		if(visit(pRoot->pData)==ERROR){
			return ERROR;
		}
		TraverseInOrder(pRoot->pRight,visit);
	}
	return OK;
}
//后序遍历
Status TraverseInPostOrder(BinaryTree pRoot,Status(*visit)()){
	if(pRoot == NULL){
		return OK;
	}
	else{
		TraverseInPostOrder(pRoot->pLeft,visit);
		TraverseInPostOrder(pRoot->pRight,visit);
		if(visit(pRoot->pData)==ERROR){
			return ERROR;
		}
	}
	return OK;
}

//--------------------------------------------------------------------------------
//统计叶子结点的个数
//方法一：利用遍历算法完成，代码略
//方法二：采用分治算法，空树返回0，只有一个结点返回1，否则返回左右子树的叶子结点数之和
int NumOfLeaves(BinaryTree pRoot){
	if(pRoot == NULL) return 0;
	if(pRoot->pLeft == NULL && pRoot->pRight == NULL) return 1;
	return NumOfLeaves(pRoot->pLeft)+NumOfLeaves(pRoot->pRight);
}

//--------------------------------------------------------------------------------
//利用拓展的先序序列创建二叉树
//拓展的先序序列：在先序序列的基础上，用特定元素表示空子树
//e.g.  AB.DF..G..C.E.H..
void CreateBinaryTree(BinaryTree *pRoot){//注意这里是一个二重指针
	char ch;
	ch = getchar();
	if(ch == '.') *pRoot = NULL;
	else{
		*pRoot = (BinaryTree)malloc(sizeof(BinaryTree));
		*pRoot -> data = ch;//这里使用的是普通的二叉树结构
		CreateBinaryTree(&((*pRoot)->pLeft));
		CreateBinaryTree(&((*pRoot)->pRight));
	}
}

//还是利用先序序列创建二叉树
Status CreateBinaryTree(BinaryTree* pBinaryTree,char* preorderSequence){
	static int i=0;
	char rootData;
	BinaryNode* pRoot;
	rootData = preorderSequence[i++];
	if(rootData == '\0' || rootData == EMPTY_BINARY_NODE){
		*pBinaryTree=NULL;
        return OK;
	}
	pRoot=(BinaryNode*)malloc(sizeof(BinaryNode));
	if(pRoot == NULL)	return ERROR;
	pRoot->data=rootData;
	*pBinaryTree=pRoot;
	if(CreateBinaryTree(&(pRoot->pLeft),preorderSequence)==ERROR){
        return ERROR;
    }
	if(CreateBinaryTree(&(pRoot->pRight),preorderSequence)==ERROR){
        return ERROR;
    }
    return OK;
}

	
//--------------------------------------------------------------------------------
//求二叉树的高度
int DepthOfBinaryTree(BinaryTree pRoot){
	int h1,h2;
	if(pRoot == NULL) return 0;
	else{
		h1 = DepthOfBinaryTree(pRoot->pLeft)+1;
		h2 = DepthOfBinaryTree(pRoot->pRight)+1;
		return  h1 > h2 ? h1 : h2;
}

//--------------------------------------------------------------------------------
//线索二叉树
typedef enum {NO_CHILD=0, CHILD=1} ThreadTag;
typedef struct BinaryNode BinaryNode, *BinaryTree;
struct BinaryNode {
    GenericPointer pData;
    ThreadTag leftTag;
    BinaryNode* pLeft;
    ThreadTag rightTag;
    BinaryNode* pRight;
};
//按中序进行线索化
void ThreadBinaryTree(BinaryTree pRoot){
	static BinaryNode* pPre = NULL;
	if(pRoot == NULL) return;
	ThreadBinaryTree(pRoot->pLeft);//线索化左子树
	//加线索
	if(pRoot -> leftTag == NO_CHILD){
		pRoot -> pLeft = pPre;
	}
	if(pPre != NULL && pPre -> rightTag == NO_CHILD){
		pPre -> pRight = pRoot;
	}
	pPre = pRoot;
	
	ThreadBinaryTree(pRoot->pRight);//线索化右子树
}

//找中序线索树的前驱节点
BinaryNode* PreviousInorderNode(BinaryNode* pNode){
	BinaryNode* pTemp;
	if(pNode -> leftTag == NO_CHILD)	return pNode->pLeft;
	pTemp = pNode->pLeft;
	//找左子树中最右下端的结点
	while(pTemp->rightTag==CHILD){
		pTemp=pTemp->pRight; 
	}
	return pTemp;
}

//找中序线索树的后继节点
BinaryNode* NextInorderNode(BinaryNode* pNode){
	BinaryNode* pTemp;
	if(pNode->rightTag==NO_CHILD)	return pNode->pRight;
	pTemp=pNode->pRight; 
	//找右子树最左下端的节点
	while(pTemp->leftTag==CHILD){
        pTemp=pTemp->pLeft; 
    }
	return pTemp;
}

//遍历中序线索树
//在中序线索树上找第一个结点
BinaryNode* FirstInorderNode(BinaryTree pRoot){
	if(pRoot == NULL)	return NULL;
	BinaryNode* pTemp = pRoot;
	//找左子树中最左的结点
	while(pTemp->leftTag==CHILD){
		pTemp = pTemp -> pLeft;
	}
	return pTemp;
}
//遍历
Status TraverseInorderThreadedBinaryTree(BinaryTree pRoot,Status(*visit)()){
	BinaryNode* pTemp = FirstInorderNode(pRoot);
	while(pTemp != NULL){
		if(visit(pTemp) == ERROR){
			return ERROR;
		}
		pTemp = NextInorderNode(pTemp);
	}
		return OK;
}


//--------------------------------------------------------------------------------
//利用序列组合创建二叉树
//利用先序和中序序列创建二叉树
Status CreateBinaryTree(BinaryTree* pBinaryTree,char* preorder,char* inorder,int n){
	if(n <= 0) {
        *pBinaryTree=NULL;
        return OK;
    }
	BinaryNode* pRoot = (BinaryNode*)malloc(sizeof(BinaryNode));
	if(pRoot == NULL)	return ERROR;
	pRoot->data = preorder[0];
    *pBinaryTree = pRoot;
	int i=Locate(inorder, preorder[0],n); //返回根的中序位置,该函数省略
	if (i < 0)	return ERROR;
	if(CreateBinaryTree(&(pRoot->pLeft),preorder+1,inorder,i)==ERROR){
        return ERROR;
    }
	if(CreateBinaryTree(&(pRoot->pRight),preorder+i+1,inorder+i+1,n-i-1)==ERROR){
        return ERROR;
    } 
    return OK;
}

//--------------------------------------------------------------------------------
//树
//--------------------------------------------------------------------------------
//双亲表示法
typedef struct {
    TreeElem data;
    int parent;
} TreeNode;
typedef struct {
    TreeNode Tree[MAX_TREE_SIZE];
    int numOfNodes;
} Tree;

//孩子表示法
typedef struct ChildNode{//孩子链表结点定义
    int  child;
    struct ChildNode *pNext;
} ChildNode;
typedef struct {//顺序表结点的定义
    TreeElem data;
    ChildNode* pFirstChild;
} TreeNode;
typedef struct {
    TreeNode  nodeArray[MAX_TREE_SIZE];
    int root;//根节点在线性表中的位置
    int numOfNodes;
} Tree;

//孩子兄弟表示法
typedef struct TreeNode{
    TreeElem data;
    struct TreeNode *pFirstChild;
    struct TreeNode *pNextSibling;
} TreeNode, *Tree;


//树的先根遍历（采用孩子兄弟表示法）
//一：
Status RootFirst(Tree root,Status(*visit)()){
	TreeNode* pTemp;
	if(root != NULL){
		if(visit(root->data) == ERROR)	return ERROR;
		pTemp = root -> pFirstChild;
		while(p != NULL){
			RootFirst(p);
			p = p -> pNextSibling;
		}
	}
	return OK;
}

//二:
Status RootFirst(Tree root,Status(*visit)()){
	if(root != NULL){
		if(visit(root->data) == ERROR)	return ERROR;
		RootFirst(root->data);
		RootFirst(root->pNextSibling);
	}
	return OK;
}


//--------------------------------------------------------------------------------
//哈夫曼树
//--------------------------------------------------------------------------------
//类型定义
typedef struct {
    int weight;
    int parent;
    int leftChild;
    int rightChild;
} HuffmanNode,*HuffmanTree;

//哈夫曼树的构建
HuffmanTree ConstructHuffmanTree(int weight[],int n){
	int m = 2*n-1;
	HuffmanTree ht = (HuffmanTree)malloc(m*sizeof(HuffmanNode));
	if(ht == NULL)	return NULL;
	//初始化
	int i;
	for(i = 0;i < n;i++){
		ht[i].weight = weight[i];
		ht[i].parent = -1;
		ht[i].leftChild = -1;
		ht[i].rightChild = -1;
	}
	for(i = n;i < m;i++){
		ht[i].weight = 0;
		ht[i].parent = -1;
		ht[i].leftChild = -1;
		ht[i].rightChild = -1;
	}
	//构建
	int a,b;//存放权值最小的两个结点并使权值a<b
	for(i = n;i < m;i++){
		if(Select(hf,i,&a,&b)==ERROR)	return NULL;
		ht[i].weight = ht[a].weight+ht[b].weight;
		ht[a].parent = i;
		ht[b].parent = i;
		ht[i].leftChild = a;
		ht[i].rightChild = b;
	}
	return ht;
}

Status Select(HuffmanTree ht,int n,int* pa,int* pb){
	int i,t,a,b;
	for(i = 0;i < n;i++){//找无双亲的第一个结点
		if(ht[i].parent < 0)	break;
	}
	if(i >= n)	return ERROR;
	a = i;
	for(i = a+1;i < n;i++){//找无双亲的第二个结点
		if(ht[i].parent < 0)	break;
	}
	if(i >= n)	return ERROR;
	b = i;
	if(ht[b].weight < ht[a].weight){
		t = a;
		a = b;
		b = t;
	}
	i = a > b ? a : b;
	for(i=i+1;i < n;i++){
		if(ht[i].parent<0 && ht[i].weight<ht[b].weight){
			b = i;
			if(ht[b].weight<ht[a].weight){
				t = a;
				a = b;
				b = t;
			}
		}
	}
	*pa = a;
	*pb = b;
	return OK;
}

//哈夫曼编码
Status PrintHuffmanCode(HuffmanTree ht,int numOfLeaves){
	int i,j,p,k;
	char reverseCode[MAX_CODE_LENGTH];
	if(ht == NULL || numOfLeaves < 2){
		print("ERROR");
		return ERROR;
	}
	for(i = 0;i < numOfLeaves;i++){
		j = i;//从叶子到跟，倒着为第i个叶子编码
		k = 0;//数组的下标
		while(ht[j].parent>0){
			p = ht[j].parent;
			if(j == ht[p].leftChild){
				reverseCode[k] = '0';
			}
			else{
				reverseCode[k] = '1';
			}
			k++;
			j = p;
		}
		print("第%d个叶子节点的编码：");
		k = k-1;
		while(k >= 0){//倒序输出
			putchar(reverseCode[k]);
			k--;
		}
	}
	return OK;
}