//二叉树 #include<iostream> #include<stack> #include<queue> using namespace std; //二叉树结点 typedef struct BiTNode{ char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //按先序序列创建二叉树 int CreateBiTree(BiTree &T){ char data; //‘#’表示空树 cin>>data; if(data == '#'){ T = NULL; } else{ T = (BiTree)malloc(sizeof(BiTNode)); T->data = data; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return 0; } //输出 void Visit(BiTree T){ if(T->data != '#'){ printf("%c ",T->data); } } //先序遍历 void PreOrder(BiTree T){ if(T != NULL){ //访问根节点 Visit(T); //访问左子结点 PreOrder(T->lchild); //访问右子结点 PreOrder(T->rchild); } } //中序遍历 void InOrder(BiTree T){ if(T != NULL){ //访问左子结点 InOrder(T->lchild); //访问根节点 Visit(T); //访问右子结点 InOrder(T->rchild); } } //后序遍历 void PostOrder(BiTree T){ if(T != NULL){ //访问左子结点 PostOrder(T->lchild); //访问右子结点 PostOrder(T->rchild); //访问根节点 Visit(T); } } //树的高度 int BinTreeDepth(BiTree t) { int h,h1,h2; if(t == NULL) return 0; else { h1 = BinTreeDepth(t->lchild); h2 = BinTreeDepth(t->rchild); h = max(h1,h2) + 1; return h; } } //求二叉树中节点的最大距离 void Find_Dis(BiTree t) { } //释放树空间 void DestroyBinTree(BiTree t) { if(t==NULL) return; DestroyBinTree(t->lchild); DestroyBinTree(t->rchild); t->lchild=NULL; t->rchild=NULL; free(t); } //先序遍历(非递归) //思路：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。 void PreOrder2(BiTree T){ stack<BiTree> stack; //p是遍历指针 BiTree p = T; //栈不空或者p不空时循环 while(p || !stack.empty()){ if(p != NULL){ //存入栈中 stack.push(p); //访问根节点 printf("%c ",p->data); //遍历左子树 p = p->lchild; } else{ //退栈 p = stack.top(); stack.pop(); //访问右子树 p = p->rchild; } }//while } //中序遍历(非递归) //思路：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。先将T入栈，遍历左子树； //遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。 void InOrder2(BiTree T){ stack<BiTree> stack; //p是遍历指针 BiTree p = T; //栈不空或者p不空时循环 while(p || !stack.empty()){ if(p != NULL){ //存入栈中 stack.push(p); //遍历左子树 p = p->lchild; } else{ //退栈，访问根节点 p = stack.top(); printf("%c ",p->data); stack.pop(); //访问右子树 p = p->rchild; } }//while } //后序遍历(非递归) typedef struct BiTNodePost{ BiTree biTree; char tag; }BiTNodePost,*BiTreePost; //后序遍历 void PostOrder2(BiTree T){ stack<BiTreePost> stack; //p是遍历指针 BiTree p = T; BiTreePost BT; //栈不空或者p不空时循环 while(p != NULL || !stack.empty()){ //遍历左子树 while(p != NULL){ BT = (BiTreePost)malloc(sizeof(BiTNodePost)); BT->biTree = p; //访问过左子树 BT->tag = 'L'; stack.push(BT); p = p->lchild; } //左右子树访问完毕访问根节点 while(!stack.empty() && (stack.top())->tag == 'R'){ BT = stack.top(); //退栈 stack.pop(); BT->biTree; printf("%c ",BT->biTree->data); } //遍历右子树 if(!stack.empty()){ BT = stack.top(); //访问过右子树 BT->tag = 'R'; p = BT->biTree; p = p->rchild; } }//while } //层次遍历 void LevelOrder(BiTree T){ BiTree p = T; //队列 queue<BiTree> queue; //根节点入队 queue.push(p); //队列不空循环 while(!queue.empty()){ //对头元素出队 p = queue.front(); //访问p指向的结点 printf("%c ",p->data); //退出队列 queue.pop(); //左子树不空，将左子树入队 if(p->lchild != NULL){ queue.push(p->lchild); } //右子树不空，将右子树入队 if(p->rchild != NULL){ queue.push(p->rchild); } } } int main() { BiTree T; cout<<"输入二叉树"<<endl; CreateBiTree(T); printf("先序遍历： "); PreOrder(T); printf(" "); printf("先序遍历(非递归)： "); PreOrder2(T); printf(" "); printf("中序遍历： "); InOrder(T); printf(" "); printf("中序遍历(非递归)： "); InOrder2(T); printf(" "); printf("后序遍历： "); PostOrder(T); printf(" "); printf("后序遍历(非递归)： "); PostOrder2(T); printf(" "); printf("层次遍历： "); LevelOrder(T); printf(" "); cout<<"树的高度为："<<BinTreeDepth(T)<<endl<<endl; cout <<"释放树空间"<<endl<<endl; DestroyBinTree(T); cout<<"求二叉树中节点的最大距离"<<endl; //cout<<Find_Dis(T)<<endl; system("pause"); return 0; }
TestCase：ABC##DE#G##F###