作业1

问题1

请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。
二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。

• 二叉树头文件BinaryTree.h

#ifndef BT
#define BT

#include <iostream>
using namespace std;

//模板节点类
template <class Type>
class BinTreeNode
{
public:
    BinTreeNode<Type> *leftChild=NULL, *rightChild=NULL;
    Type data;
};


//模板二叉树类
template <class Type>
class BinaryTree
{
public:
    BinTreeNode<Type> *root ;

    BinaryTree(){ root = NULL;};
    BinaryTree(BinTreeNode<Type> *r){root = r;}
    BinaryTree(const Type& key){ BinTreeNode<Type> r(key); root = &r;}

    void PreOrder(BinTreeNode<Type> *current);
    void InOrder(BinTreeNode<Type> *current);
    void PostOrder(BinTreeNode<Type> *current);

    BinTreeNode<Type>*  create();
    void destroy(BinTreeNode<Type>* r);
};

//删除包含输入节点及以其为根节点的子树,后序删除
template <typename T>
void BinaryTree<T>::destroy(BinTreeNode<T>* r)
{
    if(r != NULL)
    {
        destroy(r->leftChild);
        destroy (r->rightChild);
        cout << "删除值为" << r->data << "的节点" << endl;
        delete r;
    }
}


template <typename T>
BinTreeNode<T>* BinaryTree<T>::create(){

    BinTreeNode<T>* current;

    T val;
    //cout << "按照中序，输入字符串。‘-’表示NULL：" << endl;
    cin >> val;//输入键值
    cout << "读入" << val << endl;
    if(val == '-')//标识当前子树为空，转向下一节点
    {
        cout << "空节点" << endl;
        return NULL;
    }
    else{
        current = new BinTreeNode<T>;
        current->data = val;
        cout << "创建一个非空节点，值是" << val << endl;
        current->leftChild = create();
        current->rightChild = create();
    }
    return current;
}


template <class Type>
void BinaryTree<Type>::PreOrder(BinTreeNode<Type> *current)
{
    if(current != NULL)
    {
        cout << current->data;
        PreOrder (current->leftChild);
        PreOrder (current->rightChild);
    }
}

template <class Type>
void BinaryTree<Type>::InOrder(BinTreeNode<Type> *current)
{
    if(current != NULL)
    {
        InOrder(current->leftChild);
        cout << (current->data);
        InOrder (current->rightChild);
    }
}

template <class Type>
void BinaryTree<Type>::PostOrder(BinTreeNode<Type> *current)
{
    if(current != NULL)
    {
        PostOrder(current->leftChild);
        PostOrder (current->rightChild);
        cout << (current->data);

    }
}

#endif

• main函数文件

#include<iostream>
#include "BinaryTree.h"
using namespace std;

template <typename T>
BinTreeNode<T> * leafLink(BinTreeNode<T> *r);
void hw1_1();

int main()
{
    hw1_1();
}

void hw1_1()
{
    BinTreeNode<char> *head;
    BinTreeNode<char> *temp;
    cout << "按照中序，输入字符串。‘-’表示NULL：" << endl;//abd--ef--g--c--
    BinaryTree<char> tree;
    tree.root = tree.create();
    cout << "............." <<endl;
    head = leafLink(tree.root);
    cout << "单链表：" << endl;

    while(head->rightChild != NULL)
    {
        temp=head;
        cout << head->data << "-->";
        head = head->rightChild;
        temp->rightChild = NULL;
    }

    cout << head->data <<endl;

    tree.destroy(tree.root);
}

template <typename T>
BinTreeNode<T> * leafLink(BinTreeNode<T> *r)
{
    static BinTreeNode<T> *s1,*s2;
    //static int flag=0;
    //BinTreeNode<T>* current;
    if(r == NULL)
        return NULL;
    if(r->leftChild ==NULL && r->rightChild == NULL)
    {
        if(s2==NULL)
        {   s2 = r;s1 = r; cout << "找到一个叶子节点,值是" << s1->data << endl;} //cout << "找到一个叶子节点,值是" << s1->data << endl;}
        else
        {   s2->rightChild = r;s2 = r;cout << "找到一个叶子节点,值是" << r->data << endl;} //cout << "找到一个叶子节点,值是" << r->data << endl;}
    }
    else
    {
        leafLink(r->leftChild);
        leafLink(r->rightChild);
    }

    return s1;
}

• 运行测试

  1. 构建的二叉树为：

     
     
  2. 控制台输入及输出：

按照中序，输入字符串。‘-’表示NULL：
abd--ef--g--c--
读入a
创建一个非空节点，值是a
读入b
创建一个非空节点，值是b
读入d
创建一个非空节点，值是d
读入-
空节点
读入-
空节点
读入e
创建一个非空节点，值是e
读入f
创建一个非空节点，值是f
读入-
空节点
读入-
空节点
读入g
创建一个非空节点，值是g
读入-
空节点
读入-
空节点
读入c
创建一个非空节点，值是c
读入-
空节点
读入-
空节点
.............
找到一个叶子节点,值是d
找到一个叶子节点,值是f
找到一个叶子节点,值是g
找到一个叶子节点,值是c
单链表：
d-->f-->g-->c
删除值为d的节点
删除值为f的节点
删除值为g的节点
删除值为e的节点
删除值为b的节点
删除值为c的节点
删除值为a的节点

问题2

已知二叉树以二叉链表存储，编写算法完成：对于树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。

• main函数文件

#include<iostream>
#include "BinaryTree.h"
using namespace std;

template <typename T>
BinTreeNode<T> * leafLink(BinTreeNode<T> *r);
void hw1_1();
void hw1_2();

int main()
{
    hw1_2();
}

template <typename T>
void findAndDel(T &key, BinTreeNode<T> *r, BinaryTree<T> &tree);
void hw1_2()
{
    cout << "按照中序，输入字符串。‘-’表示NULL：" << endl;
    BinaryTree<char> tree;
    tree.root = tree.create();
    cout << "目前树的前序输出:  ";
    tree.PreOrder(tree.root);
    cout << endl;

    char key;
    cout << "输入要删除的字符" << endl;
    cin >> key;

    findAndDel(key, tree.root, tree);

    cout << "............."<< endl;
    cout << "删除值为"<<key<<"节点后，树的前序输出:  ";
    tree.PreOrder(tree.root);
    cout << endl;
    tree.destroy(tree.root);
}


template <typename T>
void findAndDel(T &key, BinTreeNode<T> *r, BinaryTree<T> &tree)
{
    if(r != NULL)
    {
        if(key == r->data)
        {
            cout << "找值为"<< r->data <<"的节点" << endl;
            tree.destroy(r->leftChild);
            tree.destroy(r->rightChild);
            r->leftChild = NULL;
            r->rightChild = NULL;
        }
        else
        {
            //cout << "找值为"<< r->data <<"的左子树" << endl;
            findAndDel(key, r->leftChild, tree);
            //cout << "找值为"<< r->data <<"的右子树" << endl;
            findAndDel(key, r->rightChild, tree);
        }
    }
}

• 运行测试

按照中序，输入字符串。‘-’表示NULL：
abd--ef--g--ceh--k--i--
读入a
创建一个非空节点，值是a
读入b
创建一个非空节点，值是b
读入d
创建一个非空节点，值是d
读入-
空节点
读入-
空节点
读入e
创建一个非空节点，值是e
读入f
创建一个非空节点，值是f
读入-
空节点
读入-
空节点
读入g
创建一个非空节点，值是g
读入-
空节点
读入-
空节点
读入c
创建一个非空节点，值是c
读入e
创建一个非空节点，值是e
读入h
创建一个非空节点，值是h
读入-
空节点
读入-
空节点
读入k
创建一个非空节点，值是k
读入-
空节点
读入-
空节点
读入i
创建一个非空节点，值是i
读入-
空节点
读入-
空节点
目前树的前序输出:  abdefgcehki
输入要删除的字符
e
找值为e的节点
删除值为f的节点
删除值为g的节点
找值为e的节点
删除值为h的节点
删除值为k的节点
.............
删除值为e节点后，树的前序输出:  abdecei
删除值为d的节点
删除值为e的节点
删除值为b的节点
删除值为e的节点
删除值为i的节点
删除值为c的节点
删除值为a的节点