fzyz_sb 发表于4年前

• 发表于 4年前
• 阅读 289
• 收藏 14
• 评论 2

5.2 二叉树

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

typedef struct TREE{
int						data;
struct TREE			*leftChild;
struct TREE			*rightChild;
}Tree;

void insertTree( Tree *tree, int data );
void deleteTree( Tree *tree, int data );
int searchTree( Tree *tree, int data );
void showTree( Tree *tree );

int main( void )
{
Tree *tree = ( Tree * )malloc( sizeof( Tree ) );
tree->leftChild = tree->rightChild = NULL;

insertTree( tree, 5 );
insertTree( tree, 3 );
insertTree( tree, 2 );
insertTree( tree, 4 );
insertTree( tree, 8 );
insertTree( tree, 7 );
insertTree( tree, 9 );
insertTree( tree, 6 );

showTree( tree->leftChild );

deleteTree( tree, 3 );
deleteTree( tree, 5 );
deleteTree( tree, 6 );

printf("\n");
showTree( tree->leftChild );

printf("\n");
if ( searchTree( tree, 8 ) ){
printf("8 in the tree\n");
}
else{
printf("8 not in the tree\n");
}

if ( searchTree( tree, 13 ) ){
printf("13 in the tree\n");
}
else{
printf("13 not in the tree\n");
}

return 0;
}

void insertTree( Tree *tree, int data )
{
Tree *newTree = ( Tree * )malloc( sizeof( Tree ) );
newTree->leftChild = newTree->rightChild = NULL;
newTree->data = data;

if ( ( NULL == tree->leftChild ) && ( NULL == tree->rightChild ) ){
tree->leftChild = newTree;
}
else{
tree = tree->leftChild;
while ( NULL != tree ){
if ( data == tree->data ){
return;
}
else if ( data < tree->data ){
if ( NULL == tree->leftChild ){
tree->leftChild = newTree;
return;
}
tree = tree->leftChild;
}
else{
if ( NULL == tree->rightChild ){
tree->rightChild = newTree;
return;
}
tree = tree->rightChild;
}
}
}
}

/*

*/
void deleteTree( Tree *tree, int data )
{
Tree *prevTree = ( Tree * )malloc( sizeof( Tree ) );		//指向删除节点的前一个节点
Tree *tempTree = ( Tree * )malloc( sizeof( Tree ) );		//处理被删除的节点拥有左右树的特殊情况
prevTree = tree;
tree = tree->leftChild;

while ( tree ){
if ( data < tree->data ){
prevTree = tree;
tree = tree->leftChild;
}
else if ( data > tree->data ){
prevTree = tree;
tree = tree->rightChild;
}
else{
//删除节点的左子树为空,则直接用右子树替换该节点
if ( NULL == tree->leftChild ){
if ( data == prevTree->leftChild->data ){
prevTree->leftChild = prevTree->leftChild->rightChild;
}
else{
prevTree->rightChild = prevTree->rightChild->rightChild;
}
}
else if ( NULL == tree->rightChild ){		//删除节点的右子树为空,则直接用左子树替换该节点
if ( data == prevTree->leftChild->data ){
prevTree->leftChild = prevTree->leftChild->leftChild;
}
else{
prevTree->rightChild = prevTree->rightChild->leftChild;
}
}
else{
tempTree = tree;		//保存右子树中最小节点的前节点
tree = tree->rightChild;
while ( tree->leftChild ){			//找到最小节点
tempTree = tree;
tree = tree->leftChild;
}
//替换数据
if ( data == prevTree->leftChild->data ){
prevTree->leftChild->data = tree->data;
}
else{
prevTree->rightChild->data = tree->data;
}

//删除最小节点
if ( tempTree->leftChild->data == tree->data ){
tempTree->leftChild = tree->rightChild;
}
else{
tempTree->rightChild = tree->rightChild;
}
}
break;
}
}
}
int searchTree( Tree *tree, int data )
{
tree = tree->leftChild;
while ( tree ){
if ( data == tree->data ){
return 1;
}
else if ( data < tree->data ){
tree = tree->leftChild;
}
else{
tree = tree->rightChild;
}
}

return 0;
}
void showTree( Tree *tree )
{
if ( tree ){
printf("%d ", tree->data );
showTree( tree->leftChild );
showTree( tree->rightChild );
}
}``````

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

#define MAX_SIZE 100
typedef struct TREE{
int						data;
struct TREE			*leftChild;
struct TREE			*rightChild;
}Tree;

Tree *stack[ MAX_SIZE ];
int top = 0;
int rear = 0;

void insertTree( Tree *tree, int data );
void showTree( Tree *tree );

int main( void )
{
Tree *tree = ( Tree * )malloc( sizeof( Tree ) );
tree->leftChild = tree->rightChild = NULL;

insertTree( tree, 5 );
insertTree( tree, 3 );
insertTree( tree, 2 );
insertTree( tree, 4 );
insertTree( tree, 8 );
insertTree( tree, 7 );
insertTree( tree, 9 );
insertTree( tree, 6 );

showTree( tree->leftChild );

return 0;
}

void insertTree( Tree *tree, int data )
{
Tree *newTree = ( Tree * )malloc( sizeof( Tree ) );
newTree->leftChild = newTree->rightChild = NULL;
newTree->data = data;

if ( ( NULL == tree->leftChild ) && ( NULL == tree->rightChild ) ){
tree->leftChild = newTree;
}
else{
tree = tree->leftChild;
while ( NULL != tree ){
if ( data == tree->data ){
return;
}
else if ( data < tree->data ){
if ( NULL == tree->leftChild ){
tree->leftChild = newTree;
return;
}
tree = tree->leftChild;
}
else{
if ( NULL == tree->rightChild ){
tree->rightChild = newTree;
return;
}
tree = tree->rightChild;
}
}
}
}

void showTree( Tree *tree )
{
stack[ rear++ ] = tree;
while ( 1 ){
tree = stack[ top++ ];
if ( tree ){
printf("%d ", tree->data );
if ( tree->leftChild ){
stack[ rear++ ] = tree->leftChild;
}
if ( tree->rightChild ){
stack[ rear++ ] = tree->rightChild;
}
}
else{
break;
}
}
}``````

5.4 二叉树的其他操作

1. 二叉树的复制

2. 判断二叉树的等价性

``````int equal(tree_pointer first, tree_pointer second )
{
return ((!first && !second)||(first && second &&
(first->data == second->data)) &&
equal(first->left_child, second->left_child) &&
equal(first->right_child, second->right_child))
}``````

3. 交换左右子树
``````void swapLeftRight( Tree *tree )
{
if ( tree ){
Tree *tempTree = ( Tree * )malloc( sizeof( Tree ) );
tempTree = tree->leftChild;
tree->leftChild = tree->rightChild;
tree->rightChild = tempTree;
swapLeftRight( tree->leftChild );
swapLeftRight( tree->rightChild );
}
}``````

5.5 线索二叉树

5.6 堆

1. 最大树是指在树中,一个结点有儿子结点,其关键字都不小于儿子结点的关键字值.最大堆是一棵完全二叉树,也是一棵最大树.

2. 最小数是指在树中,一个结点有儿子结点,其关键字都不大于儿子结点的关键字值.最小堆是一棵完全二叉树,也是一棵最小数.

5.7 二叉搜索树

×