title: 二叉树操作三道题（分享）
author: Codemon
date: 2022-11-12 09:06:11
tags:
二叉树操作三道题
A.二叉树左右孩子交换Time Limit: 1000 MSMemory Limit: 32768 KTotal Submit: 116 (57 users)Total Accepted: 55 (52 users)Special Judge: NoDescription根据输入利用二叉链表创建二叉树，并将所有结点的左右孩子交换，并输出。说明：输入的第一行为根结点;第二行以后每行的第二元为第一元的左孩子，第三元为第一元的右孩子, 0表示空；其中#为输入结束标记。输出时按结点层次顺序输出。Sample InputAA B CB 0 DC 0 ED 0 0E 0 0#Sample OutputA C BC E 0B D 0E 0 0D 0 0Hint输出有换行符
#include
#include
#include
#include
#include
using namespace std;
typedef struct node
{
char val;
struct node* left;
struct node* right;
} node;
#define ALLOC_(name, xx) \
node * name = (node*)malloc(sizeof(node)); \
name->val = xx; \
name->left = name->right = NULL;
void buildTree(node*& t)
{
char a, b, c;
cin >> a;
if (a == '#')
return;
map<char, node*> mp;
ALLOC_(root, a);
mp[root->val] = root;
while (cin >> a)
{
if (a == '#')
break;
cin >> b >> c;
auto parent = mp.find(a);
if (b != '0') {
auto left = mp.find(b);
if (left == mp.end())
{
ALLOC_(p, b);
mp[p->val] = p;
left = mp.find(p->val);
}
parent->second->left = left->second;
}
if (c != '0') {
auto right = mp.find(c);
if (right == mp.end())
{
ALLOC_(p, c);
mp[p->val] = p;
right = mp.find(p->val);
}
parent->second->right = right->second;
}
}
t = root;
return;
}
void Swap(node*& T1, node*& T2)
{
node* t = T1;
T1 = T2;
T2 = t;
}
void NodeSwap(node*& T)
{
if (T != NULL)
{
if (T->left != NULL && T->right != NULL)
{
Swap(T->left, T->right);
}
else if (T->left != NULL && T->right == NULL)
{
T->right = T->left;
T->left = NULL;
}
else if (T->left == NULL && T->right != NULL)
{
T->left = T->right;
T->right = NULL;
}
else
{
;
}
NodeSwap(T->left);
NodeSwap(T->right);
}
else
{
;
}
}
void FloorPrint_QUEUE(node*& Tree)
{
queue <node*> q;
if (Tree != NULL)
{
q.push(Tree);
}
while (q.empty() == false)
{
cout << q.front()->val << " ";
if (q.front()->left != NULL)
{
q.push(q.front()->left);
cout << q.front()->left->val<<" ";
}
else {
cout << "0" << " ";
}
if (q.front()->right != NULL)
{
q.push(q.front()->right);
cout << q.front()->right->val << endl;
}
else {
cout << "0" << endl;
}
q.pop();
}
}
int main() {
node* T;
buildTree(T);
NodeSwap(T);
FloorPrint_QUEUE(T);
return 0;
}
B.计算二叉树高度Time Limit: 1000 MSMemory Limit: 32768 KTotal Submit: 89 (52 users)Total Accepted: 50 (49 users)Special Judge: NoDescription根据输入利用二叉链表创建二叉树，并输出二叉树的高度。说明：输入的第一行为根结点;第二行以后每行的第二元为第一元的左孩子，第三元为第一元的右孩子, 0表示空；其中#为输入结束标记。InputOutputSample InputAA B DB 0 CD 0 0C E 0E 0 FF 0 0#Sample Output5
#include
#include
#include
#include
using namespace std;
typedef struct node
{
char val;
struct node* left;
struct node* right;
} node;
#define ALLOC_(name, xx) \
node * name = (node*)malloc(sizeof(node)); \
name->val = xx; \
name->left = name->right = NULL;
void buildTree(node*& t)
{
char a, b, c;
cin >> a;
if (a == '#')
return;
map<char, node*> mp;
ALLOC_(root, a);
mp[root->val] = root;
while (cin >> a)
{
if (a == '#')
break;
cin >> b >> c;
auto parent = mp.find(a);
if (b != '0') {
auto left = mp.find(b);
if (left == mp.end())
{
ALLOC_(p, b);
mp[p->val] = p;
left = mp.find(p->val);
}
parent->second->left = left->second;
}
if (c != '0') {
auto right = mp.find(c);
if (right == mp.end())
{
ALLOC_(p, c);
mp[p->val] = p;
right = mp.find(p->val);
}
parent->second->right = right->second;
}
}
t = root;
return;
}
int GetHeight(node* BT) {
int h1;
int h2;
if (!BT)
return 0;
else {
h1 = GetHeight(BT->left);
h2 = GetHeight(BT->right);
return h1 > h2 ? ++h1 : ++h2;
}
}
int main() {
node* T;
buildTree(T);
cout << GetHeight(T) << endl;
return 0;
}
C.计算二叉树叶子结点数Time Limit: 1000 MSMemory Limit: 32768 KTotal Submit: 213 (57 users)Total Accepted: 64 (54 users)Special Judge: NoDescriptionInputSample InputA B C 0 D 0 E #Sample Output2
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
using namespace std;
#define len1 sizeof(BiTNode)
#define len2 sizeof(queue)
typedef char ElemType;
typedef struct BiTNode {
ElemType data;
struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
typedef struct SqQueue {
BiTree p;
struct SqQueue* pnext;
}SqQueue, * queue;
void createTree(BiTree& T)
{
ElemType x;
BiTree tree = NULL;
BiTree pnew = NULL;
queue phead = NULL, ptail = NULL, listnew = NULL, pcur = NULL;
int temp;
do
{
scanf("%c", &x);
if (x == '#')break;
temp = getchar();
pnew = (BiTree)calloc(1, len1);
pnew->data = x;
listnew = (queue)calloc(1, len2);
listnew->p = pnew;
if (tree == NULL)
{
tree = pnew;
phead = listnew;
ptail = listnew;
pcur = listnew;
continue;
}
else
{
ptail->pnext = listnew;
ptail = listnew;
}
if (pcur->p->lchild == NULL )
{
pcur->p->lchild = pnew;
}
else if (pcur->p->rchild == NULL )
{
pcur->p->rchild = pnew;
pcur = pcur->pnext;
}
} while (1);
T = tree;
}
int getLeafNum(BiTree root)
{
if (NULL == root || root->data == '0')
{
return 0;
}
if ((NULL == root->lchild || root->lchild->data == '0') && (NULL == root->rchild|| root->rchild->data == '0'))
{
return 1;
}
int leftLeafNum = getLeafNum(root->lchild);
int rightLeafNum = getLeafNum(root->rchild);
int leafNum = leftLeafNum + rightLeafNum;
return leafNum;
}
int main() {
BiTree T;
createTree(T);
int s;
s = getLeafNum(T);
cout << s << endl;
return 0;
}
Original: https://blog.csdn.net/qq_51000584/article/details/127817211
Author: 敲代码的A梦
Title: 二叉树操作题
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/654740/
转载文章受原作者版权保护。转载请注明原作者出处！