// 李毛毛 #include<iostream> #include<cstdlib> #include<stack> #include<queue> using namespace std; typedef struct BinTreeNode { char data; struct BinTreeNode *leftChild; struct BinTreeNode *rightChild; }*myTree; //函数申明 void CreateBinTree(myTree tree); //二叉树递归遍历 void preorderTraversal(myTree tree); //（中左右） void inorderTraversal(myTree tree); //（左中右） void orderTraversal(myTree tree); //（右中左） //二叉树的栈（非递归）遍历 void PreOrder_NoRecurve1(myTree p); //先序遍历 void InOrder_NoRecurve(myTree p); //中序遍历 void PostOrder_NoRecurve(myTree p); //后序遍历 //二叉树的队列（非递归）遍历 void LevelOrder(myTree p); int main() { cout<<"请输入你要创建的二叉树（以#结束）:"; myTree root = NULL; CreateBinTree(root); return 0; } //使用广义表创建二叉树函数,这里以“字符”创建二叉树,以'#'字符代表结束 void CreateBinTree(myTree root) { stack<myTree> s; int k; //k是处理左、右子树的标记 myTree p,t; //p用来记住当前创建的节点，t用来记住栈顶的元素 char ch; cin>>ch; while(ch != '#') { switch(ch) { case '(': //对(做处理 s.push(p); k=1; break; case ')': //对)做处理 s.pop(); break; case ',': //对,做处理 k=2; break; default: p = (myTree)malloc(sizeof(BinTreeNode)); //构造一个结点 p->leftChild = NULL; p->rightChild = NULL; if (root == NULL) //如果头节点是空 { root = p; p->data = ch; } else if (k == 1) //链入*t的左孩子 { t = s.top(); t->leftChild = p; p->data = ch; } else //链入*t的右孩子 { t = s.top(); t->rightChild = p; p->data = ch; } } cin>>ch; } cout<<endl<<"采用递归遍历二叉树"<<endl; cout<<"使用中左右输出："; preorderTraversal(root); cout<<endl; cout<<"使用左中右输出："; inorderTraversal(root); cout<<endl; cout<<"使用左右中输出："; orderTraversal(root); cout<<endl<<endl<<"采用栈遍历二叉树："<<endl; cout<<"使用先序输出："; PreOrder_NoRecurve1(root); cout<<endl; cout<<"使用中序输出: "; InOrder_NoRecurve(root); cout<<endl; cout<<"使用后序输出："; PostOrder_NoRecurve(root); cout<<endl; cout<<endl<<"采用层次遍历（队列）二叉树：" <<endl; LevelOrder(root); cout<<endl; } /*myTree constructABinaryTree() { //创建一个二叉树 myTree root = (myTree)malloc(sizeof(BinTreeNode)); root->data = 5; root->leftChild = NULL; root->leftChild = NULL; myTree leftChild = (myTree)malloc(sizeof(BinTreeNode)); leftChild->data = 7; leftChild->leftChild = NULL; leftChild->rightChild = NULL; root->leftChild = leftChild; myTree rightChild = (myTree)malloc(sizeof(BinTreeNode)); rightChild->data = 6; rightChild->leftChild = NULL; rightChild->rightChild = NULL; root->rightChild = rightChild; myTree twoLeftChild = (myTree)malloc(sizeof(BinTreeNode)); twoLeftChild->data = 4; twoLeftChild->leftChild = NULL; twoLeftChild->rightChild = NULL; leftChild->leftChild = twoLeftChild; myTree leftRightChild = (myTree)malloc(sizeof(BinTreeNode)); leftRightChild->data = 3; leftRightChild->leftChild = NULL; leftRightChild->rightChild = NULL; leftChild->rightChild = leftRightChild; return root; }*/ void preorderTraversal(myTree tree) { cout << tree->data << " "; if (tree->leftChild != NULL) preorderTraversal(tree->leftChild); if (tree->rightChild != NULL)preorderTraversal(tree->rightChild); //中左右 } void inorderTraversal(myTree tree) { if (tree->leftChild != NULL) inorderTraversal(tree->leftChild); //左中右 cout << tree->data << " "; if (tree->rightChild != NULL)inorderTraversal(tree->rightChild); } void orderTraversal(myTree tree) //左右中、 { if (tree->leftChild != NULL) orderTraversal(tree->leftChild); if (tree->rightChild != NULL)orderTraversal(tree->rightChild); cout << tree->data<<" "; } void PreOrder_NoRecurve1(myTree p) //先序遍历 { stack<myTree> s; s.push(NULL); /*最先push一个NULL，到最后一个结点没有左右子树时， 栈里只有一个NULL了，令指针p指向这个NULL，再判断就会结束循环*/ while (p!=NULL) { cout << p->data << " "; if(p->rightChild!=NULL) //预留右子树指针在栈中 { s.push(p->rightChild); } if (p->leftChild!=NULL) //进左子树 { p = p->leftChild; } else //左子树为空 { p = s.top(); s.pop(); } } } void InOrder_NoRecurve(myTree p) //中序遍历 { stack<myTree> s; do { while (p!=NULL) { s.push(p); p = p->leftChild; } if (!s.empty()) { p = s.top(); s.pop(); cout << p->data << " "; p = p->rightChild; } } while (p!=NULL||!s.empty()); } void PostOrder_NoRecurve(myTree p) //后序遍历 { if (p == NULL) return ; stack<myTree> s; s.push(p); myTree lastPop = NULL; while (!s.empty()) { while (s.top()->leftChild != NULL) s.push(s.top()->leftChild); while (!s.empty()) { //右叶子结点 || 没有右结点 if (lastPop == s.top()->rightChild || s.top()->rightChild == NULL) { cout << s.top()->data << " "; lastPop = s.top(); s.pop(); } else if (s.top()->rightChild != NULL) { s.push(s.top()->rightChild); break; } } } } void LevelOrder(myTree p) //队列层次遍历 { queue<myTree> Q; Q.push(p); //根节点进队 myTree t; while (!Q.empty()) { t = Q.front(); //t先记住队头,再将队头出队 Q.pop(); cout << t->data << " "; //访问队头元素的数据 if (t->leftChild != NULL) { Q.push(t->leftChild); } if (t->rightChild != NULL) { Q.push(t->rightChild); } } }
