提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

A. DS二叉树–二叉树构建与遍历（含代码框架）

题目描述

给定一颗二叉树的逻辑结构如下图，（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构，并输出该二叉树的先序遍历、中序遍历和后序遍历结果
在这里插入图片描述
本题目的代码框架参考如下
在这里插入图片描述
三种遍历的代码框架
在这里插入图片描述
主函数如下：
在这里插入图片描述

输入

第一行输入一个整数t，表示有t个二叉树

第二行起输入每个二叉树的先序遍历结果，空树用字符‘0’表示，连续输入t行

输出

输出每个二叉树的先序遍历、中序遍历和后序遍历结果

输入样例1

2
AB0C00D00
AB00C00

输出样例1

ABCD
BCAD
CBDA
ABC
BAC
BCA

代码

#include
#include
using namespace std;
class BiTreeNode{
public:
char data;
BiTreeNode *LeftChild;
BiTreeNode *RightChild;
BiTreeNode():LeftChild(NULL),RightChild(NULL){}
~BiTreeNode(){}
};
class BiTree{
private:
BiTreeNode Root;
int pos;
string strTree;
BiTreeNode CreateBiTree();
void PreOrder(BiTreeNode *t);
void InOrder(BiTreeNode *t);
void PostOrder(BiTreeNode *t);

public:
BiTree(){};
~BiTree(){};
void CreateTree (string TreeArray);
void PreOrder();
void InOrder();
void PostOrder();
};

void BiTree::CreateTree(string TreeArray) {
pos=0;
strTree.assign(TreeArray);
Root=CreateBiTree();
}
BiTreeNode* BiTree::CreateBiTree() {
BiTreeNode *T;
char ch;
ch=strTree[pos++];
if(ch==‘0’)
T=NULL;
else{
T=new BiTreeNode();
T->data=ch;
T->LeftChild=CreateBiTree();
T->RightChild=CreateBiTree();
}
return T;
}

void BiTree::PreOrder() {
PreOrder(Root);
}
void BiTree::PreOrder(BiTreeNode *t) {
if(t!=NULL){
cout<data;
PreOrder(t->LeftChild);
PreOrder(t->RightChild);
}
}
void BiTree::InOrder() {
InOrder(Root);
}
void BiTree::InOrder(BiTreeNode *t) {
if(t!=NULL){
InOrder(t->LeftChild);
cout<data;
InOrder(t->RightChild);
}
}
void BiTree::PostOrder() {
PostOrder(Root);
}
void BiTree::PostOrder(BiTreeNode *t) {
if(t!=NULL){
PostOrder(t->LeftChild);
PostOrder(t->RightChild);
cout<data;
}
}

int main(void){
int t,i;
string str;
cin>>t;
while(t–){
BiTree p;
cin>>str;
p.CreateTree(str);
p.PreOrder();
cout<<endl;
p.InOrder();
cout<<endl;
p.PostOrder();
cout<<endl;
}
return 0;
}

B. DS二叉树–叶子数量

题目描述

计算一颗二叉树包含的叶子结点数量。

提示：叶子是指它的左右孩子为空。

建树方法采用“先序遍历+空树用0表示”的方法，即给定一颗二叉树的先序遍历的结果为AB0C00D00，其中空节点用字符‘0’表示。则该树的逻辑结构如下图。
在这里插入图片描述

输入

第一行输入一个整数t，表示有t个测试数据

第二行起输入二叉树先序遍历的结果，空树用字符‘0’表示，输入t行

输出

逐行输出每个二叉树的包含的叶子数量

输入样例1

3
AB0C00D00
AB00C00
ABC00D00E00

输出样例1

2
2
3

代码

#include<iostream>
#include <string>
using namespace std;
class BiTreeNode{
public:
    char data;
    BiTreeNode *LeftChild;
    BiTreeNode *RightChild;
    BiTreeNode():LeftChild(NULL),RightChild(NULL){}
    ~BiTreeNode(){}
};
class BiTree{
private:
    BiTreeNode *Root;
    int pos;
    int leaves;
    string strTree;
    BiTreeNode* CreateBiTree();
    void PreOrder(BiTreeNode *t);
    void InOrder(BiTreeNode *t);
    void PostOrder(BiTreeNode *t);

public:
    BiTree(){};
    ~BiTree(){};
    void CreateTree (string TreeArray);
    void PreOrder();
    void InOrder();
    void PostOrder();
    int getleaves(){return leaves;}
};

void BiTree::CreateTree(string TreeArray) {
    pos=0;
    leaves=0;
    strTree.assign(TreeArray);
    Root=CreateBiTree();
}
BiTreeNode* BiTree::CreateBiTree() {
    BiTreeNode *T;
    char ch;
    ch=strTree[pos++];
    if(ch=='0')
        T=NULL;
    else{
        T=new BiTreeNode();
        T->data=ch;
        T->LeftChild=CreateBiTree();
        T->RightChild=CreateBiTree();
    }
    return T;
}

