D.S.BinarySearchTree||Pre，In，Post Order）&&InYin

注意结合二叉树： Pre，In，Post Order 利用：return || 递归倒序思考 || 或者 建立后从前到后处理！！！

template
void BinaryTree::PreOrder( BinTreeNode subTree,void( \visit )(BinTreeNode *p ) )
{
if( subTree != NULL ){
visit( subTree );
PreOrder( subTree->leftChild ,visit);
PreOrder( subTree->rightChild,visit );
}
}
template
void BinaryTree::InOrder( BinTreeNode subTree,void( \visit )(BinTreeNode *p ) )
{//中序遍历以 subTree为根的子树
if( subTree != NULL )
{
InOrder( subTree->leftChild,visit );
visit(subTree);
InOrder( subTree->rightChild,visit );
}
}
template
void BinaryTree::PostOrder( BinTreeNode subTree,void( \visit )(BinTreeNode *p ) )
{
if( subTree != NULL )
{
PostOrder( subTree->leftChild,visit );
PostOrder( subTree->rightChild,visit );
visit( subTree );
}
}

后序遍历的应用：

template
int BinaryTree::Size( BinTreeNode* subTree ) const{
//计算以 subTree 为根的二叉树的的结点个数
if( subTree == NULL ) return 0;
else
return 1 + Size( subTree->leftChild ) + Size( subTree->rightChild );
}//+Height

前序遍历的应用：

template
BinTreeNode BinaryTree::Copy( BinTreeNode orignode )
{//给出一个 以origin为根的二叉树的副本
if( orignode == NULL ) return NULL;
BinTreeNode temp = new BinTreeNode;
temp->data = orignode->data;
temp->leftChild = Copy( orignode->leftChild );
temp->rightChild = Copy( orignode->rightChild );
return temp;
}
template
int operator==( const BinaryTree& s, const BinaryTree& t ){
return ( equal( s.root,t.root ) ) ? true :false ;
}
template
bool equal( BinTreeNode a,BinTreeNode b )
{
if( a == NULL && b == NULL ) return true;
else
if( a != NULL && b != NULL && a->data ==b->data && equal(a->leftChild ,b->leftChild ) && equal( a->rightChild,b->rightChild ) )
return true;
else
return false;
}
template
void BinaryTree::CreateBinTree( istream& in,BinTreeNode & subTree)
{
T item;
if( !in.eof() )
{
in >> item;
if( item != RefValue ){
subTree = new BinTreeNode;
subTree->data = item;
if ( subTree == NULL ){
cerr << “ 存储分配错误！ “ << endl;exit(1);
}
CreateBinTree( in,subTree->leftChild );
CreateBinTree( in,subTree->rightChild );
}
else
subTree == NULL;
}
}
template
void PrintBTree(BinTreeNode BT)
{// 以广义表的形式输出二叉树的算法
if( BT != NULL ){
cout << BT->data;
if( BT->leftChild != NULL || BT->rightChild != NULL ){
cout << “(“;
PrintBTree(BT->leftChild);
cout << “,”;
PrintBTree(BT->rightChild);
cout << “)”;
}
}
}
int main()
{
//BinTreeNode root;
//istream in;
BinaryTree testNone;
//Errorz! testNone.CreateBinTree( root );
cin >> testNone;
cout << “录入完成！” << endl;
PrintBTree(testNone.getRoot());
cout << “Hello world!” << endl;
return 0;
}

递归是一种算法结构，回溯是一种算法思想 一个递归就是在函数中调用函数本身来解决问题 回溯就是通过不同的尝试来生成问题的解，有点类似于穷举，但是和穷举不同的是回溯会“剪枝”，意思就是对已经知道错误的结果没必要再枚举接下来的答案了，比如一个有序数列1,2,3,4,5，我要找和为5的所有集合，从前往后搜索我选了1，然后2，然后选3 的时候发现和已经大于预期，那么4,5肯定也不行，这就是一种对搜索过程的优化。