非递归创建排序二叉树

非递归创建排序二叉树

今天,博主写了关于一个非递归创建排序二叉树的算法,平时,我们常见的都是递归创建排序二叉树,但是递归的空间复杂度也更高为o(n),相反,非递归的空间复杂度则为o(1),下面是代码,感兴趣的同学,可以学习一下。

Tree* sort_binary(Tree *T, int data) { 	Tree* p=NULL; 	Tree* s=T; 	int l = 0; 	 	if (T == NULL) { 		T = (Tree*)malloc(sizeof(Tree)); 		T->data = data; 		T->lchild = NULL; 		T->rchild = NULL; 		s = T;  	} 	while (T!=NULL&& data!=T->data) { 		p = T; 		if (data < T->data) { 			T = T->lchild; 			l = 0; 		} 		else { T = T->rchild; l = 1; } 	} 	if (p != NULL) { 		if (T == NULL && l == 0) {  			p->lchild = (Tree*)malloc(sizeof(Tree)); 			p->lchild->data = data; 			p->lchild->rchild = NULL; 			p->lchild->lchild = NULL; 		} 		else if(T == NULL && l == 1) { 			p->rchild = (Tree*)malloc(sizeof(Tree)); 			p->rchild->data = data; 			p->rchild->lchild = NULL; 			p->rchild->rchild = NULL; 		} 	} 	return s; 	  } void middle_order(Tree* T) { 	if (T) { 		middle_order(T->lchild); 		printf("%d ", T->data); 	 		middle_order(T->rchild); 	} }    int main() { 	Tree* T = NULL; 	//T = (Tree*)malloc(sizeof(Tree)); 	//T=create_binary_tree(T); 	int a[] = { 5,6,4,7,24,8,4,3,6,7,13,4,7,6 };  	for (int i = 0; i < 9; i++) { 		T=sort_binary(T, a[i]); 		printf("%d  ", T); 	} 	//printf("%d ", T); 	/*printf("%d ", T->lchild); 	printf("%d ", T->rchild);*/ 	middle_order(T); 	//	middle_f(T); 	return 0;  }  

版权声明:玥玥 发表于 2021-03-31 11:21:08。
转载请注明:非递归创建排序二叉树 | 女黑客导航