问题描述

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();
}

解决方案

C++二叉树类实现
二叉树的创建和遍历C++实现

解决方案二：

#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的时候写的，你可以参考一下，要换的话就是把结构体换成类就可以了，没有什么难度。。。