先序序列 1,2,3,4 对应的二叉树有多少种
时间: 2024-03-29 11:39:48 浏览: 27
对于含有 n 个结点的二叉树,它的先序序列的第一个结点是根结点,剩余的 n-1 个结点会被分为左子树和右子树。设左子树和右子树的结点个数分别为 i 和 n-i-1,则左子树的先序序列和右子树的先序序列可以分别看作是含有 i 个结点和 n-i-1 个结点的子问题。
因此,可以得到递归式:
f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-1)*f(0),其中 f(0)=1,f(1)=1
即含有 n 个结点的二叉树的数量为 f(n)。
根据递归式,可以得到先序序列为 1,2,3,4 的二叉树的数量为:
f(4) = f(0)*f(3) + f(1)*f(2) + f(2)*f(1) + f(3)*f(0) = 14
因此,先序序列为 1,2,3,4 的二叉树有 14 种。
相关问题
给定先序序列,按照该序列创建二叉树,并输出它对应的先序序列、中序序列和后序序列。用c语言实现代码。
可以使用递归的方法,每次递归的时候取出先序序列的第一个元素作为当前的根节点,然后根据根节点将中序序列分成左子树和右子树两部分,再递归创建左右子树,最后输出先序、中序和后序序列即可。
下面是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 树的结构体
typedef struct TreeNode {
char val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建二叉树
TreeNode* createTree(char* preorder, char* inorder, int len) {
if (len == 0) return NULL;
// 创建根节点
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = preorder[0];
root->left = NULL;
root->right = NULL;
int i;
// 在中序序列中查找根节点的位置
for (i = 0; i < len; i++) {
if (inorder[i] == preorder[0]) break;
}
// 递归创建左右子树
root->left = createTree(preorder + 1, inorder, i);
root->right = createTree(preorder + i + 1, inorder + i + 1, len - i - 1);
return root;
}
// 先序遍历
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
printf("%c ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;
inorderTraversal(root->left);
printf("%c ", root->val);
inorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%c ", root->val);
}
int main() {
char preorder[] = {'A', 'B', 'D', 'E', 'C', 'F', 'G'};
char inorder[] = {'D', 'B', 'E', 'A', 'F', 'C', 'G'};
int len = sizeof(preorder) / sizeof(char);
TreeNode* root = createTree(preorder, inorder, len);
printf("先序遍历:");
preorderTraversal(root);
printf("\n");
printf("中序遍历:");
inorderTraversal(root);
printf("\n");
printf("后序遍历:");
postorderTraversal(root);
printf("\n");
return 0;
}
```
输出结果为:
```
先序遍历:A B D E C F G
中序遍历:D B E A F C G
后序遍历:D E B F G C A
```
注意:这里假设了先序序列和中序序列中的每个元素都不相同,否则就无法确定根节点在中序序列中的位置了。如果存在相同元素,可以加入一个计数器来记录先序序列中根节点的位置。
给出构造先序序列和层序序列对应的所有二叉树的实现
我们可以通过递归的方式来实现给定先序序列和层序序列构造二叉树的过程。
具体实现步骤如下:
1.定义二叉树结构体
首先,我们需要定义二叉树结构体,包括节点值和左右子节点的指针。
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
```
2.递归构造二叉树
接着,我们可以定义一个递归函数来构造二叉树。该函数的输入参数包括先序序列和层序序列,以及根节点在先序序列中的位置、子树在层序序列中的起始位置和结束位置。
```python
def buildTree(preorder, inorder):
if not preorder:
return None
# 根节点为先序序列的第一个节点
root_val = preorder[0]
root = TreeNode(root_val)
# 划分左右子树
idx = inorder.index(root_val)
left_inorder = inorder[:idx]
right_inorder = inorder[idx+1:]
left_preorder = []
right_preorder = []
# 根据左右子树在中序序列中的位置,划分先序序列
for val in preorder[1:]:
if val in left_inorder:
left_preorder.append(val)
else:
right_preorder.append(val)
# 递归构造左右子树
left_start = 0
left_end = len(left_inorder) - 1
right_start = len(left_inorder)
right_end = len(inorder) - 2
root.left = buildTree(left_preorder, left_inorder, left_start, left_end, levelorder)
root.right = buildTree(right_preorder, right_inorder, right_start, right_end, levelorder)
return root
```
在递归函数中,我们首先根据先序序列的第一个节点来构造根节点。然后,根据根节点在中序序列中的位置,将中序序列划分为左右子树,并将先序序列也划分为左右子树。接着,我们递归构造左右子树,并将其连接到根节点上。
3.获取层序序列
最后,我们需要实现一个函数来获取给定二叉树的层序序列。该函数可以使用队列来实现广度优先遍历,将每层节点的值添加到结果列表中。
```python
def levelOrder(root):
if not root:
return []
queue = [root]
res = []
while queue:
level = []
size = len(queue)
for i in range(size):
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
```
完整代码实现如下:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder, inorder):
if not preorder:
return None
# 根节点为先序序列的第一个节点
root_val = preorder[0]
root = TreeNode(root_val)
# 划分左右子树
idx = inorder.index(root_val)
left_inorder = inorder[:idx]
right_inorder = inorder[idx+1:]
left_preorder = []
right_preorder = []
# 根据左右子树在中序序列中的位置,划分先序序列
for val in preorder[1:]:
if val in left_inorder:
left_preorder.append(val)
else:
right_preorder.append(val)
# 递归构造左右子树
left_start = 0
left_end = len(left_inorder) - 1
right_start = len(left_inorder)
right_end = len(inorder) - 2
root.left = buildTree(left_preorder, left_inorder, left_start, left_end, levelorder)
root.right = buildTree(right_preorder, right_inorder, right_start, right_end, levelorder)
return root
def levelOrder(root):
if not root:
return []
queue = [root]
res = []
while queue:
level = []
size = len(queue)
for i in range(size):
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
```
参考链接:
- [LeetCode 题解](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/gong-shui-san-xie-yi-ti-shuang-jie-ti-rua-39f5/)
- [算法基础课](https://www.acwing.com/video/2574/)