用顺序存储结构来存储一颗具有n个结点的二叉树，编写算法实现对该二叉树进行先序遍历，输出先序遍历序列。

假设二叉树的结点按照从上到下、从左到右的顺序编号为1~n，则可以使用数组来存储二叉树，具体存储方式如下：

- 结点i的左孩子为2i，右孩子为2i+1；
- 结点i的父节点为i/2（向下取整，根节点的父节点为0）。

根据这个存储方式，可以按照先序遍历的顺序依次输出数组中的元素。

具体实现的代码如下：

void preorder(int* tree, int i, int n) {
    if(i <= n) {
        cout << tree[i] << " "; // 输出当前结点的值
        preorder(tree, 2*i, n); // 遍历左子树
        preorder(tree, 2*i+1, n); // 遍历右子树
    }
}

其中，tree是存储二叉树的数组，i是当前遍历的结点编号，n是二叉树的结点总数。调用preorder(tree, 1, n)即可输出先序遍历序列。

相关问题

用顺序存储结构来存储一颗具有n个结点的二叉树，编写算法实现对该二叉树进行先序遍历，输出先序遍历序列。用c语言怎么写

假设二叉树的结点结构体定义如下：

typedef struct node {
    int data; //结点数据
    struct node *left; //左子树指针
    struct node *right; //右子树指针
} Node;

则可以使用一个数组来存储二叉树，按照完全二叉树的顺序存储，即从上到下、从左到右存储结点。对于第i个结点，其左子树存储在2i处，右子树存储在2i+1处。

先序遍历的递归算法如下：

void preorderTraversal(Node *tree, int i) {
    if (i > n || tree[i] == NULL) {
        return;
    }
    printf("%d ", tree[i]->data); //输出当前结点
    preorderTraversal(tree, 2*i); //遍历左子树
    preorderTraversal(tree, 2*i+1); //遍历右子树
}

其中，n为二叉树结点个数，tree为存储二叉树的数组，i为当前结点的下标。

用顺序存储结构来存储一颗具有n个结点的二叉树，编写算法实现对该二叉树进行先序遍历，输出先序遍历序列

我们可以使用数组来存储二叉树，对于第i个节点，它的左子节点存储在2i位置上，右子节点存储在2i+1位置上，父节点存储在i/2位置上。

下面是先序遍历的递归实现：

def pre_order_traversal(tree, i):
    if i >= len(tree) or tree[i] is None:
        return
    print(tree[i], end=" ")
    pre_order_traversal(tree, 2*i)
    pre_order_traversal(tree, 2*i+1)

其中，tree是存储二叉树的数组，i是当前节点的位置。

我们可以从根节点开始遍历整个树：

tree = [None, 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
pre_order_traversal(tree, 1)

输出结果为：`A B D H E I C F G`，即为先序遍历序列。