有关C语言中的二进制搜索树操作的问题 [英] Question about binary search tree operations in C language

问题描述

你好朋友，我在编写一个c语言程序来进行操作时遇到问题，这些程序用于在二叉搜索树中进行插入，预排序，排序，后排序，删除和节点搜索.我有搜索网络，但是找到的程序包含tree.h或windows.h头文件，这些文件在我的Turbo C软件中无法打开.如果有人可以给我提供这个代码，那就太好了.实际问题来了，预购和后购也要比整棵树删除节点.也是C.
因为它很快，所以并不完美.如果有多个具有相同值的节点，搜索将很难找到所有节点，我将保留delete供您实现.

另外，此代码没有经过良好的测试，您应该检查结果的准确性.

除了您的要求之外，您可能还希望实现Balance()方法来平衡树，否则在极端情况下，它最终可能会成为具有更大内存占用量的链表.

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

//I don''t know if Turbo C has NULL defined
#ifndef NULL
	#define NULL 0
#endif

typedef struct tagBSTNode {
	int nValue; //This could be a struct or whatever other data type you are using as the nodes
	tagBSTNode *pLeft; //The left child node for elements that are less than this element
	tagBSTNode *pRight; //The right child node for elements that are greater than or equal to this node
} BSTNode;

BSTNode *CreateNode(int nValue) { //The parameter here would be whatever data type the node is representing
	BSTNode *pNode = (BSTNode *)malloc(sizeof(BSTNode));
	if (pNode == NULL) {
		puts("Out of memory.");
		exit(-1);
	}
	pNode->nValue = nValue;
	pNode->pLeft = NULL;
	pNode->pRight = NULL;
	return pNode;
}

void DestroyNode(BSTNode *pNode) {
	if (pNode != NULL) {
		free(pNode);
	}
}

void DestroyTree(BSTNode *pHead) {
	if (pHead->pLeft != NULL) {
		DestroyTree(pHead->pLeft);
	}
	if (pHead->pRight != NULL) {
		DestroyTree(pHead->pRight);
	}
	DestroyNode(pHead);
}

//This function compares 2 BSTNodes and returns their relationship in terms of sorted order:
// <0 if pNode1 < pNode2
// =0 if pNode1 == pNode2
// >0 if pNode1 > pNode2
int CompareNodes(BSTNode *pNode1, BSTNode *pNode2) {
	if (pNode1->nValue < pNode2->nValue) {
		return -1;
	} else if (pNode1->nValue > pNode2->nValue) {
		return 1;
	} else {
		return 0;
	}
}

//This function compares a BSTNode and an int and returns the relationship in terms of sorted order:
// <0 if pNode > nValue
// =0 if pNode == nValue
// >0 if pNode < nValue
int CompareNode(BSTNode *pNode, int nValue) {
	if (pNode->nValue > nValue) {
		return -1;
	} else if (pNode->nValue < nValue) {
		return 1;
	} else {
		return 0;
	}
}

//Returns the new head of (sub)tree. In most cases this will be the same value as pHead.
BSTNode *InsertNode(BSTNode *pHead, BSTNode *pNew) {
	if (pHead == NULL) { //The tree is empty.
		return pNew; //This is now the head element in the tree
	}
	if (CompareNodes(pNew, pHead) < 0) { //pNew needs to go to the left
		if (pHead->pLeft == NULL) { //There are no child nodes on the left. Set it and return the head.
			pHead->pLeft = pNew;
		} else {
			pHead->pLeft = InsertNode(pHead->pLeft, pNew); //Recurse through the tree untill we find an empty child node
		}
		return pHead; //Return the head element
	} else { //pNew needs to go to the right
		//This could also be that pNew == pHead. It is up to you which side it goes, I chose right (greater than)
		if (pHead->pRight == NULL) { //There are no child nodes on the right. Set it and return the head.
			pHead->pRight = pNew;
		} else {
			pHead->pRight = InsertNode(pHead->pRight, pNew); //Recurse through the tree untill we find an empty child node
		}
		return pHead; //Return the head element
	}
}

void PrintTreePreOrder(BSTNode *pHead) {
	//Iterates the tree in pre-order and prints each element
	//Hopefully you can see how to do pre-order and post-order
	printf("%d ", pHead->nValue);
	if (pHead->pLeft != NULL) {
		PrintTreePreOrder(pHead->pLeft);
	}
	if (pHead->pRight != NULL) {
		PrintTreePreOrder(pHead->pRight);
	}
}

