是的,是已知前序遍历和中序遍历,建立二叉树具体应该怎么办呢

2024-12-18 02:35:08
推荐回答(2个)
回答1:

= =可以采用二分法。
比如说先序遍历是ABDCEF
中序遍历是DBAECF
因为先序是中左右,所以先序遍历第一个必定是根节点,所以根节点是A
因为中序遍历是左中右,所以中序遍历的根节点的左子树必然在根节点前面,右子树必然在后面,也就是说 DB是A的左子树,ECF是右子树。这样就先建立A,然后开始二分。
以左右分别为一种情况,左子树先序是DB,中序是BD,所以B是D的左孩子,然后另一边也是一样,就可以得出C是A的右孩子,然后再以C二分。得出C的左孩子是E,右孩子是F,所以后续遍历就是DBEFCA.
无论如何复杂的二叉树都是用这种方法、

回答2:

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

所以树的结构是A(B(D,E(G,)),C(,F(H,)))
把它画成图,后序遍历就是DGEBHFCA

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

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