海南网站设计公司,音频网站建设,云南网络推广公司,wordpress autop0x01 实验目的
掌握二叉树的基本概念#xff0c;二叉树的存储结构使用链表。
0x02 实验内容
输入一个完全二叉树的层次遍历字符串#xff0c;创建这个二叉树#xff0c;输出这个二叉树的前序遍历字符串、中序遍历字符串、后序遍历字符串、结点数目、二叉树高度(上述每一个…0x01 实验目的
掌握二叉树的基本概念二叉树的存储结构使用链表。
0x02 实验内容
输入一个完全二叉树的层次遍历字符串创建这个二叉树输出这个二叉树的前序遍历字符串、中序遍历字符串、后序遍历字符串、结点数目、二叉树高度(上述每一个结果独立一行显示)。输入二叉树前序序列和中序序列(各元素各不相同)创建这个二叉树输出该二叉树的后序序列、层次遍历。
0x03 实验过程
层次遍历
判断队列是否为空的条件必须加上因为队列为空时有可能会通过q.front()获取到一些非NULL的奇怪的东西然后获取其element时会报错。
void levelOrder(binaryTreeNodeE* node) {queuebinaryTreeNodeE* q;while (node ! NULL) {if(Level 0) {Level;coutnode-element;if(node-leftChild ! NULL) q.push(node-leftChild);if(node-rightChild ! NULL) q.push(node-rightChild);if(!q.empty()) {node q.front();q.pop();}else node NULL; } else {cout,node-element;if(node-leftChild ! NULL) q.push(node-leftChild);if(node-rightChild ! NULL) q.push(node-rightChild);if(!q.empty()) {node q.front();q.pop();}else node NULL; }}}层次遍历构建二叉树
先将第一个节点放入队列之后树上每添加一个节点就要将该节点入队列。先进先出的进行添加节点操作直到node数组空了。
template class E
binaryTreeNodeE* constructTreeByLevelOrder(binaryTreeNodeE node[],int num) {queuebinaryTreeNodeE* q;q.push(node[0]);int i 1;while(i num) {binaryTreeNodeE* current q.front();q.pop();if(i num) {current-leftChild node[i];q.push(node[i]);}i;if(i num) {current-rightChild node[i];q.push(node[i]);}i;}return node[0];
}前序遍历和中序遍历构建二叉树
采用递归地形式依次构建左子树和右子树。利用前序遍历的的第一个节点是头节点以及在中序遍历中头结点的两侧分别为左子树和右子树这两个性质。
templateclass E
binaryTreeNodeE* create(binaryTreeNodeE preorder[], int p, int q, binaryTreeNodeE inorder[], int i, int j) {if (p q) return nullptr;if (p q) return preorder[p];int k i;// 找到根节点在中序遍历序列中的位置while (preorder[p].element ! inorder[k].element) k;preorder[p].leftChild create(preorder, p1, pk, inorder, i, k-1);preorder[p].rightChild create(preorder, pk1, q, inorder, k1, j);return preorder[p];
}改BUG 0x04 实验源码
#includebits/stdc.h
using namespace std;
int in 0;
int post 0;
int Level 0;
templateclass T
class binaryTreeNode {public:T element;binaryTreeNodeT *leftChild,*rightChild;binaryTreeNode() {leftChild rightChild NULL;}binaryTreeNode(const T theElement) : element(theElement) {leftChild rightChild NULL;}binaryTreeNode(const T theElement, binaryTreeNode *theLeftChild, binaryTreeNode *theRightChild):element(theElement) {leftChild theLeftChild;rightChild theRightChild;}
};
templateclass E
class linkedBinaryTree {public:linkedBinaryTree() {root NULL;treeSize 0;}bool empty() const {return treeSize 0;}int size() const {return treeSize;}void setSize(int size) {treeSize size;}void preOrder(binaryTreeNodeE* node,int level) {if(node ! NULL) {if(level 0) {coutnode-element;preOrder(node-leftChild, level);preOrder(node-rightChild, level);} else {cout,node-element;preOrder(node-leftChild, level);preOrder(node-rightChild, level);}}}void inOrder(binaryTreeNodeE* node) {if(node ! NULL) {if(node-leftChild NULL in 0) {coutnode-element;in;} else {inOrder(node-leftChild);cout,node-element;inOrder(node-rightChild);}}}void postOrder(binaryTreeNodeE* node) {if(node ! NULL) {if(node-leftChild NULL post 0) {coutnode-element;post;} else {postOrder(node-leftChild);postOrder(node-rightChild);cout,node-element;}}}void levelOrder(binaryTreeNodeE* node) {queuebinaryTreeNodeE* q;while (node ! NULL) {if(Level 0) {Level;coutnode-element;if(node-leftChild ! NULL) q.push(node-leftChild);if(node-rightChild ! NULL) q.push(node-rightChild);if(!q.empty()) {node q.front();q.pop();}else node NULL; } else {cout,node-element;if(node-leftChild ! NULL) q.push(node-leftChild);if(node-rightChild ! NULL) q.push(node-rightChild);if(!q.empty()) {node q.front();q.pop();}else node NULL; }}}int getHeight(binaryTreeNodeE* node) {if(node NULL) return 0;int h1 getHeight(node-leftChild);int h2 getHeight(node-rightChild);if(h1 h2) {return h1;} else {return h2;}}private:binaryTreeNodeE *root;int treeSize;
};
template class E
binaryTreeNodeE* constructTreeByLevelOrder(binaryTreeNodeE node[],int num) {queuebinaryTreeNodeE* q;q.push(node[0]);int i 1;while(i num) {
// coutq.front()q.front()endl;
// coutq.front()q.front()endl;
// coutnode[0]node[0]endl;
// coutnode[0]nodeendl;binaryTreeNodeE* current q.front();q.pop();if(i num) {current-leftChild node[i];
// coutcurrent-leftChild-elementendl;
// coutnode[0].leftChild-elementendl;q.push(node[i]);}i;if(i num) {current-rightChild node[i];q.push(node[i]);}i;}return node[0];
}
templateclass E
binaryTreeNodeE* create(binaryTreeNodeE preorder[], int p, int q, binaryTreeNodeE inorder[], int i, int j) {if (p q) return nullptr;if (p q) return preorder[p];int k i;// 找到根节点在中序遍历序列中的位置while (preorder[p].element ! inorder[k].element) k;preorder[p].leftChild create(preorder, p1, pk, inorder, i, k-1);preorder[p].rightChild create(preorder, pk1, q, inorder, k1, j);return preorder[p];
}
int main() {//两种写法都可以。//binaryTreeNodechar *node new binaryTreeNodechar[100];binaryTreeNodechar node[100];string s;coutInput1endl;cins;for(int i 0; i s.length(); i) {binaryTreeNodechar n(s.at(i));node[i] n;}linkedBinaryTreechar tree;constructTreeByLevelOrder(node,s.length());tree.setSize(s.length());
// node[0].leftChild node[1];
// node[0].rightChild node[2];
// coutpreOrderendl;
// 记录层数方便输出逗号int level 0;coutOutput1endl;
// coutnode[0].elementendl;
// coutnode[0].leftChildendl;tree.preOrder(node[0],level);coutendl;tree.inOrder(node[0]);in 0;coutendl;tree.postOrder(node[0]);post 0;coutendl;couttree.size()endl;couttree.getHeight(node[0])endl;// tree.constructTreeByLevelOrder(node,length);
// tree.inOrder();
// cout2node[0].elementnode[0].leftChild-element;coutInput2endl;string s1,s2;cins1s2;binaryTreeNodechar node1[100];binaryTreeNodechar node2[100];for(int i 0; i s1.length(); i) {binaryTreeNodechar n(s1.at(i));node1[i] n;}int noting;for(int i 0; i s2.length(); i) {binaryTreeNodechar n(s2.at(i));node2[i] n;if(s2.at(i) s1.at(0)) noting i;}//constructTreeByPreOrderAndInOrder(node1, node2, s1.length(), s2.length(), noting);coutOutput2endl;create(node1, 0, s1.length()-1, node2, 0, s2.length()-1);
// tree.preOrder(node1[0],level);
// coutendl;
// tree.inOrder(node1[0]);
// coutendl;tree.postOrder(node1[0]);coutendl;tree.levelOrder(node1[0]);coutendl;coutEndendl;return 0;
}0x05 错误代码
#includebits/stdc.h
using namespace std;
int in 0;
int post 0;
int Level 0;
templateclass T
class binaryTreeNode {public:T element;binaryTreeNodeT *leftChild,*rightChild;binaryTreeNode() {leftChild rightChild NULL;}binaryTreeNode(const T theElement) : element(theElement) {leftChild rightChild NULL;}binaryTreeNode(const T theElement, binaryTreeNode *theLeftChild, binaryTreeNode *theRightChild):element(theElement) {leftChild theLeftChild;rightChild theRightChild;}
};
templateclass E
class linkedBinaryTree {public:linkedBinaryTree() {root NULL;treeSize 0;}bool empty() const {return treeSize 0;}int size() const {return treeSize;}void setSize(int size) {treeSize size;}void preOrder(binaryTreeNodeE* node,int level) {if(node ! NULL) {if(level 0) {coutnode-element;preOrder(node-leftChild, level);preOrder(node-rightChild, level);} else {cout,node-element;preOrder(node-leftChild, level);preOrder(node-rightChild, level);}}}void inOrder(binaryTreeNodeE* node) {if(node ! NULL) {if(node-leftChild NULL in 0) {coutnode-element;in;} else {inOrder(node-leftChild);cout,node-element;inOrder(node-rightChild);}}}void postOrder(binaryTreeNodeE* node) {if(node ! NULL) {if(node-leftChild NULL post 0) {coutnode-element;post;} else {postOrder(node-leftChild);postOrder(node-rightChild);cout,node-element;}}}void levelOrder(binaryTreeNodeE* node) {queuebinaryTreeNodeE* q;while (node ! NULL) {if(Level 0) {Level;coutnode-element;if(node-leftChild ! NULL) q.push(node-leftChild);if(node-rightChild ! NULL) q.push(node-rightChild);node q.front();q.pop();} else {cout,node-element;if(node-leftChild ! NULL) q.push(node-leftChild);if(node-rightChild ! NULL) q.push(node-rightChild);node q.front();q.pop();}}}int getHeight(binaryTreeNodeE* node) {if(node NULL) return 0;int h1 getHeight(node-leftChild);int h2 getHeight(node-rightChild);if(h1 h2) {return h1;} else {return h2;}}private:binaryTreeNodeE *root;int treeSize;
};
template class E
binaryTreeNodeE* constructTreeByLevelOrder(binaryTreeNodeE node[],int num) {queuebinaryTreeNodeE* q;q.push(node[0]);int i 1;while(i num) {
// coutq.front()q.front()endl;
// coutq.front()q.front()endl;
// coutnode[0]node[0]endl;
// coutnode[0]nodeendl;binaryTreeNodeE* current q.front();q.pop();if(i num) {current-leftChild node[i];
// coutcurrent-leftChild-elementendl;
// coutnode[0].leftChild-elementendl;q.push(node[i]);}i;if(i num) {current-rightChild node[i];q.push(node[i]);}i;}return node[0];
}
template class E
//左子树的实现
binaryTreeNodeE* soul(int noting, binaryTreeNodeE node1[], binaryTreeNodeE node2[]) {int index1 100;int index2 100;for(int i 1; i noting; i) {for(int j noting; j 0; j--) {if(node1[i].element node2[j].element) {index1 index2;index2 j;coutindex1index1endl;coutindex2index2endl;}}if(index1 index2) {node1[i-1].leftChild node1[i];} else {
// coutYesendl;for(int j noting; j 0; j--) {if(node1[i].element node2[j].element) {for(int k noting; k 0; k--) {if(node2[j-1].element node1[k].element) {node1[k].rightChild node1[i];}}}}}}return node1[0];
}
template class E
binaryTreeNodeE* constructTreeByPreOrderAndInOrder(binaryTreeNodeE node1[], binaryTreeNodeE node2[], int num1, int num2, int noting) {soul(noting, node1, node2);int temp;//获取下一个左子树区间 for(int i noting 1; i num1; i) {if(node2[i].element node1[noting1].element) {temp noting;noting i;}}do {//重复操作直到剩下最后一个元素或者不剩下元素退出循环 int num 0;binaryTreeNodechar node3[100];binaryTreeNodechar node4[100];for(int i temp 1; i noting; i) {node3[num] node1[i];node4[num] node2[i];num;}soul(noting, node3, node4);for(int i noting 1; i num1; i) {if(node2[i].element node1[noting1].element) {temp noting;noting i;}}} while(noting 1 ! num1 - 1 noting 1 ! num1);//如果剩一个元素 if(noting 1 num1 - 1) node2[num1 - 1].rightChild node2[num1];return node1[0];
}
int main() {//binaryTreeNodechar *node new binaryTreeNodechar[100];binaryTreeNodechar node[100];string s;coutInputendl;cins;for(int i 0; i s.length(); i) {binaryTreeNodechar n(s.at(i));node[i] n;}linkedBinaryTreechar tree;constructTreeByLevelOrder(node,s.length());tree.setSize(s.length());
// node[0].leftChild node[1];
// node[0].rightChild node[2];
// coutpreOrderendl;
// 记录层数方便输出逗号int level 0;coutOutputendl;
// coutnode[0].elementendl;
// coutnode[0].leftChildendl;tree.preOrder(node[0],level);coutendl;tree.inOrder(node[0]);in 0;coutendl;tree.postOrder(node[0]);post 0;coutendl;couttree.size()endl;couttree.getHeight(node[0])endl;// tree.constructTreeByLevelOrder(node,length);
// tree.inOrder();
// cout2node[0].elementnode[0].leftChild-element;coutInput2endl;string s1,s2;cins1s2;binaryTreeNodechar node1[100];binaryTreeNodechar node2[100];for(int i 0; i s1.length(); i) {binaryTreeNodechar n(s1.at(i));node1[i] n;}int noting;for(int i 0; i s2.length(); i) {binaryTreeNodechar n(s2.at(i));node2[i] n;if(s2.at(i) s1.at(0)) noting i;}constructTreeByPreOrderAndInOrder(node1, node2, s1.length(), s2.length(), noting);coutOutput2endl;tree.preOrder(node1[0],level);coutendl;tree.inOrder(node1[0]);coutendl;tree.postOrder(node1[0]);coutendl;tree.levelOrder(node1[0]);coutendl;return 0;
}
