用二叉链表的方式建立的树怎么判断是否为完全二叉树

对于一颗二叉树，如果其深度为d，除第d层外，其它各层（1~d-1）的节点数都达到了最大值，第d层所有的节点都从左向右连续地紧密排列，这样的二叉树被称为完全二叉树。

对于二叉链表来说，可以按照层序遍历的顺序给节点编号，从1开始逐个增加。如果当前节点的编号为i，则：

1.如果该节点是根节点，则编号为1；
2.如果该节点的编号为i，那么其左子节点的编号为2i，右子节点的编号为2i+1；
3.如果一个节点的编号为i，但是其父节点的编号为j，则i > j。

那么对于一颗完全二叉树，它的节点编号应该是连续的，没有间断。因此，我们可以按照层序遍历的顺序逐个检查节点的编号是否连续，如果出现了间断，则该二叉树不是完全二叉树。

相关问题

建立二叉树并利用二叉链表的方式存储此二叉树

建立二叉树并利用二叉链表的方式存储此二叉树的步骤如下：

1. 定义二叉树的结构体，包括数据域和左右子树指针域。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

2. 定义二叉链表的结构体，包括根节点指针。

struct BinaryTree {
    TreeNode* root;
    BinaryTree() : root(nullptr) {}
};

3. 通过递归的方式建立二叉树，每次读入一个节点的值，如果值为-1，则表示该节点为空，否则创建一个新节点，并递归创建其左右子树。

TreeNode* buildTree() {
    int val;
    cin >> val;
    if (val == -1) {
        return nullptr;
    }
    TreeNode* root = new TreeNode(val);
    root->left = buildTree();
    root->right = buildTree();
    return root;
}

4. 将建立好的二叉树存储到二叉链表中，即将根节点指针指向建立好的二叉树。

BinaryTree binaryTree;
binaryTree.root = buildTree();

以二叉链表表示二叉树，建立一棵二叉树

### 回答1：
好的，以下是使用二叉链表表示二叉树的代码，建立一棵简单的二叉树：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
# 构建一棵二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

以上代码中，我们定义了一个`TreeNode`类来表示二叉树的节点，节点包括`val`、`left`和`right`三个属性，分别表示节点的值、左子节点和右子节点。然后，我们通过创建一个根节点`root`，以及对其左右子节点的逐层赋值，建立了一棵二叉树。具体来说，这棵二叉树的结构如下所示：

      1
    /   \
   2     3
  / \   / \
 4   5 6   7

### 回答2：
二叉链表是一种常用的数据结构，用于表示二叉树。它由一个称为“结点”的数据类型组成，每个结点中包含了三个指针，分别指向该结点的左子树、右子树和父结点。在这种结构中，每个结点都有了一个与父结点的连接，因此可以轻松地遍历整个二叉树。使用二叉链表可以方便地获取某个结点的左子树、右子树以及父结点等信息。

要建立一棵二叉树，我们需要从根节点开始逐层构建。可以采用递归的方式来构建二叉树。首先，我们需要定义一个结构体类型来表示每一个结点：

struct Node {
    int data;
    Node *left;
    Node *right;
    Node *parent;
};

其中，data表示结点存储的数据，left和right分别表示左子树和右子树的指针，parent表示父结点的指针。接下来，我们可以按照以下步骤来构建二叉树：

1. 定义根结点：

Node *root = new Node;
root->data = 1;
root->left = NULL;
root->right = NULL;
root->parent = NULL;

2. 递归构建左子树和右子树：

root->left = new Node;
root->left->data = 2;
root->left->left = new Node;
root->left->left->data = 4;
root->left->left->left = NULL;
root->left->left->right = NULL;
root->left->left->parent = root->left->left;

root->left->right = new Node;
root->left->right->data = 5;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->left->right->parent = root->left;

root->right = new Node;
root->right->data = 3;
root->right->left = NULL;
root->right->right = new Node;
root->right->right->data = 6;
root->right->right->left = NULL;
root->right->right->right = NULL;
root->right->right->parent = root->right;

在这个例子中，我们先定义了根结点，然后递归构建了左子树和右子树。左子树包含了结点2和结点4、右子树包含了结点3和结点6。可以看到，对于每个结点，我们都需要明确它的左子树、右子树和父结点的指针，才能正确地建立二叉树。

3. 返回根结点：

return root;

最后，返回根结点即可。完整代码如下：

#include <iostream>

using namespace std;

struct Node {
    int data;
    Node *left;
    Node *right;
    Node *parent;
};

Node *buildTree() {
    Node *root = new Node;
    root->data = 1;
    root->left = NULL;
    root->right = NULL;
    root->parent = NULL;

    root->left = new Node;
    root->left->data = 2;
    root->left->left = new Node;
    root->left->left->data = 4;
    root->left->left->left = NULL;
    root->left->left->right = NULL;
    root->left->left->parent = root->left->left;

    root->left->right = new Node;
    root->left->right->data = 5;
    root->left->right->left = NULL;
    root->left->right->right = NULL;
    root->left->right->parent = root->left;

    root->right = new Node;
    root->right->data = 3;
    root->right->left = NULL;
    root->right->right = new Node;
    root->right->right->data = 6;
    root->right->right->left = NULL;
    root->right->right->right = NULL;
    root->right->right->parent = root->right;

    return root;
}

void inorderTraversal(Node *root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->data << " ";
    inorderTraversal(root->right);
}

int main() {
    Node *root = buildTree();
    inorderTraversal(root);
    return 0;
}

在主函数中，我们使用中序遍历的方式来输出二叉树的各个结点。输出结果为“4 2 5 1 3 6”，与我们建立的二叉树结构一致。以上就是使用二叉链表表示二叉树，并建立一棵二叉树的方法。

### 回答3：
二叉链表是常用的一种二叉树的存储方式，将每个节点的左右孩子指针指向它们的子节点，再使用一个指向父节点的指针，构成一个二叉链表。使用二叉链表可以方便地进行二叉树的遍历、查找和插入等操作。

下面介绍如何建立一棵二叉树。

首先，我们需要定义一个二叉树节点的结构体，它应该包含节点值、左右孩子指针和父指针。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode* parent;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr), parent(nullptr) {}
};

接下来，我们可以使用递归的方式，依次创建每个节点，并将其连接到对应的父节点、左右孩子节点。如果孩子节点不存在，则将其置为nullptr。

TreeNode* buildBinaryTree(vector<int>& nums, int start, int end, TreeNode* parent) {
    if (start > end) { // 递归终止条件
        return nullptr;
    }
    int mid = start + (end - start) / 2; // 找到中间节点
    auto root = new TreeNode(nums[mid]); // 创建节点
    root->parent = parent; // 连接到父节点
    root->left = buildBinaryTree(nums, start, mid - 1, root); // 连接左孩子节点
    root->right = buildBinaryTree(nums, mid + 1, end, root); // 连接右孩子节点
    return root;
}

最后，我们可以调用上述函数，传入二叉树的节点数组和其边界，即可完成二叉树的建立过程。例如，我们可以使用以下代码来创建一棵平衡二叉树。

vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
auto root = buildBinaryTree(nums, 0, nums.size() - 1, nullptr);

这样，我们就成功地使用二叉链表表示、创建了一棵二叉树。在实际应用中，我们可以根据需要对二叉树进行遍历、查找和插入等操作。