void BiTree::PreOrder() {
    PreOrder(Root);
}
void BiTree::PreOrder(BiTreeNode *t) {
  if(t!=NULL){
      if(!t->LeftChild&&!t->RightChild)  leaves++;
      PreOrder(t->LeftChild);
      PreOrder(t->RightChild);
  }
}
void BiTree::InOrder() {
    InOrder(Root);
}
void BiTree::InOrder(BiTreeNode *t) {
    if(t!=NULL){
        InOrder(t->LeftChild);
        cout<<t->data;
        InOrder(t->RightChild);
    }
}
void BiTree::PostOrder() {
    PostOrder(Root);
}
void BiTree::PostOrder(BiTreeNode *t) {
    if(t!=NULL){
        PostOrder(t->LeftChild);
        PostOrder(t->RightChild);
        cout<<t->data;
    }

}

int main(void){
    int t,i;
    string str;
    cin>>t;
    while(t--){
        BiTree p;
        cin>>str;
        p.CreateTree(str);
        p.PreOrder();
        cout<<p.getleaves()<<endl;
    }
    return 0;
}

C. DS二叉树——二叉树之父子结点

题目描述

给定一颗二叉树的逻辑结构如下图，（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构。

编写程序输出该树的所有叶子结点和它们的父亲结点
在这里插入图片描述

输入

第一行输入一个整数t，表示有t个二叉树

第二行起，按照题目表示的输入方法，输入每个二叉树的先序遍历，连续输入t行

输出

第一行按先序遍历，输出第1个示例的叶子节点

第二行输出第1个示例中与叶子相对应的父亲节点

以此类推输出其它示例的结果

样例输入

3
AB0C00D00
AB00C00
ABCD0000EF000

样例输出

C D
B A
B C
A A
D F
C E

代码

#include<iostream>
#include<bits/stdc++.h> 
#include <string>

using namespace std;

class BiTreeNode {
public:
    char data;
    BiTreeNode *LeftChild;
    BiTreeNode *RightChild;

    BiTreeNode() : LeftChild(NULL), RightChild(NULL) {}

    ~BiTreeNode() {}
};

class BiTree {
private:
    BiTreeNode *Root;
    int pos;
    string strTree;

    BiTreeNode *CreateBiTree();

    void PreOrder(BiTreeNode *t);

    void fa(BiTreeNode* father, BiTreeNode *tr) ;

    void InOrder(BiTreeNode *t);

    void PostOrder(BiTreeNode *t);

public:
    BiTree() {};

    ~BiTree() {};

    void CreateTree(string TreeArray);

    void PreOrder();

    void fa() ;

    void InOrder();

    void PostOrder();
};

void BiTree::CreateTree(string TreeArray) {
    pos = 0;
    strTree.assign(TreeArray);
    Root = CreateBiTree();
}

BiTreeNode *BiTree::CreateBiTree() {
    BiTreeNode *T;
    char ch;
    ch = strTree[pos++];
    if (ch == '0')
        T = NULL;
    else {
        T = new BiTreeNode();
        T->data = ch;
        T->LeftChild = CreateBiTree();
        T->RightChild = CreateBiTree();
    }
    return T;
}

void BiTree::PreOrder() {
    PreOrder(Root);
}

void BiTree::fa() {
    fa(Root, Root);
    cout<<endl;
}
void BiTree::fa(BiTreeNode *father, BiTreeNode *tr) {
    if (!tr->LeftChild && !tr->RightChild) {
        cout << father->data << ' ';
        return;
    }
    if (tr->LeftChild) fa(tr, tr->LeftChild);
    if (tr->RightChild) fa(tr, tr->RightChild);
}

void BiTree::PreOrder(BiTreeNode *t) {
    if (t != NULL) {
        PreOrder(t->LeftChild);
        PreOrder(t->RightChild);
    }
}

void BiTree::InOrder() {
    InOrder(Root);
}

void BiTree::InOrder(BiTreeNode *t) {
    if (t != NULL) {
        InOrder(t->LeftChild);
        cout << t->data;
        InOrder(t->RightChild);
    }
}

void BiTree::PostOrder() {
    PostOrder(Root);
}

void BiTree::PostOrder(BiTreeNode *t) {
    if (t != NULL) {
        PostOrder(t->LeftChild);
        PostOrder(t->RightChild);
        if (!t->LeftChild && !t->RightChild) {
            cout << t->data << ' ';
        }
    }
}


int main() {
    int t, i;
    string str;
    cin >> t;
    while (t--) {
        BiTree p;
        cin >> str;
        p.CreateTree(str);
        p.PostOrder();
        cout << endl;
        p.fa();
    }
    return 0;
}

D. DS树–二叉树高度

题目描述

给出一棵二叉树，求它的高度。二叉树的创建采用前面实验的方法。

注意，二叉树的层数是从1开始

输入

第一行输入一个整数t，表示有t个二叉树

第二行起输入每个二叉树的先序遍历结果，空树用字符‘0’表示，连续输入t行

