数据结构练习题目（二叉树部分）

一、判断二叉树A中是否有与B相同的子树

#include<iostream>
#include<stdlib.h>
#include<malloc.h>
#include <stack>
using namespace std;
struct BinaryTreeNode {
    char value;
    BinaryTreeNode *left;
    BinaryTreeNode *right;
};

class BinaryTree {
public:
    BinaryTreeNode* root;
    BinaryTree() {}//构造函数
    BinaryTreeNode * CreateBinaryTree();  //建立二叉树
};

BinaryTreeNode * BinaryTree::CreateBinaryTree() //建树函数
{
    BinaryTreeNode *T;
    char data;
    cin >> data;
    if (data == '#')
        T = NULL;
    else
    {
        T = new BinaryTreeNode;
        T->value = data;
        T->left = CreateBinaryTree();
        T->right = CreateBinaryTree();
    }
    return T;
}

bool isSameTree(BinaryTreeNode *rootT,  BinaryTreeNode * rootB)//判断树是否相同
{
    if (rootT == NULL && rootB == NULL) //子父都为空，为真
        return true;
    else if ((rootT == NULL && rootB != NULL) || (rootT != NULL && rootB == NULL))
        return false;
    else if (rootT->value == rootB->value) //如果相同，进入下一层比较
    {
        return isSameTree(rootT->left, rootB->left) && isSameTree(rootT->right, rootB->right);
    }
    return false;
}

bool isSubTree(BinaryTreeNode *rootA, BinaryTreeNode * rootB)//判断是否是子树
{
    if (isSameTree(rootA, rootB)) //如果两树相同，返回true
        return true;
    if (rootB == NULL) //B为空，返回true
        return true;
    if (rootA == NULL) //A为空，则返回false
        return false;
    if (rootA->value == rootB->value) //如果相同，进入下一层比较
        return isSubTree(rootA->left, rootB->left) || isSubTree(rootA->right, rootB->right);
    return isSubTree(rootA->left, rootB) || isSubTree(rootA->right, rootB);
//相似只需要某个部分相同，所以可以比较左子树部分和右子树部分，取两者其一
}

int main()
{
    BinaryTree A, B;
    A.root=A.CreateBinaryTree();
    B.root = B.CreateBinaryTree();
    if (isSameTree(A.root, B.root))
        cout << "两树相同\n";
    if (isSubTree(A.root, B.root))
        cout << "B是A的子树\n";
    return 0;
}

二、编写一个将二叉树的所有叶子结点从左向右链接成单链表的算法

#include<iostream>
#include<stdlib.h>
#include<malloc.h>
#include <stack>
#include <queue>
using namespace std;
struct BinaryTreeNode {  //结点结构体定义
    char value;
    BinaryTreeNode *left;
    BinaryTreeNode *right;
};

struct listNode {         //链表结点定义
    char data;
    listNode *next;
};
listNode *L = new listNode;

BinaryTreeNode* CreateTree()//建树
{
    BinaryTreeNode * T;
    char ch;
    cin >> ch;
    if (ch == '#')
        T = NULL;
    else
    {
        T = new BinaryTreeNode;
        T->value = ch;
        T->left = CreateTree();
        T->right = CreateTree();
    }
    return T;
}

void Creatlist(BinaryTreeNode*T,listNode*&L)//利用先序遍历递归，用链表L把结点串起来
{

    if (T != NULL) {
        if (T->left == NULL&&T->right == NULL) //如果左右子树为空，则为叶子结点
        {
            listNode *temp = new listNode;  //串起来
            temp->data = T->value;
            L->next = temp;
            L = L->next;    

        }
        Creatlist(T->left,L);     //递归左子树
        Creatlist(T->right,L);    //递归右子树
    }
    L->next = NULL;
}
int main()
{
    //ABD##E##CF##G##
    // A
    // B C
    // D E F G 
    BinaryTreeNode * A;
    A = CreateTree();
    listNode *first = L;//first作为L的首地址
    Creatlist(A,L);
    first = first->next;
    for (; first!=NULL&&first->next!=NULL;)
    {
        if (first == NULL)
            break;
        cout << first->data;

        first = first->next;
    }
    return 0;
}

