bintree.cpp

计算生物二叉树的matlab具体程序

#include "BinTree.h"

//构造函数
CBinTree::CBinTree()
{
	m_root = NULL;
}

/************************************************************************/
/* 用一个Key类型的数组，初始化这个Tree                                  */
/* pK 指向这个数组的指针                                                */
/* iLen 数组的长度                                                      */
/************************************************************************/
void CBinTree::InitTree(Key* pK, int iLen)
{
	for (int i = 0; i < iLen; i++)
	{
		TNode* node = new TNode;
		node->k = pK[i];
		node->parent = NULL;
		node->left = NULL;
		node->right = NULL;

		Insert(node);
	}
}

/************************************************************************/
/* 把节点z插入到树中去                                                  */
/************************************************************************/
void CBinTree::Insert(TNode* z)
{
	TNode *y = NULL;
	TNode *x = m_root;

	while (x != NULL)
	{
		y = x;
		if (x->k < z->k)
		{
			x = x->right;
		}
		else
		{
			x = x->left;
		}
	}

	z->parent = y;

	if (y == NULL)
	{
		m_root = z;
	}

	if (y->k > z->k)
	{
		y->left = z;
	}
	else
	{
		y->right = z;
	}	
}

/************************************************************************/
/* 把节点z从树中删掉，分三种情况                                        */
/* 1 z没有子结点，直接删除                                              */
/* 2 z只有一个子节点，直接把其子树做为其父节点的子树                    */
/* 3 z有两个子节点，找到z的后继，把后继节点放到z 的位置，在调整树       */
/************************************************************************/
TNode* CBinTree::Delete(TNode* z)
{
	TNode *y = new TNode;
	TNode *x = new TNode;
	if (z->left == NULL || z->right == NULL)
	{
		y = z;
	}
	else
	{
		y = successor(z);
	}

	if (y->left != NULL)
	{
		x = y->left;	
	}
	else
	{
		x = y->right;
	}

	if (x != NULL)
	{
		x->parent = y->parent;
	}
	
	if (y->parent == NULL)
	{
		m_root = x;
	}
	else
	{
		if (y->parent->left == y)
		{
			y->parent->left = x;
		}
		if (y->parent->right == y)
		{
			y->parent->right = x;
		}
	}

	if (y != z)
	{
		TNode* temp = y;
		y = z;
		z = temp;
	}

	return y;
}

//找到节点x的后继节点
TNode* CBinTree::successor(TNode* x)
{
	if (x->right != NULL)
	{
		return tree_min(x->right);
	}

	TNode* y = x->parent;

	while (y != NULL && x == y->right)
	{
		x = y;
		y = y->parent;
	}

	return y;
}

//找到节点x的前驱节点
TNode* CBinTree::predecessor(TNode* x)
{
	if (x->left != NULL)
	{
		return tree_max(x->left);
	}

	TNode* y = x->parent;

	while (y != NULL && x == y->left)
	{
		x = y;
		y = y->parent;
	}

	return y;
}

//找到以root为根的树中Key最小的节点
TNode* CBinTree::tree_min(TNode* root)
{
    while (root != NULL)
    {
		root = root->left;
    }

	return root;
}

//找到以root为根的树中Key最大的节点
TNode* CBinTree::tree_max(TNode* root)
{
    while (root != NULL)
    {
		root = root->right;
    }

	return root;
}

//查找以root为根，Key等于k的节点
TNode* CBinTree::tree_search(Key k, TNode* root)
{
	if (k == root->k)
	{
		return root;
	}
	else if (k < root->k)
	{
		return tree_search(k, root->left);
	}
	else
	{
		
		return tree_search(k, root->right);
	}
}