C++ 遍历二叉树实例详解

2叉数又叫红黑树，关于2叉数的遍历问题，有很多，一般有三种常用遍历方法：

(1)前序遍历(2)中序遍历(3)后续遍历

以下是经典示例：

#include "stdafx.h" #include<stdio.h> #include<malloc.h> #include <math.h > #define MaxSize 20 typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; }BiTNode,*BiTree; //建立二叉树 void CreateBiTree(BiTree *T) { char ch; scanf("%c",&ch); getchar(); if(ch==' ') { printf("不产生子树。\n"); *T=NULL; } else { if(!(*T=(BiTNode *)malloc(sizeof(BiTNode)))) { printf("分配空间失败"); return; }//生成一个新节点 (*T)->data = ch; printf("产生左右子树。\n"); CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } } //递归前序遍历 void Preorder(BiTNode *T) { if(T) { printf("%c ",T->data); Preorder(T->lchild); Preorder(T->rchild); } } //递归中序遍历 void Inorder(BiTNode *T) { if(T) { Inorder(T->lchild); printf("%c ",T->data); Inorder(T->rchild); } } //递归后序遍历 void Postorder(BiTNode *T) { if(T) { Postorder(T->lchild); Postorder(T->rchild); printf("%c ",T->data); } } //非递归前序遍历 void NPreorder(BiTNode *T) { BiTNode *stack[MaxSize],*p; int top=-1; if(T) { top++; stack[top]=T; //根节点进栈 while(top>-1) //栈不为空时循环 { p=stack[top]; //退栈并访问该节点 top--; printf("%c ",p->data); if(p->rchild) //右孩子进栈 { top++; stack[top]=p->rchild; } if(p->lchild) //左孩子进栈 { top++; stack[top]=p->lchild; } } } } //非递归中序遍历 void NInorder(BiTNode *T) { BiTNode *stack[MaxSize],*p; int top=-1; p=T; while(p||top!=-1) { if(p) { top++; stack[top]=p; p=p->lchild; } //根节点进栈，遍历左子树 else //根节点退栈，访问根节点，遍历右子树 { p=stack[top]; top--; printf("%c ",p->data); p=p->rchild; } } } //非递归后序遍历 void NPostorder(BiTNode *T) { BiTNode *stack[MaxSize],*p; int flag,top=-1; do { while(T) { top++; stack[top]=T; T=T->lchild; } //所有左节点进栈 p=NULL; //p总是指向当前节点的前一个已经访问过的节点 flag=1; //flag为1表示当前节点已经访问过了 while(top!=-1 && flag) { T=stack[top]; if(T->rchild==p) //右子树不存在或者已经被访问过时 { printf("%c ",T->data); top--; p=T; //调整p指针 } else { T=T->rchild; flag=0; //调整访问标志 } } } while(top!=-1); } //层次遍历二叉树 void Translever(BiTNode *T) { struct node { BiTNode *vec[MaxSize]; int f,r; //r为队尾，f为队头 }queue; BiTNode *p; p=T; queue.f=0; queue.r=0; if(T) printf("%c ", p->data); queue.vec[queue.r]=p; queue.r=queue.r+1; while(queue.f<queue.r) { p=queue.vec[queue.f]; queue.f=queue.f+1; if(p->lchild) { printf("%c ",p->lchild->data); queue.vec[queue.r]=p->lchild; queue.r=queue.r+1; } if(p->rchild) { printf("%c ",p->rchild->data); queue.vec[queue.r]=p->rchild; queue.r=queue.r+1; } } printf("\n"); } //求二叉树的深度 int Depth(BiTNode *T) { int dep1,dep2; if(T==NULL) return(0); else { dep1=Depth(T->lchild); dep2=Depth(T->rchild); if(dep1>dep2) return(dep1+1); else return(dep2+1); } } //输出二叉树 void Disptree(BiTNode *T) { if(T) { printf("%c",T->data); if(T->lchild || T->rchild) { printf("("); Disptree(T->lchild); if(T->rchild) printf(","); Disptree(T->rchild); printf(")"); } } }

main.cpp

void main() { BiTree T=NULL; char j; int sign = 1; printf("本程序可以进行建立二叉树、递归与非递归先序、中序、后序遍历二叉树、层次遍历二叉树、输出二叉树的扩展序列的操作。\n"); printf("请将二叉树的先序序列输入以建立二叉树，叶子节点用空格代替。\n"); printf("您必须一个一个地输入字符。\n"); while(sign) { printf("请选择: \n"); printf("0.生成二叉树 1.求二叉树的深度\n"); printf("2.递归先序遍历 3.非递归先序遍历\n"); printf("4.递归中序遍历 5.非递归中序遍历\n"); printf("6.递归后序遍历 7.非递归后序遍历\n"); printf("8.层次遍历 9.输出二叉树的广义表形式\n"); printf("q.退出程序\n"); scanf("%c",&j); getchar(); switch(j) { case '0': printf("生成二叉树:"); CreateBiTree(&T); printf("\n"); printf("\n"); break; case '1': if(T) { printf("此二叉树的深度为:"); printf("%d",Depth(T)); printf("\n"); printf("\n"); } else printf("二叉树为空!\n"); break; case '2': if(T) { printf("递归先序遍历二叉树:"); Preorder(T); printf("\n"); printf("\n"); } else printf("二叉树为空!\n"); break; case '3': if(T) { printf("非递归先序遍历二叉树:"); NPreorder(T); printf("\n"); printf("\n"); } else printf("二叉树为空!\n"); break; case '4': if(T) { printf("递归中序遍历二叉树:"); Inorder(T); printf("\n"); printf("\n"); } else printf("二叉树为空!\n"); break; case '5': if(T) { printf("非递归中序遍历二叉树:"); NInorder(T); printf("\n"); printf("\n"); } else printf("二叉树为空!\n"); break; case '6': if(T) { printf("递归后序遍历二叉树:"); Postorder(T); printf("\n"); printf("\n"); } else printf("二叉树为空!\n"); break; case '7': if(T) { printf("非递归后序遍历二叉树:"); NPostorder(T); printf("\n"); printf("\n"); } else printf("二叉树为空!\n"); break; case '8': if(T) { printf("层次遍历二叉树:"); Translever(T); printf("\n"); printf("\n"); } else printf("二叉树为空!\n"); break; case '9': if(T) { printf("输出二叉树:"); Disptree(T); printf("\n"); printf("\n"); } else printf("二叉树为空!\n"); break; default: sign=0; printf("程序运行结束，按任意键退出!\n"); } } }

示例：

转换成双向链表

先序列：H F C D M I N
中序列：C F D H I M N
后序列：C D F I N M H

#include <iostream> using namespace std; struct BSTreeNode{ char m_val; BSTreeNode *m_pLeft; BSTreeNode *m_pRight; }; BSTreeNode *pHead;//链表显示的头结点 BSTreeNode *pListIndex;//游标指针 void showOrderLiust(BSTreeNode *pCurrent); void createBSTree(BSTreeNode *&pCurrent,char ch) { if (NULL == pCurrent) { pCurrent = new BSTreeNode; pCurrent->m_val = ch; pCurrent->m_pLeft = NULL; pCurrent->m_pRight = NULL; }else { if (pCurrent->m_val > ch) { createBSTree(pCurrent->m_pLeft,ch); }else if (pCurrent->m_val < ch) { createBSTree(pCurrent->m_pRight,ch); } else { return; } } } //遍历二叉树 void PreOrderTraverse(BSTreeNode *pCurrent) { if (NULL == pCurrent) { return; } if (NULL!=pCurrent) { //先遍历根节点 cout<<pCurrent->m_val<<endl; //在遍历左节点 PreOrderTraverse(pCurrent->m_pLeft); //在遍历右节点 PreOrderTraverse(pCurrent->m_pRight); } } //中序遍历 void InOrderTraverse(BSTreeNode *pCurrent) { if (NULL == pCurrent) { return; } if (NULL != pCurrent->m_pLeft) { InOrderTraverse(pCurrent->m_pLeft); } showOrderLiust(pCurrent); //在遍历右节点 if (NULL != pCurrent->m_pRight) { InOrderTraverse(pCurrent->m_pRight); } } //后序遍历 void EndOrderTraverse(BSTreeNode *pCurrent) { if (NULL == pCurrent) { return; } if (NULL != pCurrent->m_pLeft) { EndOrderTraverse(pCurrent->m_pLeft); } cout<<pCurrent->m_val<<endl; //在遍历右节点 if (NULL != pCurrent->m_pRight) { EndOrderTraverse(pCurrent->m_pRight); } } void showOrderLiust(BSTreeNode *pCurrent) { pCurrent->m_pLeft = pListIndex; if (NULL != pListIndex) { pListIndex->m_pRight = pCurrent; }else { pHead = pCurrent; } pListIndex = pCurrent; cout<<pCurrent->m_val<<endl; } int main(int argc,char**argv) { BSTreeNode *pRoot = NULL; pHead = NULL; pListIndex = NULL; createBSTree(pRoot,'H'); createBSTree(pRoot,'F'); createBSTree(pRoot,'C'); createBSTree(pRoot,'D'); createBSTree(pRoot,'M'); createBSTree(pRoot,'I'); createBSTree(pRoot,'N'); PreOrderTraverse(pRoot); InOrderTraverse(pRoot); EndOrderTraverse(pRoot); delete pRoot; return 0; }

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！