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