遍历序列构造二叉树

1.由先序序列和中序序列可以唯一地确定一棵二叉树

1)先序序列第一个结点一定是根节点。
2)中序序列以根节点分割成两个序列,前一个序列树左子树的中序序列,后一个是右子树的中序序列。
3)在先序序列中找到这两个子序列,用1)2)方法递归下去,即可确定二叉树

2.由后序序列和中序序列可以唯一地确定一棵二叉树

1)后序序列最后一个结点一定是根结点。
2)中序序列以根节点分割成两个序列,前一个序列树左子树的中序序列,后一个是右子树的中序序列。
3)在后序序列中找到这两个子序列,用1)2)方法递归下去,即可确定二叉树

3.由层序序列和中序序列可以唯一地确定一棵二叉树

1)层序序列第一个结点一定是根结点。
2)由孩子结点最多两个,中序序列以根节点分割成两个序列,如果可以分成两个,则下一层结点就是层序序列的下两个结点。(一个就是层序下一个结点)
3)再以这两个结点为根节点递归操作。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容