输出

每行输出一个二叉树的高度

样例输入

1
AB0C00D00

样例输出

3

代码

#include<iostream>
#include <string>
using namespace std;

class BiTreeNode {
public:
    char data;
    BiTreeNode *LeftChild;
    BiTreeNode *RightChild;

    BiTreeNode() : LeftChild(NULL), RightChild(NULL) {}

    ~BiTreeNode() {}
};

class BiTree {
private:
    BiTreeNode *Root;
    int pos;

    string strTree;

    BiTreeNode *CreateBiTree();

    int Height(BiTreeNode *t);

public:
    BiTree() {};

    ~BiTree() {};

    void CreateTree(string TreeArray);


    void Height();
};

void BiTree::CreateTree(string TreeArray) {
    pos = 0;
    strTree.assign(TreeArray);
    Root = CreateBiTree();
}

BiTreeNode *BiTree::CreateBiTree() {
    BiTreeNode *T;
    char ch;
    ch = strTree[pos++];
    if (ch == '0')
        T = NULL;
    else {
        T = new BiTreeNode();
        T->data = ch;
        T->LeftChild = CreateBiTree();
        T->RightChild = CreateBiTree();
    }
    return T;
}

void BiTree::Height() {
    cout<<Height(Root)<<endl;
}
int BiTree::Height(BiTreeNode *t) {
    if(t==NULL){
        return 0;
    }
    else {
        int m= Height(t->LeftChild);
        int n= Height(t->RightChild);
        return m>n?m+1:n+1;
    }
}


int main(void) {
    int t, i;
    string str;
    cin >> t;
    while (t--) {
        BiTree p;
        cin >> str;
        p.CreateTree(str);
        p.Height();
    }
    return 0;
}

E. DS二叉树——二叉树之数组存储

题目描述

二叉树可以采用数组的方法进行存储，把数组中的数据依次自上而下,自左至右存储到二叉树结点中，一般二叉树与完全二叉树对比，比完全二叉树缺少的结点就在数组中用0来表示。，如下图所示
在这里插入图片描述
从上图可以看出，右边的是一颗普通的二叉树，当它与左边的完全二叉树对比，发现它比完全二叉树少了第5号结点，所以在数组中用0表示，同样它还少了完全二叉树中的第10、11号结点，所以在数组中也用0表示。

结点存储的数据均为非负整数

输入

第一行输入一个整数t，表示有t个二叉树

第二行起，每行输入一个数组，先输入数组长度，再输入数组内数据，每个数据之间用空格隔开，输入的数据都是非负整数

连续输入t行

输出

每行输出一个示例的先序遍历结果，每个结点之间用空格隔开

输入样例

3
3 1 2 3
5 1 2 3 0 4
13 1 2 3 4 0 5 6 7 8 0 0 9 10

输出样例

1 2 3
1 2 4 3
1 2 4 7 8 3 5 9 10 6

提示

注意从数组位置和二叉树深度、结点位置进行关联，或者父子结点在数组中的位置存在某种管理，例如i, i+1, i/2, i+1/2…或者2i, 2i+1…仔细观察哦

代码

#include <iostream>
#include <string>

using namespace std;

class BiTreeNode {
public:
    int  data;
    BiTreeNode *LeftChild;
    BiTreeNode *RightChild;

    BiTreeNode() : LeftChild(NULL), RightChild(NULL) {}
};

class BiTree {
private:
    BiTreeNode *Root;

    BiTreeNode *CreateBiTree(int a[], int x);

    void PreOrder(BiTreeNode *t);

public:
    BiTree() {}

    ~BiTree() {}

    void PreOrder();

    void CreateTree(int a[], int x);
};

void BiTree::PreOrder() {
    PreOrder(Root);
    cout<<endl;
}

void BiTree::PreOrder(BiTreeNode *t) {
    if (t == NULL) return;
    cout << t->data << ' ';
    PreOrder(t->LeftChild);
    PreOrder(t->RightChild);
}

void BiTree::CreateTree(int a[], int x) {
    Root = CreateBiTree(a, x);
}

BiTreeNode *BiTree::CreateBiTree(int a[], int x) {
    BiTreeNode *T;
    if (a[x] == 0)
        T = NULL;
    else {
        T = new BiTreeNode();
        T->data = a[x];
        T->LeftChild = CreateBiTree(a, 2 * x);
        T->RightChild = CreateBiTree(a, 2 * x + 1);
    }
    return T;
}

int main(void) {
    int t, i, n;
    cin >> t;
    int a[100] = {0};
    while (t--) {
        BiTree p;
        cin >> n;
        for (i = 1; i <= n; i++)
            cin >> a[i];
        p.CreateTree(a, 1);
        p.PreOrder();
    }
    return 0;
}
# 数据结构 # 算法 # c++
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

avatar 开放原子开发者工作坊

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

avatar 开放原子开发者工作坊

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

avatar 开放原子开发者工作坊