Datastructures-树(中)

引例：实现一个按字典序的存着12个月的英文单词的二叉搜索树

char* months[12] = {  
	"January", "February", "March", "April",    
	"May", "June", "July", "August",    
	"September", "October", "November", "December"    
};  

▶

解答

综合了前边所有的前置知识，还用到了C语言相关基础。
避坑！：第一个指针T必须事先赋值为NULL，不然会出现一个segmentation fault-段错误，指到了不该指的地方。

#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  

// 定义二叉树节点结构体  
typedef struct TreeNode {  
	char *s;  
	struct TreeNode *Left;  
	struct TreeNode *Right;  
} BinTree;  

// 插入函数  
BinTree* TreeInsert(char *s, BinTree *T) {  
	if (T == NULL) {  
		T = (BinTree*)malloc(sizeof(BinTree));  
		if (T == NULL) {  
			printf("Memory allocation failed\n");  
			exit(EXIT_FAILURE);  
		}  
		T->s = strdup(s);  // 复制字符串  
		T->Left = T->Right = NULL;  
	} else if (strcmp(s, T->s) < 0) {  
		T->Left = TreeInsert(s, T->Left);  
	} else if (strcmp(s, T->s) > 0) {  
		T->Right = TreeInsert(s, T->Right);  
	}  
	// 不处理重复项（如果s等于T->s，则不插入）  
	return T;  
}  

// 中序遍历函数  
void InOrderTraversal(BinTree *T) {  
	if (T != NULL) {  
		InOrderTraversal(T->Left);  
		printf("%s\n", T->s);  
		InOrderTraversal(T->Right);  
	}  
}  

// 释放二叉树内存的函数  
void FreeTree(BinTree *T) {  
	if (T != NULL) {  
		FreeTree(T->Left);  
		FreeTree(T->Right);  
		free(T->s);  // 释放字符串内存  
		free(T);     // 释放节点内存  
	}  
}  

int main() {  
	char* months[12] = {  
		"January", "February", "March", "April",    
		"May", "June", "July", "August",    
		"September", "October", "November", "December"    
	};  
	BinTree *T = NULL;  
	
	// 插入月份到BST  
	for (int i = 0; i < 12; i++) {  
		T = TreeInsert(months[i], T);  
	}  
	
	// 中序遍历BST并打印结果  
	printf("Inorder traversal of BST:\n");  
	InOrderTraversal(T);  
	
	// 释放二叉树内存  
	FreeTree(T);  
	
	return 0;  
}

可以试试把递归和非递归的各种遍历都试试。