数据结构关于二叉树的各种算法

根据extended preOrder sequence建立二叉树 三种遍历的递归算法 三种遍历的非递归算法 层顺遍历的非递归算法 树深度 宽度 叶子数 节点数 度为1节点数的算法 树的克隆 根据两种顺序建立二叉树

#include 
#include 

using namespace std;

typedef struct BinNode
{
    char data;
    struct BinNode *lch *rch;
} BinNode;
//--------------------------------------------------------------------------
BinNode* createTree_InPost（const string& inOrder const string& PostOrder）;
BinNode* createTree_PreIn（const string preOrder const string& inOrder）;
void display（BinNode* t）;
void destroy（BinNode *t）;
//--------------------------------------------------------------------------
int main（）
{
    BinNode *binNode;
    string preOrder inOrder postOrder;
    //----------------------------------------------
    cout << “Enter the inOrder and the postOrder to create the tree“ << endl;
    cin >> inOrder >> postOrder;
    binNode = createTree_InPost（inOrder postOrder）;
    if（!binNode）
    {
        cout << “creating fails“ << endl;
        exit（-1）;
    }
    display（binNode）;
    destroy（binNode）;
    cout << endl << endl;
    //----------------------------------------------
    cout << “Enter the inOrder and the postOrder to create the tree“ << endl;
    cin >> preOrder >> inOrder;
    binNode = createTree_PreIn（preOrder inOrder）;
    if（!binNode）
    {
        cout << “creating fails“ << endl;
        exit（-1）;
    }
    display（binNode）;
    destroy（binNode）;
    //----------------------------------------------
    return 0;
}


BinNode* createTree_InPost（const string& inOrder const string& PostOrder）
{
    if （inOrder.empty（） || PostOrder.empty（））
        return NULL;
    char rootC = *（PostOrder.end（） - 1）; //find the root node
    string::size_type rootIndex = inOrder.find_first_of（rootC）;
    string leftMidIn = inOrder.substr（0 rootIndex）;
    string rightMidIn = inOrder.substr（rootIndex+1）;
    string leftLastIn;
    string rightLastIn;
    string::const_iterator curIter = PostOrder.begin（）;
    string::const_iterator endIter = PostOrder.end（）;
    for （; curIter!=endIter; ++curIter）
    {
        char c = *curIter;
        if （leftMidIn.find_first_of（c） != string::npos）
        {
            leftLastIn.push_back（c）;
        }
        else if （rightMidIn.find_first_of（c） != string::npos）
        {
            rightLastIn.push_back（c）;
        }
    }
    BinNode* tree = new BinNode;
    tree->data = rootC;
    tree->lch = createTree_InPost（leftMidIn leftLastIn）;
    tree->rch = createTree_InPost（rightMidIn rightLastIn）;
    return tree;
}

BinNode* createTree_PreIn（const string preOrder const string& inOrder）
{
    if （preOrder.empty（） || inOrder.empty（））
        return NULL;

    char rootC = *preOrder.begin（）;
    string::size_type rootIndex = inOrder.find_first_of（rootC）;
    string leftInOrder = inOrder.substr（0 rootIndex）;
    string rightInOrder = inOrder.substr（rootIndex+1）;
    string leftPreOrder rightPreOrder;
    string::const_iterator curIter = preOrder.begin（）;
    string::const_iterator endIter = preOrder.end（）;
 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       4015  2012-10-16 11:28  createBinTree_twoOrder.cpp

     文件      10612  2012-10-30 15:40  createBiTree_preorder.cpp

----------- ---------  ---------- -----  ----

                14627                    2