6.3二叉树层序遍历

// 李毛毛 #includeiostream #includecstdlib #includestack #includequeue 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) { stackmyTree s; int k; //k是处理左、右子树的标记 myTree p,t; //p用来记住当前创建的节点t用来记住栈顶的元素 char ch; cinch; while(ch ! #) { switch(ch) { case (: //对(做处理 s.push(p); k1; break; case ): //对)做处理 s.pop(); break; case ,: //对,做处理 k2; 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; } } cinch; } coutendl采用递归遍历二叉树endl; cout使用中左右输出; preorderTraversal(root); coutendl; cout使用左中右输出; inorderTraversal(root); coutendl; cout使用左右中输出; orderTraversal(root); coutendlendl采用栈遍历二叉树endl; cout使用先序输出; PreOrder_NoRecurve1(root); coutendl; cout使用中序输出: ; InOrder_NoRecurve(root); coutendl; cout使用后序输出; PostOrder_NoRecurve(root); coutendl; coutendl采用层次遍历队列二叉树 endl; LevelOrder(root); coutendl; } /*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) //先序遍历 { stackmyTree 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) //中序遍历 { stackmyTree 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 ; stackmyTree 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) //队列层次遍历 { queuemyTree 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); } } }