DS之遍历二叉树,ds历二叉树
在二叉树的一些应用中,常常要求在树中查找具有某种特征的结点,或者对树中全部结点逐一进行某种处理。这就提出了一个遍历二叉树的问题,即如何按某条搜索路径巡访树中的每个结点,使得每个结点均被访问一次,而且仅被访问一次。
由二叉树的递归定义可知,二叉树是由三个基本单元构成的:根结点,左子树和右子树。若能依次遍历这三部分,便是遍历了整个二叉树。若限定先左后右的顺序,则遍历二叉树通常有三种算法:先序,中序,后序。
先序遍历二叉树的操作定义为:
若二叉树为空,则空操作;否则;
(1)访问根结点;(2)先序遍历左子树;(3)先序遍历右子树。
中序遍历二叉树的操作定义为:
若二叉树为空,则空操作;否则;
(1)中序遍历左子树;(2)访问根结点;(3)中序遍历右子树。
后序遍历二叉树的操作定义为:若二叉树为空,则空操作;否则;
(1)后序遍历左子树;(2)后序遍历右子树;(3)访问根结点。
对于二叉树的遍历我们在二叉树的二叉链表上实现。在二叉树的二叉链表的基本操作中也介绍了四种遍历方法,我们就来实现前三种遍历方法。在遍历函数的参数中除了一个指针参数外,还有一个指向函数的指针参数。这个函数最简单的实现为Visit()函数。这个函数最简单的代码为:
Status printElement(TElemType e)//最简单的Visit()函数 { cout<<e<<","; return OK; }
再者就是需要构建二叉表(先序输入数据元素)的代码:
Status CreateBiTree(BiTree &T)//按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树,构造二叉链表表示的二叉树T { int i=0; char a[100]; cin>>a[i]; if(a[i]=='#') T=NULL; else { if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) { exit(OVERFLOW); } T->data=a[i];//生成根结点 CreateBiTree(T->lchild); //构造左子树 CreateBiTree(T->rchild); //构造右子树 } return OK; }
先来看看二叉链表的先序遍历代码:
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))//先序遍历二叉树 { if(T) { if(Visit(T->data)) { if(PreOrderTraverse(T->lchild,Visit)) { if(PreOrderTraverse(T->rchild,Visit)) { return OK; } } return ERROR; } } else { return OK; } }
再来看二叉链表的中序遍历代码:
Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))//中序遍历二叉树 { if(T) { if(InOrderTraverse(T->lchild,Visit)) { if(Visit(T->data)) { if(InOrderTraverse(T->rchild,Visit)) { return OK; } } return ERROR; } } else { return OK; } }
最后来看二叉链表的后序遍历代码:
Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e))//后序遍历二叉树 { if(T) { if(PostOrderTraverse(T->lchild,Visit)) { if(PostOrderTraverse(T->rchild,Visit)) { if(Visit(T->data)) { return OK; } } return ERROR; } } else { return OK; } }
完整的代码为:
#include <iostream> #include <Cstdlib> using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef char TElemType; typedef int Status; typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; //左右孩子指针 }BiTNode,*BiTree; Status CreateBiTree(BiTree &T)//按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树,构造二叉链表表示的二叉树T { int i=0; char a[100]; cin>>a[i]; if(a[i]=='#') T=NULL; else { if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) { exit(OVERFLOW); } T->data=a[i];//生成根结点 CreateBiTree(T->lchild); //构造左子树 CreateBiTree(T->rchild); //构造右子树 } return OK; } Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))//先序遍历二叉树 { if(T) { if(Visit(T->data)) { if(PreOrderTraverse(T->lchild,Visit)) { if(PreOrderTraverse(T->rchild,Visit)) { return OK; } } return ERROR; } } else { return OK; } } Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))//中序遍历二叉树 { if(T) { if(InOrderTraverse(T->lchild,Visit)) { if(Visit(T->data)) { if(InOrderTraverse(T->rchild,Visit)) { return OK; } } return ERROR; } } else { return OK; } } Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e))//后序遍历二叉树 { if(T) { if(PostOrderTraverse(T->lchild,Visit)) { if(PostOrderTraverse(T->rchild,Visit)) { if(Visit(T->data)) { return OK; } } return ERROR; } } else { return OK; } } Status printElement(TElemType e)//最简单的Visit()函数 { cout<<e<<","; return OK; } int main() { BiTree T;//构建二叉树 CreateBiTree(T);//先序输入二叉树的数据元素 cout<<"先序遍历二叉树的输出:"; PreOrderTraverse(T,printElement); cout<<endl; cout<<"中序遍历二叉树的输出:"; InOrderTraverse(T,printElement); cout<<endl; cout<<"后序遍历二叉树的输出:"; PostOrderTraverse(T,printElement); cout<<endl; return 0; }
输入的数据:先序输入ABC##DE#G##F###(#代表空)
这棵树的图为:
输出的结果为: