二叉搜索树(binary search tree) 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

二叉搜索树(binary search tree)能够高效的进行插入, 查询, 删除某个元素, 时间复杂度O(logn).

简单的实现方法例如以下.

代码:

/*

 * main.cpp

 *

 *  Created on: 2014.7.20

 *      Author: spike

 */

/*eclipse cdt, gcc 4.8.1*/

#include <stdio.h>

#include <queue>

#include <vector>

#include <functional>

using namespace std;

struct node {

	int val;

	node *lch, *rch;

};

class BinarySearchTree {

public:

	node *insert(node *p, int x) {

		if (p==NULL) {

			node* q = new node;

			q->val = x;

			q->lch = q->rch = NULL;

			return q;

		} else {

			if (x<p->val) p->lch = insert(p->lch, x);

			else p->rch = insert(p->rch, x);

			return p;

		}

	}

	bool find(node *p, int x) {

		if (p==NULL) return false;

		else if (x==p->val) return true;

		else if (x<p->val) return find(p->lch, x);

		else return find(p->rch, x);

	}

	node *remove(node *p, int x) {

		if (p==NULL) return NULL;

		else if (x<p->val) p->lch = remove(p->lch, x);

		else if (x>p->val) p->rch = remove(p->rch, x);

		else if (p->lch == NULL) {

			node* q=p->rch;

			delete p;

			return q;

		} else if (p->lch->rch == NULL) {

			node* q = p->lch;

			q->rch = p->rch;

			delete p;

			return q;

		} else {

			node* q;

			for (q = p->lch; q->rch->rch!=NULL; q=q->rch);

			node* r = q->rch;

			q->rch = r->lch;

			r->lch = p->lch;

			r->rch = p->rch;

			delete p;

			return r;

		}

		return p;

	}

};

int main(void)

{

	BinarySearchTree iBST;

	node* root = NULL;

	root = iBST.insert(root, 7);

	root = iBST.insert(root, 2);

	root = iBST.insert(root, 15);

	root = iBST.insert(root, 1);

	root = iBST.insert(root, 5);

	root = iBST.insert(root, 10);

	root = iBST.insert(root, 17);

	root = iBST.insert(root, 4);

	root = iBST.insert(root, 6);

	root = iBST.insert(root, 8);

	root = iBST.insert(root, 11);

	root = iBST.insert(root, 16);

	root = iBST.insert(root, 19);

	bool isOK = iBST.find(root, 15);

	printf("result = %s\n", isOK?

"Yes":"No");

	iBST.remove(root,15);

	isOK = iBST.find(root, 15);

	printf("result = %s\n", isOK?"Yes":"No");

	isOK = iBST.find(root, 10);

	printf("result = %s\n", isOK?"Yes":"No");

	return 0;

}

输出;

result = Yes

result = No

result = Yes