链式存储判断一棵树完全二叉树

以下是判断一棵二叉树是否是完全二叉树的算法：

def isCompleteTree(root):
    if root is None:
        return True
    
    queue = [root]
    flag = False
    
    while queue:
        node = queue.pop(0)
        
        if node.left:
            if flag:
                return False
            queue.append(node.left)
        else:
            flag = True
        
        if node.right:
            if flag:
                return False
            queue.append(node.right)
        else:
            flag = True
    
    return True

相关问题

二叉树的链式存储初始化一棵树

二叉树的链式存储使用指针来表示树的结构，每个节点包括一个数据域和两个指针域，分别指向左子树和右子树。初始化一棵树需要创建根节点，并为根节点分配空间，然后递归地创建左子树和右子树。

下面是一个示例代码来初始化一棵二叉树：

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 创建一个新节点
TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 初始化一棵树
TreeNode* initTree() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    return root;
}

int main() {
    TreeNode* root = initTree();
    printf("根节点的数据为：%d\n", root->data);
    printf("左子树的根节点数据为：%d\n", root->left->data);
    printf("右子树的根节点数据为：%d\n", root->right->data);
    return 0;
}

在上面的代码中，我们创建了一个名为 TreeNode 的结构体来表示二叉树的节点，其中包括一个数据域和两个指针域。createNode() 函数用来创建一个新节点，initTree() 函数用来初始化一棵树。在 main() 函数中，我们调用 initTree() 函数来初始化一棵树，并打印出根节点、左子树的根节点和右子树的根节点的数据。

1. 设计在链式存储结构上建立一棵二叉树的算法。

设计链式存储结构上建立二叉树的算法通常涉及到递归操作。这里是一个基本的步骤：

1. **创建节点**：首先，你需要定义一个二叉树节点的结构，它包含一个数据域用于存储值，以及两个指针，分别指向左子树和右子树。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

2. **构建空树**：如果输入的数据为空或只有一个元素，那么返回对应的根节点即可。

3. **插入元素**：对于给定的有序链表，你可以从头开始遍历。当找到第一个大于当前节点值的元素时，将其设置为当前节点的右孩子；反之，如果小于或等于，则在当前节点的左侧递归地插入直到找到合适的位置。

   def build_binary_tree(head):
       if head is None or head.next is None:
           return TreeNode(head.val) if head else None
       else:
           slow = head
           fast = head
           while fast and fast.next:
               slow = slow.next
               fast = fast.next.next
           temp = slow.next
           slow.next = None
           root = TreeNode(temp.val)
           root.left = build_binary_tree(head)
           root.right = build_binary_tree(temp.next)
           return root

4. **递归终止条件**：在链表遍历过程中，如果遍历到列表的末尾（即fast或fast.next为None），说明已经到达叶子节点，此时直接返回当前节点。

这个算法利用了链表的特性，不需要预先分配连续的空间，适合动态增长的数据结构。