已知二叉树的先序遍历序列和中序遍历序列,输出其后序遍历序列和层次序遍历序列。void postOrder( int root ) { //以root为根节点的二叉树(子树)的 - 后序字符串序列首指
时间: 2024-06-01 13:08:39 浏览: 10
针为root的后序遍历序列
if( root != -1 ) {
postOrder( left[root] ); //左子树
postOrder( right[root] ); //右子树
printf( "%d ", root ); //根节点
}
}
void levelOrder( int root ) { //层次遍历
queue<int> q;
q.push( root );
while( !q.empty() ) {
int now = q.front();
q.pop();
printf( "%d ", now );
if( left[now] != -1 ) q.push( left[now] );
if( right[now] != -1 ) q.push( right[now] );
}
}
相关问题
已知二叉树的先序遍历序列和中序遍历序列,输出其后序遍历序列和层次序遍历序列
可以通过先序遍历序列和中序遍历序列重建二叉树,然后对重建后的二叉树进行后序遍历和层次遍历即可。
具体步骤如下:
1. 根据先序遍历序列确定根结点。
2. 在中序遍历序列中找到根结点所在位置,根结点左边的序列是左子树的中序遍历序列,右边的序列是右子树的中序遍历序列。
3. 通过左子树的中序遍历序列长度确定先序遍历序列中左子树的先序遍历序列,右子树的先序遍历序列为剩余部分。
4. 递归处理左子树和右子树,重建二叉树。
5. 对重建后的二叉树进行后序遍历和层次遍历。
下面是 Python 代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
inorderIndex = inorder.index(preorder[0])
leftInorder = inorder[:inorderIndex]
rightInorder = inorder[inorderIndex+1:]
leftPreorder = preorder[1:len(leftInorder)+1]
rightPreorder = preorder[len(leftInorder)+1:]
root.left = buildTree(leftPreorder, leftInorder)
root.right = buildTree(rightPreorder, rightInorder)
return root
def postorderTraversal(root):
if not root:
return []
stack = [root]
res = []
while stack:
node = stack.pop()
res.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return res[::-1]
def levelOrder(root):
if not root:
return []
queue = [root]
res = []
while queue:
level = []
for i in range(len(queue)):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = buildTree(preorder, inorder)
print(postorderTraversal(root)) # 输出后序遍历序列 [4, 5, 2, 6, 7, 3, 1]
print(levelOrder(root)) # 输出层次遍历序列 [[1], [2, 3], [4, 5, 6, 7]]
```
已知二叉树的先序遍历序列和中序遍历序列,使用C++输出其层次序遍历序列
可以使用递归的方式构建二叉树,并利用队列实现层次遍历。以下是示例代码:
```c++
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return NULL;
}
int rootVal = preorder[preStart];
int rootIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
int leftSize = rootIndex - inStart;
TreeNode* root = new TreeNode(rootVal);
root->left = buildTree(preorder, inorder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1);
root->right = buildTree(preorder, inorder, preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd);
return root;
}
void levelOrder(TreeNode* root) {
if (root == NULL) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* curr = q.front();
q.pop();
cout << curr->val << " ";
if (curr->left != NULL) {
q.push(curr->left);
}
if (curr->right != NULL) {
q.push(curr->right);
}
}
}
}
int main() {
vector<int> preorder = { 3, 9, 20, 15, 7 };
vector<int> inorder = { 9, 3, 15, 20, 7 };
TreeNode* root = buildTree(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
levelOrder(root); // 输出 3 9 20 15 7
return 0;
}
```