BiTreeOrder.rar_BiTreeOrder_创建二叉树

#include <iostream> #include <stack> using namespace std; const int MAX = 200; typedef struct BiTnode { char data; struct BiTnode *lchild,*rchild; }BiTnode,*BiTree; class BinaryTree { public: BinaryTree() { root = NULL; } ~BinaryTree() { Destroy(root); } void CreateBiTree() { CreateBiTree(root); } void PreOrder() //递归------先序遍历 { PreOrder(root); } void InOrder() //递归------中序遍历 { InOrder(root); } void PostOrder() //递归------后序遍历 { PostOrder(root); } void LevelOrder() { LevelOrder(root); } void PreOrderTraverse() //非递归------先序遍历 { PreOrderTraverse(root); } void InOrderTraverse() //非递归------中序遍历 { InOrderTraverse(root); } void PostOrderTraverse() //非递归------后序遍历 { PostOrderTraverse(root); } private: BiTree root; stack<BiTree> s; void CreateBiTree(BiTree &); void PreOrder(BiTree); void InOrder(BiTree); void PostOrder(BiTree); void LevelOrder(BiTree); void PreOrderTraverse(BiTree); void InOrderTraverse(BiTree); void PostOrderTraverse(BiTree); void Destroy(BiTree &); }; void BinaryTree::CreateBiTree(BiTree &root)//建立二叉树 { char ch; if((ch=getchar()) == '#') root = NULL; else { root=new BiTnode; root->data = ch; root->lchild = NULL; root->rchild = NULL; CreateBiTree(root->lchild); CreateBiTree(root->rchild); } } void BinaryTree::PreOrder(BiTree root)//先序遍历 { if(root!=NULL) { cout << root->data << ' '; PreOrder(root->lchild); PreOrder(root->rchild); } } void BinaryTree::InOrder(BiTree root)//中序遍历 { if(root!=NULL) { InOrder(root->lchild); cout << root->data << ' '; InOrder(root->rchild); } } void BinaryTree::PostOrder(BiTree root)//后序遍历 { if(root!=NULL) { PostOrder(root->lchild); PostOrder(root->rchild); cout << root->data << ' '; } } void BinaryTree::LevelOrder(BiTree root)//层序遍历 { BiTree Q[MAX],p; int front=0,rear=0; if(root!=NULL) { Q[rear] = root; rear = (rear+1)%MAX; } while(front != rear) { p = Q[front]; front = (front+1)%MAX; cout << p->data << ' '; if(p->lchild!=NULL) { Q[rear] = p->lchild; rear = (rear+1)%MAX; } if(p->rchild!=NULL) { Q[rear] = p->rchild; rear = (rear+1)%MAX; } } } void BinaryTree::PreOrderTraverse(BiTree root) { BiTree p; p = root; while(p != NULL || !s.empty()) { if(p != NULL) { s.push(p); cout << p->data << ' '; p = p->lchild; } else { p = s.top(); s.pop(); p = p->rchild; } } } void BinaryTree::InOrderTraverse(BiTree root) { BiTree p; p = root; while(p != NULL || !s.empty()) { if(p != NULL) { s.push(p); p = p->lchild; } else { p = s.top(); s.pop(); cout << p->data << ' '; p = p->rchild; } } } void BinaryTree::PostOrderTraverse(BiTree root) { BiTree p,q; p = root; while(p != NULL || !s.empty()) { if(p != NULL) { s.push(p); p = p->lchild; } else { p = s.top(); if(p->rchild != NULL && p->rchild != q) { p = p->rchild; s.push(p); p = p->lchild; } else { s.pop(); cout << p->data << ' '; q = p; p = NULL; } } } } void BinaryTree::Destroy(BiTree &root)//删除二叉树所有结点 { if(root!=NULL) { Destroy(root->lchild); Destroy(root->rchild); delete root; root = NULL; } } int main() { BinaryTree btree; cout << "建立二叉树:" << endl; cout << "请输入二叉树的先序遍历序列," << endl; cout << "空节点用#表示,最大" << MAX << "字符!" << endl; btree.CreateBiTree(); cout << "先序遍历输出: "; btree.PreOrder(); cout << endl; cout << "先序非递归遍历输出:"; btree.PreOrderTraverse(); cout << endl; cout << "中序遍历输出: "; btree.InOrder(); cout << endl; cout << "中序非递归遍历输出:"; btree.InOrderTraverse(); cout << endl; cout << "后序遍历输出: "; btree.PostOrder(); cout << endl; cout << "后序非递归遍历输出:"; btree.PostOrderTraverse(); cout << endl; cout << "层次遍历输出:"; btree.LevelOrder(); cout << endl; return 0; }