void PrintTreeInOrder(BSTNode *pHead) {
	//Iterates the tree in order and prints each element
	if (pHead->pLeft != NULL) {
		PrintTreeInOrder(pHead->pLeft);
	}
	printf("%d ", pHead->nValue);
	if (pHead->pRight != NULL) {
		PrintTreeInOrder(pHead->pRight);
	}
}

void PrintTreePostOrder(BSTNode *pHead) {
	//Iterates the tree in post-order and prints each element
	if (pHead->pLeft != NULL) {
		PrintTreePostOrder(pHead->pLeft);
	}
	if (pHead->pRight != NULL) {
		PrintTreePostOrder(pHead->pRight);
	}
	printf("%d ", pHead->nValue);
}

BSTNode *SearchTree(BSTNode *pHead, int nValue) {
	if (pHead == NULL) {
		return NULL; //Element not found
	}
	int nCmp = CompareNode(pHead, nValue);
	if (nCmp == 0) {
		return pHead; //This is the element we are looking for
	} else if (nCmp < 0) {
		return SearchTree(pHead->pLeft, nValue);
	} else { //if (nCmp > 0)
		return SearchTree(pHead->pRight, nValue);
	}
}

int main() {
	BSTNode *pBST = NULL;
	//This will build a sample tree from the following values
	int nSampleValues[] = { 5, 1, 8, 0, 2, 3 };
	int nSearchValues[] = { 3, 1, 7 };
	int nValue;
	for (nValue = 0; nValue < sizeof(nSampleValues) / sizeof(nSampleValues[0]); ++nValue) {
		pBST = InsertNode(pBST, CreateNode(nSampleValues[nValue]));
	}
	printf(" Pre-order: ");
	PrintTreePreOrder(pBST);
	printf("\n");
	printf("  In-order: ");
	PrintTreeInOrder(pBST);
	printf("\n");
	printf("Post-order: ");
	PrintTreePostOrder(pBST);
	printf("\n");
	for (nValue = 0; nValue < sizeof(nSearchValues) / sizeof(nSearchValues[0]); ++nValue) {
		printf("Searching for %d: ", nSearchValues[nValue]);
		if (SearchTree(pBST, nSearchValues[nValue]) == NULL) {
			printf("Not Found\n");
		} else {
			printf("Found\n");
		}
	}
	//Cleanup the memory used
	DestroyTree(pBST);
	return 0;
}

Hi friends I am having problem while coding a c language program for operations as insert, preorders, inorders, postorders ,deletion and searching of nodes in a binary search tree. I have search net but programs that I found has tree.h or windows.h header files which does not open in my Turbo C software. Please if anyone can provide me this code would be great. Actual problem is coming for preorders and postorders also deletion of node than whole tree.

解决方案

I wrote up a quick tree implementation in Visual C, but it should work in Turbo C as well.
Because it was quick, it isn''t perfect. Search will have trouble finding all nodes if there are more than 1 with the same value, and I will leave delete for you to implement.

Also, this code was not well tested, you should check the accuracy of the results.

In addition to your requirements, you may also wish to implement a Balance() method to balance the tree, otherwise in extreme circumstance it can end up as a linked list with a bigger memory footprint.

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

//I don''t know if Turbo C has NULL defined
#ifndef NULL
	#define NULL 0
#endif

typedef struct tagBSTNode {
	int nValue; //This could be a struct or whatever other data type you are using as the nodes
	tagBSTNode *pLeft; //The left child node for elements that are less than this element
	tagBSTNode *pRight; //The right child node for elements that are greater than or equal to this node
} BSTNode;

BSTNode *CreateNode(int nValue) { //The parameter here would be whatever data type the node is representing
	BSTNode *pNode = (BSTNode *)malloc(sizeof(BSTNode));
	if (pNode == NULL) {
		puts("Out of memory.");
		exit(-1);
	}
	pNode->nValue = nValue;
	pNode->pLeft = NULL;
	pNode->pRight = NULL;
	return pNode;
}

void DestroyNode(BSTNode *pNode) {
	if (pNode != NULL) {
		free(pNode);
	}
}

void DestroyTree(BSTNode *pHead) {
	if (pHead->pLeft != NULL) {
		DestroyTree(pHead->pLeft);
	}
	if (pHead->pRight != NULL) {
		DestroyTree(pHead->pRight);
	}
	DestroyNode(pHead);
}

//This function compares 2 BSTNodes and returns their relationship in terms of sorted order:
// <0 if pNode1 < pNode2
// =0 if pNode1 == pNode2
// >0 if pNode1 > pNode2
int CompareNodes(BSTNode *pNode1, BSTNode *pNode2) {
	if (pNode1->nValue < pNode2->nValue) {
		return -1;
	} else if (pNode1->nValue > pNode2->nValue) {
		return 1;
	} else {
		return 0;
	}
}

