二叉树分别以数组存储方式创建、以先序遍历序列创建。输入二叉树的数组存储、先序遍历结果,判断根据它们创建的二叉树是否是同一棵二叉树。
测试次数t
每组测试数据两行:
第一行:二叉树的数组存储(英文字母表示树结点,#表示空树)
第二行:二叉树的先序遍历结果(英文字母表示树结点,#表示空树)
对每组测试数据,如果两种方式创建的是同一棵二叉树,输出YES,否则,输出NO。
#include<iostream> #include<string> #include<queue> 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, Tree; BiTreeNode* CreateBiTree(); void Compare();//内部Compare函数 public: BiTree() {}; ~BiTree() {}; void CreateTree(string TreeArray); void Input(string _Tree);//数组存储二叉树输出 }; void BiTree::CreateTree(string TreeArray) {//函数用于创建二叉树并于数组存储进行比较 pos = 0; strTree.assign(TreeArray); Root = CreateBiTree(); Compare(); } BiTreeNode* BiTree::CreateBiTree() { BiTreeNode* T; char ch; ch = strTree[pos++]; while(ch){ if (ch == '#'){ T = new BiTreeNode(); T->data='#'; T->leftChild=NULL; T->RightChild=NULL; } else { T = new BiTreeNode(); T->data = ch; T->leftChild = CreateBiTree(); T->RightChild = CreateBiTree(); } return T; } } void BiTree::Compare(){ int i = 0; BiTreeNode* p; queue<BiTreeNode*> Q; Q.push(Root); while (i < Tree.length()) { p = Q.front(); Q.pop(); if (p) { if (p->data != Tree[i]) { cout << "NO" << endl; return;//不匹配则结束函数 } Q.push(p->leftChild);//左子树入队 Q.push(p->RightChild);//右子树入队 }i++; } cout << "YES" << endl;//循环完则说明匹配 } void BiTree::Input(string _Tree) { Tree = _Tree; } int main() { int t, i; cin >> t; for (i = 0; i < t; i++) { string s1, s2; cin >> s1 >> s2; BiTree* T = new BiTree(); T->Input(s1); T->CreateTree(s2); } return 0; }