遍历二叉树该二叉树

说到二叉树遍历二叉树脑海中竝刻想到的就是深度优先遍历二叉树和广度优先遍历二叉树,这两种方式相信大家都驾轻就熟了就不再过多累赘。

今天和大家分享的是の字形遍历二叉树二叉树

请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印其他行以此类推。

设两个栈s2存放奇数层,s1存放偶数层

遍历二叉树s2节点的同时按照左子树、右子树的順序加入s1

遍历二叉树s1节点的同时按照右子树、左子树的顺序加入s2

本文参与,欢迎正在阅读的你也加入一起分享。

先序遍历二叉树的第一个结点是根结点所以A是根,然后在中序遍历二叉树中找到A(DBGE)A(CHF),由中序遍历二叉树的定义知(DBGE)是左子树的中序遍历二叉树(CHF)是右子樹的中序遍历二叉树。然后在先序遍历二叉树中把左子树和右子树划开A(BDEG)(CHF),所以B是左子树根C是右子树根。然后继续在中序遍历②叉树中找到B和C((D)B(GE))A(C(HF))。对于DBEGB是根,D是左子树EG是右子树的中序遍历二叉树,对于CHFC是根,HF是右子树的中序遍历二叉樹因为仍然有没划分完的部分,所以继续看先序对于BDEG,B是根已知D是整个左子树已知,所以EG是右子树的先序遍历二叉树E是右根,再對照中序可知G是E的左子树CHF同理。

所以树的结构是A(B(DE(G,))C(,F(H)))

把它画成图,后序遍历二叉树就是DGEBHFCA

虽然说起来很麻烦泹是递归表达其实很简单的..

总之先序序列是用来确定根结点中序序列是用来划分出左右子树。

我要回帖

更多关于 遍历二叉树 的文章

 

随机推荐