//This function compares a BSTNode and an int and returns the relationship in terms of sorted order:
// <0 if pNode > nValue
// =0 if pNode == nValue
// >0 if pNode < nValue
int CompareNode(BSTNode *pNode, int nValue) {
	if (pNode->nValue > nValue) {
		return -1;
	} else if (pNode->nValue < nValue) {
		return 1;
	} else {
		return 0;
	}
}

//Returns the new head of (sub)tree. In most cases this will be the same value as pHead.
BSTNode *InsertNode(BSTNode *pHead, BSTNode *pNew) {
	if (pHead == NULL) { //The tree is empty.
		return pNew; //This is now the head element in the tree
	}
	if (CompareNodes(pNew, pHead) < 0) { //pNew needs to go to the left
		if (pHead->pLeft == NULL) { //There are no child nodes on the left. Set it and return the head.
			pHead->pLeft = pNew;
		} else {
			pHead->pLeft = InsertNode(pHead->pLeft, pNew); //Recurse through the tree untill we find an empty child node
		}
		return pHead; //Return the head element
	} else { //pNew needs to go to the right
		//This could also be that pNew == pHead. It is up to you which side it goes, I chose right (greater than)
		if (pHead->pRight == NULL) { //There are no child nodes on the right. Set it and return the head.
			pHead->pRight = pNew;
		} else {
			pHead->pRight = InsertNode(pHead->pRight, pNew); //Recurse through the tree untill we find an empty child node
		}
		return pHead; //Return the head element
	}
}

void PrintTreePreOrder(BSTNode *pHead) {
	//Iterates the tree in pre-order and prints each element
	//Hopefully you can see how to do pre-order and post-order
	printf("%d ", pHead->nValue);
	if (pHead->pLeft != NULL) {
		PrintTreePreOrder(pHead->pLeft);
	}
	if (pHead->pRight != NULL) {
		PrintTreePreOrder(pHead->pRight);
	}
}

void PrintTreeInOrder(BSTNode *pHead) {
	//Iterates the tree in order and prints each element
	if (pHead->pLeft != NULL) {
		PrintTreeInOrder(pHead->pLeft);
	}
	printf("%d ", pHead->nValue);
	if (pHead->pRight != NULL) {
		PrintTreeInOrder(pHead->pRight);
	}
}

void PrintTreePostOrder(BSTNode *pHead) {
	//Iterates the tree in post-order and prints each element
	if (pHead->pLeft != NULL) {
		PrintTreePostOrder(pHead->pLeft);
	}
	if (pHead->pRight != NULL) {
		PrintTreePostOrder(pHead->pRight);
	}
	printf("%d ", pHead->nValue);
}

BSTNode *SearchTree(BSTNode *pHead, int nValue) {
	if (pHead == NULL) {
		return NULL; //Element not found
	}
	int nCmp = CompareNode(pHead, nValue);
	if (nCmp == 0) {
		return pHead; //This is the element we are looking for
	} else if (nCmp < 0) {
		return SearchTree(pHead->pLeft, nValue);
	} else { //if (nCmp > 0)
		return SearchTree(pHead->pRight, nValue);
	}
}

int main() {
	BSTNode *pBST = NULL;
	//This will build a sample tree from the following values
	int nSampleValues[] = { 5, 1, 8, 0, 2, 3 };
	int nSearchValues[] = { 3, 1, 7 };
	int nValue;
	for (nValue = 0; nValue < sizeof(nSampleValues) / sizeof(nSampleValues[0]); ++nValue) {
		pBST = InsertNode(pBST, CreateNode(nSampleValues[nValue]));
	}
	printf(" Pre-order: ");
	PrintTreePreOrder(pBST);
	printf("\n");
	printf("  In-order: ");
	PrintTreeInOrder(pBST);
	printf("\n");
	printf("Post-order: ");
	PrintTreePostOrder(pBST);
	printf("\n");
	for (nValue = 0; nValue < sizeof(nSearchValues) / sizeof(nSearchValues[0]); ++nValue) {
		printf("Searching for %d: ", nSearchValues[nValue]);
		if (SearchTree(pBST, nSearchValues[nValue]) == NULL) {
			printf("Not Found\n");
		} else {
			printf("Found\n");
		}
	}
	//Cleanup the memory used
	DestroyTree(pBST);
	return 0;
}

这篇关于有关C语言中的二进制搜索树操作的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！