三、设一棵二叉树用二叉链表表示，编写一个算法，判断二叉树是否为完全二叉树

#include<iostream>
#include<stdlib.h>
#include<malloc.h>
#include <stack>
#include <queue>
using namespace std;
enum Tag { L, R };
struct BinaryTreeNode {
    char value;
    BinaryTreeNode *left;
    BinaryTreeNode *right;
};

BinaryTreeNode * CreateBinaryTree()//建树
{
    BinaryTreeNode *T;

    char data;
    cin >> data;

    if (data == '#')
        T = NULL;
    else
    {
        T = new BinaryTreeNode;
        T->value = data;
        T->left = CreateBinaryTree();
        T->right = CreateBinaryTree();
    }
    return T;
}
int CompBTNode(BinaryTreeNode  *b)
{
    queue<BinaryTreeNode*> q;//定义一个队列，用于分层判断
    BinaryTreeNode * p=new BinaryTreeNode;
    int cm = 1;                       //cm=1表示二叉树为完全二叉树
    int bj = 1;                       //bj=1表示到目前为止所有结点均有左右孩子
    if (b != NULL)
    {
        q.push(b);
        while (!q.empty())        
        {
            p = q.front();
            q.pop();
            if (p->left == NULL)   //*p结点没有左孩子
            {
                bj = 0;
                if (p->right != NULL)//没有左孩子但有右孩子，不满足完全二叉树性质
                    cm = 0;
            }
            else                    //*p结点有左孩子
            {
                if (bj == 1)         //结点均有左孩子
                {
                    //左孩子进队
                    q.push(p->left);
                    if (p->right == NULL)//*p有左孩子但没有右孩子,则 bj=0
                        bj = 0;
                    else            //*p有右孩子,则继续判断
                    {
                        q.push(p->right); //右孩子进队
                    }
                }
                else                //bj=0: 迄今为止,已有结点缺左或右孩子
                    cm = 0;         //此时*p结点有左孩子
            }
        }  
        return cm;
    }
    return  1;
}
int main()
{
    BinaryTreeNode *T = NULL;
    //A B C # # # D # #
    T = CreateBinaryTree();
    if (CompBTNode(T))
        cout << "Yes";
    else
        cout << "NO";
    return 0;
}

四、统计二叉树的宽度

int maxx = 0;//存储最大结点个数
int wid[100] = { 0 };//存储每一层结点个数
int getwidth(BinaryTreeNode*T)//递归计算二叉树宽度
{

    int static floor = 1;
    if (T != NULL)
    {
        if (floor == 1) //当是根结点的时候
        {
            wid[floor]++;
            floor++;
            if (T->left)wid[floor]++; //存在左子树，数组的值加1
            if (T->right)wid[floor]++; //存在右子树，数组的值加1
        }
        else
        {
            floor++;
            if (T->left)wid[floor]++; //存在左子树，数组的值加1
            if (T->right)wid[floor]++; //存在右子树，数组的值加1
        }
        if (wid[floor] > maxx) //如果大于maxx，替换maxx的值
            maxx = wid[floor];
        maxx=getwidth(T->left); 
        floor--;     //访问过要减一
        maxx=getwidth(T->right);
    }
        return maxx;
}

五、以前序次序输出一棵二叉树所有结点的数据值及结点所在层次

//ABD##E##CF##G##
    // A
    // B C
    // D E F G 
int nfloor = 1;
void getnode(BinaryTreeNode*T)
{
    if (T != NULL)
    {   
        cout << T->value<<" ";
        cout << nfloor << endl;
        nfloor++;
        getnode(T->left);  //递归搜索左子树
        getnode(T->right);//递归搜索右子树
        nfloor--;
    }
}