最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

全球观热点:二叉树遍历的操作与实现

来源:博客园


(资料图)

先序遍历

先序遍历(递归版)
代码展示
/*先序遍历(递归版)*/Status PreOrderTraverse(BiTree T, Status Visit(TElemType e)) {if (T){Visit(T->data);PreOrderTraverse(T->lchild, Visit);PreOrderTraverse(T->rchild, Visit);}return SUCCESS;}
思路解析

先序遍历,首先判断二叉树T是否为空,若为空则代表二叉树已遍历完成。若非空则代表该结点有值,然后调用Visit方法将结点值打印出来。随后再寻找该结点的左右子结点,再重复上述步骤实现先序遍历。

先序遍历(非递归版)
代码展示
/*先序遍历(非递归版)*/Status PreOrderTraverseStore(BiTree T, Status Visit(TElemType e)) {if (T == nullptr){return ERROR;}BiTree p;LinkStack S;InitStack(S);Push(S, T);//根进栈while (!StackEmpty(S)){while ((GetTop(S, p) && p)) {if (!Visit(p->data)){return ERROR;}Push(S, p->lchild);//左走到尽头}Pop(S, p);//空指针退栈if (!StackEmpty(S))//访问结点{Pop(S, p);Push(S, p->rchild);}}return SUCCESS;}
思路解析

非递归版是采用栈来实现,初始化将原始二叉树赋值给p,然后让其入栈。之后遍历其左子树所有结点,左子树结点遍历完成后,弹出空指针栈顶,开始遍历右子树结点。每遍历一次便将新的头结点二叉树压入栈中。

中序和后序遍历

中序遍历及后序遍历(递归版)
代码展示
/*中序遍历*/Status InOrderTraverse(BiTree T, Status Visit(TElemType e)) {if (T != nullptr){InOrderTraverse(T->lchild, Visit);Visit(T->data);InOrderTraverse(T->rchild, Visit);}return SUCCESS;}
/*后序遍历*/Status PostOrderTraverse(BiTree T, Status Visit(TElemType e)) {if (T != nullptr){PostOrderTraverse(T->lchild, Visit);PostOrderTraverse(T->rchild, Visit);Visit(T->data);}return SUCCESS;}
中序遍历和后序遍历(非递归版)
代码展示
/*中序遍历(非递归)*/Status InOrderTraverseStore(BiTree T, Status Visit(TElemType e)) {if (T == nullptr){return ERROR;}BiTree p;LinkStack S;InitStack(S);Push(S, T);while (!StackEmpty(S)){while (GetTop(S, p) && p) {Push(S, p->lchild);//左子树走到尽头}Pop(S, p);//空指针退栈if (!StackEmpty(S)){Pop(S, p);if (!Visit(p->data))//访问结点{return ERROR;}Push(S, p->rchild);}}return SUCCESS;}
/*后序遍历(非递归版)*/Status PostOrderTraverseStore(BiTree T, Status(*Visit)(TElemType e)) {if (T == nullptr){return ERROR;}BiTree p = T, r = nullptr;LinkStack S;InitStack(S);while (p != nullptr || !StackEmpty(S)){if (p){Push(S, p);p = p->lchild;}else{GetTop(S, p);if (p->rchild && p->rchild != r){p = p->rchild;Push(S, p);p = p->lchild;}else{Pop(S, p);Visit(p->data);r = p;p = nullptr;}}}return SUCCESS;}
思路解析

中序和后序遍历与先序遍历差别不大,只是在与父结点的顺序有关。父结点在最前即为先序遍历,父结点在左右子结点中便是中序遍历,父结点在左右子结点之后便是后序遍历。代码实现类似,使用递归或栈来实现。

层次遍历

代码展示
/*层次遍历*/Status LevelOrderTraverse(BiTree& T) {LinkQueue lq;InitQueue(lq);QElemType q;EnQueue(lq, T);while (QueueEmpty(lq) != SUCCESS)//对列不空,则出队{DeQueue(lq, q);printf("%c ", q->data);if (q->lchild){EnQueue(lq, q->lchild);//若有左孩子,则入队}if (q->rchild){EnQueue(lq, q->rchild);//若有右孩子,则入队}}return SUCCESS;}
思路解析

层次遍历使用队列来进行遍历,首先原始二叉树入队,然后退队,打印结点值。查询该结点是否有左右子结点,若有则入队。循环往复上述步骤,当队列为空时,则层次遍历完成。

关键词: