5.2 二叉树

我们写一个二叉树,它支持树的插入,删除,查询和遍历,而且左子树的数据都小于右子树的数据(PS:树实际上很难的,想深入了解的话,可以去看看<算法导论>,什么红黑树啊,B树啊什么的,反正我没看懂就是了--估计是我太菜了^_^):

#include 
    
     #include 
     
      #include 
      
       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 
    
     #include 
     
      #include 
      
       #define MAX_SIZE 100typedef 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))}

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 二叉搜索树

这篇文章刚开始的时候就用一个程序开头,就是二叉搜索树的增删查.故不再重复.