头歌 数据结构 实验五——二叉树及其应用

前言：

这个实验总共有五关，都是基础知识，总共也才花了我一个小时(狗头保命)，除了第四五关的非递归比较难想，其他的都是小case，这里就不过多解释了。

第一关：实现二叉树的创建

BiTreeNode* CreatBiTree(char* s, int &i, int len)
// 利用先序遍历创建二叉树
// 参数：先序遍历字符串s，字符串初始下标i=0，字符串长度len。
// 返回：二叉树
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    BiTreeNode* root=new BiTreeNode;
    if(s[i]=='#'){
        root=NULL;
        i++;
    }else{
        root->data=s[i];
        i++;
        root->left=CreatBiTree(s,i,len);
        root->right=CreatBiTree(s,i,len);
    }
    return root;

    /********** End **********/
}

void InOrder(BiTreeNode* root)
// 二叉树的中序遍历
// 参数：二叉树根节点root
// 输出：中间没有空格，末尾不换行。
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    if(root!=NULL){
        InOrder(root->left);
        printf("%c",root->data);
        InOrder(root->right);
    }
    
    /********** End **********/

}

第二关：计算二叉树的深度和节点个数

int GetTreeDepth(BiTreeNode* root)
// 计算该二叉树的深度
// 参数：二叉树根节点root
// 返回：二叉树的深度
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    if(!root){
        return 0;
    }else{
        return 1+(GetTreeDepth(root->left)>=GetTreeDepth(root->right)?GetTreeDepth(root->left):GetTreeDepth(root->right));
    }
    /********** End **********/
}

int GetNodeNumber(BiTreeNode* root)
// 计算该二叉树的总节点个数
// 参数：二叉树根节点root
// 返回：二叉树的总节点个数
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    if(!root){
        return 0;
    }else{
        return 1+GetNodeNumber(root->right)+GetNodeNumber(root->left);
    }
    /********** End **********/
}

int GetLeafNodeNumber(BiTreeNode* root)
// 计算该二叉树的叶子节点个数
// 参数：二叉树根节点root
// 返回：二叉树的叶子节点个数
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    if(!root){
        return 0;
    }else if(!root->left&&!root->right){
        return 1;
    }else{
        return GetLeafNodeNumber(root->left)+GetLeafNodeNumber(root->right);
    }
    /********** End **********/
}

第三关：递归实现二叉树左右子树交换

BiTreeNode* BiTreeChange(BiTreeNode* root)
// 实现二叉树左右子树的交换（递归法）
// 参数：二叉树根节点root
// 返回：二叉树
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    if(!root){
        return NULL;
    }else{
        BiTreeChange(root->left);
        BiTreeChange(root->right);
        BiTreeNode* tmp=root->left;
        root->left=root->right;
        root->right=tmp;
    }
    
    /********** End **********/
}


void PreOrder(BiTreeNode* root)
// 二叉树的前序遍历
// 参数：二叉树根节点root
// 输出：二叉树的前序遍历，中间没有空格，末尾不换行。
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    if(root){
        printf("%c",root->data);
        PreOrder(root->left);
        PreOrder(root->right);
    }
    
    /********** End **********/
}

第四关：非递归实现二叉树左右子树交换

BiTreeNode* BiTreeChangeStack(BiTreeNode* root)
// 实现二叉树左右子树的交换（栈实现）
// 参数：二叉树根节点root
// 返回：二叉树
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    stack<BiTreeNode*> s;
    BiTreeNode *p=root;
    if(root==NULL){
        return NULL;
    }
    s.push(root);
    while(!s.empty()){
        BiTreeNode *temp=p->left;
        p->left=p->right;
        p->right=temp;
        if(p->left!=NULL){
            s.push(p->left);
        }
        if(p->right!=NULL){
            s.push(p->right);
        }
        p=s.top();
        s.pop();
    }
    return root;
    /********** End **********/
}
void PostOrder(BiTreeNode* root)
// 二叉树的后序遍历
// 参数：二叉树根节点root
// 输出：二叉树的后序遍历，中间没有空格，末尾不换行。
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    if(root!=NULL){
        PostOrder(root->left);
        PostOrder(root->right);
        printf("%c",root->data);
    }
    /********** End **********/
}

第五关：层次遍历二叉树

void HierarchyOrder(BiTreeNode* root)
// 二叉树的层次遍历（队列实现）
// 参数：二叉树根节点root
// 输出：二叉树的层次遍历，中间没有空格，末尾不换行。
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    queue<BiTreeNode*> q;
    BiTreeNode *now;
    q.push(root);
    while(!q.empty()){
        now=q.front();
        if(now!=NULL){
            printf("%c",now->data);
        }
        if(now->left!=NULL){
            q.push(now->left);
        }
        if(now->right!=NULL){
            q.push(now->right);
        }
        q.pop();
    }
    /********** End **********/
}