SWUSTOJ #977 统计利用先序遍历创建的二叉树中的空链域个数

SWUSTOJ #977 统计利用先序遍历创建的二叉树中的空链域个数

  • 题目
    • 输入
    • 输出
    • 样例输入
    • 样例输出
  • 源代码

题目

利用先序递归遍历算法创建二叉树并计算该二叉树中的空链域个数。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符"#“时表示该结点不需要创建，否则创建该结点。最后再统计创建完成的二叉树中的空链域个数。需要注意输入数据序列中的”#“字符和非”#"字符的序列及个数关系，这会最终决定创建的二叉树的形态。

输入

输入为接受键盘输入的由大写英文字符和"#"字符构成的一个字符串（用于创建对应的二叉树）。

输出

输出该用例对应的二叉树中的空链域个数。

样例输入

A##
ABC####
AB##C##
ABCD###EF##G###
A##B##
#A

样例输出

2
4
4
8
2
1

源代码

#include<iostream>
#include<queue>using namespace std;int i = 0;
int Count = 0;
class binarytree;
class TreeNode
{friend class binarytree;
public:void getleft(TreeNode * p){leftnode = p;}void getright(TreeNode *p){rightnode = p;}TreeNode(char a) { data = a; leftnode = NULL; rightnode = NULL; };char data;TreeNode *leftnode;TreeNode *rightnode;
};
class binarytree
{
public:void getroot(TreeNode* p){root = p;}void leveloder();											//后序遍历void leveloder(TreeNode* current);void preinsert(TreeNode* &current, char* arr);TreeNode * root;
};
void binarytree::leveloder()
{if (root)leveloder(root);
}
void binarytree::leveloder(TreeNode* current)
{if (current->leftnode == NULL&&current->rightnode == NULL)Count += 2;else if (current->leftnode == NULL || current->rightnode == NULL)Count++;if(current->leftnode) leveloder(current->leftnode);if(current->rightnode) leveloder(current->rightnode);
}
void binarytree::preinsert(TreeNode* &current, char* arr)		//注意这里的是引用地址
{if (arr[i] == '#'){current = NULL;i++;}else{current = new TreeNode(arr[i]);i++;preinsert(current->leftnode, arr);preinsert(current->rightnode, arr);}
}int main()
{binarytree Tree;char arr[1000];cin >> arr;Tree.preinsert(Tree.root, arr);Tree.leveloder();cout<<Count;return 0;
}

SWUSTOJ #977 统计利用先序遍历创建的二叉树中的空链域个数

SWUSTOJ #977 统计利用先序遍历创建的二叉树中的空链域个数

  • 题目
    • 输入
    • 输出
    • 样例输入
    • 样例输出
  • 源代码

题目

利用先序递归遍历算法创建二叉树并计算该二叉树中的空链域个数。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符"#“时表示该结点不需要创建，否则创建该结点。最后再统计创建完成的二叉树中的空链域个数。需要注意输入数据序列中的”#“字符和非”#"字符的序列及个数关系，这会最终决定创建的二叉树的形态。

输入

输入为接受键盘输入的由大写英文字符和"#"字符构成的一个字符串（用于创建对应的二叉树）。

输出

输出该用例对应的二叉树中的空链域个数。

样例输入

A##
ABC####
AB##C##
ABCD###EF##G###
A##B##
#A

样例输出

2
4
4
8
2
1

源代码

#include<iostream>
#include<queue>using namespace std;int i = 0;
int Count = 0;
class binarytree;
class TreeNode
{friend class binarytree;
public:void getleft(TreeNode * p){leftnode = p;}void getright(TreeNode *p){rightnode = p;}TreeNode(char a) { data = a; leftnode = NULL; rightnode = NULL; };char data;TreeNode *leftnode;TreeNode *rightnode;
};
class binarytree
{
public:void getroot(TreeNode* p){root = p;}void leveloder();											//后序遍历void leveloder(TreeNode* current);void preinsert(TreeNode* &current, char* arr);TreeNode * root;
};
void binarytree::leveloder()
{if (root)leveloder(root);
}
void binarytree::leveloder(TreeNode* current)
{if (current->leftnode == NULL&&current->rightnode == NULL)Count += 2;else if (current->leftnode == NULL || current->rightnode == NULL)Count++;if(current->leftnode) leveloder(current->leftnode);if(current->rightnode) leveloder(current->rightnode);
}
void binarytree::preinsert(TreeNode* &current, char* arr)		//注意这里的是引用地址
{if (arr[i] == '#'){current = NULL;i++;}else{current = new TreeNode(arr[i]);i++;preinsert(current->leftnode, arr);preinsert(current->rightnode, arr);}
}int main()
{binarytree Tree;char arr[1000];cin >> arr;Tree.preinsert(Tree.root, arr);Tree.leveloder();cout<<Count;return 0;
}