摘要
在由遍历序列构造二叉树问题的研究中,针对目前还没有用层次遍历和其它遍历一起构造二叉树的问题,提出了一种由层次遍历和其它遍历一起构造二叉树的新算法。考虑到层次遍历中左子树和右子树的层次遍历不具有递归属性,设计了从层次遍历中分离出左右子树层次遍历的方法,并且通过组合得到具有递归属性的层次遍历。通过对层次遍历和中序遍历的递归属性的研究,设计了由层次遍历和中序遍历构造二叉树的递归算法;通过对层次遍历和先序遍历的递归属性的研究,设计了由层次遍历和中序遍历构造没有出度为1的二叉树的递归算法;通过对层次遍历和后序遍历的递归属性的研究,设计了由层次遍历和后序遍历构造没有出度为1的二叉树的递归算法。仿真结果表明,用设计的算法构造二叉树是有效的,可为二叉树的构造提供新算法。
In the study which uses traversal sequences to construct the binary tree,in view of The fact that it is not used to construct the binary tree by using the level traversal and the other traversal,a new algorithm is put forward to construct the binary tree by using the level traversal and the other traversal. Considering that there is not recursive attribute in the level traversal of the left sub tree and the right sub tree,a method is designed to isolate the left subtree level traversal and the right subtree level traversal from the level traversal,and recursive property is gained through the combination with the two sub level traversals. By the recursive property of the level traversal and the inorder traversal,a recursive algorithm is designed to construct the binary tree by using the level traversal and inorder traversal. Through the research of the recursive attribute between the level traversal and the preorder traversal,a recursive algorithm is designed to construct the binary tree. By the research of the recursive attribute between the level traversal and the postorder traversal,a recursive algorithm is designed to construct the binary tree. The simula-tion results show that the algorithm is effective for constructing the binary tree and can provide a new algorithm for the construction of the binary tree.
出处
《武汉轻工大学学报》
2016年第4期67-72,共6页
Journal of Wuhan Polytechnic University
基金
国家自然科学基金资助项目(61179032)
关键词
层次遍历
先序遍历
中序遍历
后序遍历
递归算法
Level traversal
preorder traversal
inorder traversal
postorder traversal
recursive algorithm
