course_data_structures/Data Structure Class 6/hw8-9-10/BiTreeTest.cpp

#include <fstream>
#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
#include "Bitree.h"
#include "SeqStack.h"

template <class T>
BinTreeNode<T> *MakeTreeNode(const T item, BinTreeNode<T> *left = NULL, BinTreeNode<T> *right = NULL)
//由结点构造二叉树
{
    BinTreeNode<T> *p;
    p = new BinTreeNode<T>(item, left, right);
    return p;
}
BinTreeNode<char> *MakeCharTree()
//创建不带头结点的二叉链表
{
    BinTreeNode<char> *b, *c, *d, *e, *f, *g, *null = NULL, *root;
    g = MakeTreeNode('G');
    d = MakeTreeNode('D', null, g);
    b = MakeTreeNode('B', d);
    e = MakeTreeNode('E');
    f = MakeTreeNode('F');
    c = MakeTreeNode('C', e, f);
    root = MakeTreeNode('A', b, c);
    return root;
}

//已知二叉树的前序遍历序列preS和中序遍历序列inS，采用递归算法构造二叉树。
template <class T>
BinTreeNode<T> *createBinaryTree(T *VLR, T *LVR, int n)
{
    if (n == 0) return NULL;
    int k = 0;
    while (VLR[0] != LVR[k]) k++;
    BinTreeNode<T> *t = new BinTreeNode<T>(VLR[0]);
    t->leftChild = createBinaryTree(VLR + 1, LVR, k);
    t->rightChild = createBinaryTree(VLR + k + 1, LVR + k + 1, n - k - 1);
    return t;
}
template <class T>
void visit(BinTreeNode<T> *p)
{
    cout << p->data << " ";
}
int main()
{
    //构造二叉树1:前序遍历建立二叉树,从文件输入前序遍历序列（使用0表示空）
    ifstream fin("data.txt");
    assert(fin);
    BinaryTree<int> binTree(0); //输入序列中使用0表示空
    assert(fin >> binTree);     //前序遍历建立二叉树
    fin.close();
    cout << "\nThe binary tree is: \n"
         << binTree << endl;       //输出1：前序遍历输出二叉树到屏幕
    PrintBTree(binTree.getRoot()); //输出2：以广义表形式输出二叉树到屏幕
    ofstream fout("output.txt");
    assert(fout);
    assert(fout << binTree); //输出3：前序遍历输出二叉树到文件
    fout.close();
    BinaryTree<int> binTree1(binTree); //复制构造
    cout << "\n\nThe copy binary tree is: \n"
         << binTree1 << endl;
    PrintBTree(binTree1.getRoot());

    if (binTree == binTree1) //判相等
        cout << "\n\nThe two binary is equal. ";
    else
        cout << "\n\nThe two binary is not equal. ";

    //构造二叉树2:从广义表输入，前序遍历建立二叉树
    //binTree.CreateBinTree(cin,Tree.getRoot());

    //计算二叉树的高度
    cout << "\n\n二叉树高度等于" << binTree.Height() << endl;

    //测试-非递归算法计算二叉树的深度
    if (binTree.NonR_Height() != binTree.Height())
        cout << "\n\nERROR:二叉树高度应该等于" << binTree.Height();

    //计算二叉树的结点个数
    cout << "\n二叉树结点个数等于" << binTree.Size() << endl;

    //二叉树的遍历
    cout << "\n前序遍历结点次序为: ";
    binTree.preOrder(visit);

    cout << "\n中序遍历结点次序为: ";
    binTree.inOrder(visit);

    cout << "\n后序遍历结点次序为: ";
    binTree.postOrder(visit);

    //测试-判断平衡： 判断二叉树是否为平衡二叉树
    bool IsbTree = binTree.IsBalanced();
    if (IsbTree == true)
        cout << endl
             << "\n\n二叉树为平衡二叉树！" << endl;
    else
        cout << "\n\n二叉树为非平衡二叉树!" << endl;

    //构造二叉树3：根据前序遍历preS和中序遍历inS创建二叉树
    char *preS, *inS;
    preS = "ABDGCEF";
    inS = "DBGAECF";
    BinaryTree<char> *Tree = new BinaryTree<char>('^');
    Tree->setRoot(createBinaryTree<char>(preS, inS, 7)); //前序建立二叉树方法2
    cout << endl;
    //Tree->PrintBTree(test->getRoot(),0);
    cout << "\nThe binary tree is: \n";
    PrintBTree(Tree->getRoot());

    //测试-判断平衡： 判断二叉树是否为平衡二叉树
    IsbTree = Tree->IsBalanced();
    if (IsbTree == true)
        cout << endl
             << "\n二叉树为平衡二叉树！" << endl;
    else
        cout << endl
             << "\n二叉树为非平衡二叉树!" << endl;
    cout << endl;

    //测试-非递归算法计算二叉树的深度
    if (Tree->NonR_Height() != Tree->Height())
        cout << "\nERROR:二叉树高度应该等于" << Tree->Height();
    else
        cout << endl
             << "二叉树高度等于" << Tree->Height();

    //二叉树的非递归遍历
    cout << "\n非递归前序遍历结点次序1为: ";
    Tree->NonR_preOrder(visit);
    cout << "\n非递归前序遍历结点次序2为: ";
    Tree->NonR_preOrder1(visit);

    cout << "\n非递归中序遍历结点次序为: ";
    Tree->NonR_inOrder(visit);

    cout << "\n非递归后序遍历结点次序为: ";
    Tree->NonR_postOrder(visit);
    cout << endl;

    //测试-构造二叉树
    BinaryTree<char> Test('#');
    BinTreeNode<char> *p;
    //Test.setRoot(MakeCharTree());
    p = Test.Insert(Test.getRoot(), 'A', 0);
    p = Test.Insert(p, 'B', 0);
    p = Test.Insert(p, 'D', 0);
    p = Test.Insert(p, 'G', 1);
    p = Test.Insert(Test.getRoot(), 'C', 1);
    Test.Insert(p, 'E', 0);
    Test.Insert(p, 'F', 1);

    cout << "\nThe binary tree is: \n";
    PrintBTree(Test.getRoot(), 0); //以凹入表形式输出二叉树
    //二叉树的非递归遍历
    cout << "\n非递归前序遍历结点次序为: ";
    Test.NonR_preOrder(visit);

    cout << "\n非递归中序遍历结点次序为: ";
    Test.NonR_inOrder(visit);

    cout << "\n非递归后序遍历结点次序为: ";
    Test.NonR_postOrder(visit);
    cout << endl;

    //测试-判断平衡： 判断二叉树是否为平衡二叉树
    IsbTree = Test.IsBalanced();
    if (IsbTree == true)
        cout << endl
             << "\n\n二叉树为平衡二叉树！" << endl;
    else
        cout << "\n\n二叉树为非平衡二叉树!" << endl;
    cout << endl;

    //测试-查找
    cout << "G的双亲是" << Test.Parent(Test.Find('G'))->data << endl;
    cout << "D的双亲是" << Test.Parent(Test.Find('D'))->data << endl;
    cout << "B的双亲是" << Test.Parent(Test.Find('B'))->data << endl;
    cout << "E的双亲是" << Test.Parent(Test.Find('E'))->data << endl;
    cout << "F的双亲是" << Test.Parent(Test.Find('F'))->data << endl;
    cout << "C的双亲是" << Test.Parent(Test.Find('C'))->data << endl;

    //测试-非递归算法计算二叉树的深度
    if (Test.NonR_Height() != Test.Height())
        cout << "\nERROR:二叉树高度应该等于" << Test.Height();
    else
        cout << endl
             << "二叉树高度等于" << Test.Height();
    system("pause");
}