xybxbh 2015-11-07 14:58 采纳率: 0%
浏览 3909

C++二叉树类的创建与函数实现

编写二叉树类的成员函数,分别实现以下功能:
①交换二叉树中所有节点的左右子树。(将结果输出至文本文件中)
②按层次顺序遍历二叉树:首先访问根节点,然后是它的两个孩子节点,然后是孙子节点,依此类推。(将结果输出至屏幕)
③求二叉树的宽度,即同一层次上最多的节点数。(将结果输出至屏幕)
首先我的程序不对……不知道如何成功创建一个二叉树?
并且将结果输出至文本也求教

 #include<iostream>
#include<stdio.h>
#include<stack>
#include<queue>
using namespace std;
struct binaryTreeNode{
    int element;
    binaryTreeNode *leftChild, *rightChild;
};
class binaryTree{
public:
    binaryTreeNode *root;
    binaryTree(){
        root = NULL;
    }
    binaryTreeNode* createBinaryTree();
    void preOrder(binaryTreeNode *);                  
    void inOrder(binaryTreeNode *);                   
    void postOrder(binaryTreeNode *);                 
    void swapChild(binaryTreeNode**);
    void leverOrder(binaryTreeNode*);
    void display(){
        leverOrder(root);
        cout << endl;
    }
    int widthOfTheTree(binaryTreeNode*);
};

binaryTreeNode* binaryTree::createBinaryTree()
{
    binaryTreeNode* current = 0;
    int val = 0;
    cin >> val; 
    if (val == -1)
        return NULL;
    else
    {
        current = new binaryTreeNode;
        current->element = val;
        current->leftChild = createBinaryTree();
        current->rightChild = createBinaryTree();
        return current;
    }

}
void binaryTree::preOrder(binaryTreeNode *temp){
    if (temp != NULL)
    {
        cout << temp->element << " ";
        preOrder(temp->leftChild);
        preOrder(temp->rightChild);
    }
}
void binaryTree::inOrder(binaryTreeNode *temp){
    if (temp != NULL)
    {
        inOrder(temp->leftChild);
        cout << temp->element << " ";
        inOrder(temp->rightChild);
    }
}
void binaryTree::postOrder(binaryTreeNode *temp){     
    if (temp != NULL)
    {
        postOrder(temp->leftChild);
        postOrder(temp->rightChild);
        cout << temp->element << " ";
    }
}
void binaryTree::swapChild(binaryTreeNode**p){
    binaryTreeNode*temp;
    if ((*p)){
        temp = (*p)->leftChild;
        (*p)->leftChild = (*p)->rightChild;
        (*p)->rightChild = temp;
        swapChild(&((*p)->leftChild));
        swapChild(&((*p)->rightChild));
    }
}
void binaryTree::leverOrder(binaryTreeNode*t)
{
    queue<binaryTreeNode*> q;
    if (t != NULL)
        q.push(t);
    binaryTreeNode *b;
    while (!q.empty())
    {
        b = q.front();
        cout << b->element << ' ';
        q.pop();
        if (b->leftChild)
            q.push(b->leftChild);
        if (b->rightChild)
            q.push(b->rightChild);
    }
}
int binaryTree::widthOfTheTree(binaryTreeNode*p)
{
    if (p == NULL)
        return 0;
    queue<binaryTreeNode*> q;
    q.push(p);
    int width = 1;
    int curwidth = 1;
    int nextwidth = 0;
    while (!q.empty())
    {
        while (curwidth != 0)
        {
            binaryTreeNode *temp = q.front();
            q.pop();
            curwidth--;
            if (temp->leftChild != NULL)
            {
                q.push(temp->leftChild);
                nextwidth++;
            }
            if (temp->rightChild != NULL)
            {
                q.push(temp->rightChild);
                nextwidth++;
            }
        }
        if (nextwidth>width)
            width = nextwidth;
        curwidth = nextwidth;
        nextwidth = 0;
    }
    return width;
    cout << "width=" << width << endl;
}

void main()
{
    binaryTree a;
    a.createBinaryTree();
    a.widthOfTheTree(a.root); 
    a.display();
}
  • 写回答

1条回答 默认 最新

  • 普通网友 2015-11-08 03:44
    关注

    #include
    #include
    #include

    typedef struct BITTREE
    {
    int data;
    struct BITTREE *lchild, *rchild;
    }BitTree;

    BitTree CreateBitTree()
    {
    BitTree *root = NULL;
    int temp;
    if (scanf_s("%d", &temp))
    {
    root = (BitTree
    )malloc(sizeof(BitTree));
    root->data = temp;
    getchar();
    printf("请输入%d的左孩子:",temp);
    root->lchild = CreateBitTree();
    getchar();
    printf("请输入%d的右孩子:", temp);
    root->rchild = CreateBitTree();
    }
    return root;
    }
    //遍历
    `void print(BitTree *root)
    {
    if (root)
    {
    print(root->lchild);
    printf("%d ", root->data);
    print(root->rchild);

    }
    }
    void cc(BitTree *root)//层次遍历
    {
    queue q;
    BitTree *temp = NULL;
    if (root)
    q.push(root);
    while (!q.empty())
    {
    temp = q.front();
    q.pop();
    printf("%d ",temp->data);
    if (temp->lchild)
    q.push(temp->lchild);
    if (temp->rchild)
    q.push(temp->rchild);
    }
    }
    int GetDeep(BitTree *root)
    {
    int x, y;
    if (root == NULL)
    return 0;
    x = GetDeep(root->lchild);
    y = GetDeep(root->rchild);
    return x > y ? x + 1 : y + 1;
    }
    void jx(BitTree *root)//求树的镜像
    {
    BitTree *temp = NULL;
    if (root != NULL)
    {
    jx(root->lchild);
    jx(root->rchild);
    temp = root->lchild;
    root->lchild = root->rchild;
    root->rchild = temp;
    }
    }
    typedef struct TREE
    {
    int data;
    struct TREE *Firstcshild,*NextBother;
    }Tree;//孩子兄弟表示法
    int GetTreeDeep(Tree *root)
    {
    int max = 0,x;
    Tree *p = NULL;
    if (root == NULL)
    return 0;
    for (p = root->Firstchild; p != NULL; p = p->NextBother)
    {
    x = GetTreeDeep(p);
    if (max < x)
    max = x;
    }
    return max + 1;
    }

    void main()
    {
    BitTree *root=CreateBitTree();
    print(root);
    puts("");
    jx(root);
    print(root);
    puts("");
    }

    这是我当初学c的时候写的,你可以参考一下,要换的话就是把结构体换成类就可以了,没有什么难度。。。

    评论

报告相同问题?

悬赏问题

  • ¥15 矩阵加法的规则是两个矩阵中对应位置的数的绝对值进行加和
  • ¥15 活动选择题。最多可以参加几个项目?
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能
  • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
  • ¥50 NT4.0系统 STOP:0X0000007B
  • ¥15 想问一下stata17中这段代码哪里有问题呀