首页 > 代码库 > 二叉树

二叉树

2024-08-17 00:29:40   215人阅读

1.定义

是每个节点不能对于两个儿子的树。

2.查找二叉树

为每个节点指定一个关键值，每个节点的左子树的关键值都小于节点的关键值，而右子树的关键值都大于节点的关键值。

平均深度为O（logN）。

3. 查找二叉树的实现

1.fatal.h

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

#define Error(str) FatalError(str)
#define FatalError(str) fprintf(stderr,"%s\n",str),system("pause"),exit(1)

　　

2.searchtree.h

#include<stdio.h>
typedef int ElementType;

#ifndef _Tree_H

struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

SearchTree MakeEmpty(SearchTree T);
Position Find(ElementType X, SearchTree T);
Position FindMin(SearchTree T);
Position FindMax(SearchTree T);
SearchTree Insert(ElementType X, SearchTree T);
SearchTree Delete(ElementType X, SearchTree T);
ElementType Retrieve(Position P);
void Preorder(SearchTree T);

#endif

　　

3.searchtree.c

#include "searchtree.h"
#include "fatal.h"
#include <stdio.h>
#include <stdlib.h>

struct TreeNode
{
	ElementType Element;
	SearchTree Left;
	SearchTree Right;
};


SearchTree MakeEmpty(SearchTree T)
{
	if (T!=NULL)
	{
		MakeEmpty(T->Left);
		MakeEmpty(T->Right);
		free(T);
	}
	return NULL;
}

Position Find(ElementType X, SearchTree T)
{
	if (T==NULL)
	{
		return NULL;
	}
	if (X < T->Element)
	{
		return Find(X, T->Left);
	}
	else if (X > T->Element)
	{
		return Find(X, T->Right);
	}
	else
	{
		return T;
	}
}

Position FindMin(SearchTree T)
{
	if (T == NULL)
	{
		return NULL;
	}
	else if (T->Left == NULL)
	{
		return T;
	}
	else
	{
		return FindMin(T->Left);
	}
}

Position FindMax(SearchTree T)
{
	//if (T == NULL)
	//{
	//	return NULL;
	//}
	//else if (T->Right == NULL)
	//{
	//	return T;
	//}
	//else
	//{
	//	return FindMax(T->Right);
	//}
	if (T != NULL)
	{
		while (T->Right != NULL)
		{
			T = T->Right;
		}
	}
	return T;
}

ElementType Retrieve(Position P)
{
	return P->Element;
}

SearchTree Insert(ElementType X, SearchTree T)
{
	if (T == NULL)
	{
		T = malloc(sizeof(struct TreeNode));
		if (T == NULL)
		{
			FatalError("out of space!!!");
		}
		else
		{
			T->Element = X;
			T->Left = T->Right = NULL;
		}
	}
	else if (X < T->Element)
		T->Left = Insert(X, T->Left);
	else if (X > T->Element)
		T->Right = Insert(X, T->Right);
	return T;
}

SearchTree Delete(ElementType X, SearchTree T)
{
	Position TmpCell;
	if (T == NULL)
	{
		Error("Element not found");
	}
	else if (X < T->Element)
		T->Left = Delete(X, T->Left);
	else if (X>T->Right)
		T->Right = Delete(X, T->Right);
	else
	{
		if (T->Left && T->Right)
		{
			TmpCell = FindMin(T->Right);
			T->Element = TmpCell->Element;
			T->Right = Delete(T->Element, T->Right);
		}
		else
		{
			TmpCell = T;
			if (T->Left == NULL)
			{
				T = T->Right;
			}
			else if (T->Right == NULL)
			{
				T = T->Right;
			}
			free(TmpCell);
		}
	}
	return T;
}


void Preorder(SearchTree T)
{

	if (T == NULL)
	{
		Error("Tree not found");
	}
	if (T->Left != NULL)
	{
		Preorder(T->Left);
	}
	if (T->Right != NULL)
	{
		Preorder(T->Right);
	}
	printf("%d\t", Retrieve(T));
}

　　

4.testsearchtree.c

#include "fatal.h"
#include "searchtree.h"
#include <stdio.h>
#include <stdlib.h>


void main1()
{
	SearchTree T = NULL;
	T = MakeEmpty(T);
	int i = 0;
	for (i = 0; i < 10;i++)
	{
		T= Insert(i, T);
	}
	Preorder(T);

	for (i = 0; i < 10; i++)
	{
		T = Delete(i, T);
	}

	system("pause");
}


main()
{
	SearchTree T;
	Position P;
	int i;
	int j = 0;

	T = MakeEmpty(NULL);
	for (i = 0; i < 50; i++)
		T = Insert(i, T);
	//for (i = 0; i < 50; i++, j = (j + 7) % 50)
	//	T = Insert(j, T);

	Preorder(T);

	for (i = 0; i < 50; i++)
		if ((P = Find(i, T)) == NULL /*|| Retrieve(P) != i*/)
			printf("Error at %d\n", i);

	for (i = 0; i < 50; i ++)
		T = Delete(i, T);

	//for (i = 1; i < 50; i += 2)
	//	if ((P = Find(i, T)) == NULL || Retrieve(P) != i)
	//		printf("Error at %d\n", i);
	//for (i = 0; i < 50; i += 2)
	//	if ((P = Find(i, T)) != NULL)
	//		/*printf("Error at %d\n", i);*/

	printf("Min is %d, Max is %d\n", Retrieve(FindMin(T)),
		Retrieve(FindMax(T)));

	system("pause");
	return 0;
}

　　

二叉树


联系
我们