二叉树的存储结构C语言代码+Python代码实现

fanstuck

已于 2023-11-01 17:51:37 修改

阅读量6.9k

点赞数 13

分类专栏：数据结构文章标签：数据结构二叉树存储

于 2022-04-17 18:22:26 首次发布

本文链接：https://blog.csdn.net/master_hunter/article/details/124160255

版权

数据结构专栏收录该内容

12 篇文章

订阅专栏

一、二叉树概述

二叉树是一种常见的树状数据结构，它由节点组成，每个节点最多有两个子节点：一个称为左子节点，另一个称为右子节点。

以下是二叉树的基本特点和定义：

根节点（Root）： 二叉树的顶端节点，它没有父节点，是整棵树的起始点。
节点（Node）： 二叉树中的每个元素称为一个节点，每个节点包含一个值（或者称为数据）以及指向左子节点和右子节点的指针。
左子节点和右子节点： 每个节点可以包含最多两个子节点，分别称为左子节点和右子节点。这两个子节点可以为空。
叶子节点（Leaf Node）： 没有子节点的节点称为叶子节点，它们位于二叉树的末端。
父节点和子节点： 一个节点的直接连接的节点称为其子节点，而该节点称为其子节点的父节点。
深度（Depth）： 从根节点到某个节点的唯一路径上的节点总数。
高度（Height）： 从某个节点到其叶子节点的最长路径上的节点总数。
子树（Subtree）： 以某个节点为根节点的子树包含该节点及其所有后代节点。
二叉搜索树（Binary Search Tree）： 一种特殊的二叉树，它满足左子树上所有节点的值都小于根节点的值，右子树上所有节点的值都大于根节点的值。

二叉树的结构可以在许多算法和数据操作中发挥重要作用，如搜索、排序、遍历等。它在计算机科学领域中得到了广泛的应用。

二、二叉树存储方式

二叉树可以使用不同的存储方式，包括链式存储和顺序存储两种主要方式。

链式存储（Linked Representation）：

在链式存储中，二叉树的每个节点都是一个对象，其中包含了节点的值以及指向左子节点和右子节点的指针。这种方式适用于动态的、不固定大小的二叉树。

节点定义： 一个典型的节点可以用如下 Python 类来表示：

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

一个简单的链式存储的二叉树可以如下所示：

      1
     / \
    2   3
   / \
4   5

对应的节点对象：

node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)

node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5

顺序存储（Sequential Representation）

二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的节点元素，即将完全二叉树上的编号为i的结点元素存储在一维数组下摆为i-1的分量中。

依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中节点的序号可以唯一地反映节点之间的逻辑关系，这样既鞥最大可能地节省存储空间，又能利用数组元素的下标值。

普通二叉树转完全二叉树的方法很简单，只需给二叉树额外添加一些节点，将其"拼凑"成完全二叉树即可。

例如一颗普通二叉树：

转为顺序存储就为：

将树中节点按照层次并从左到右依次标号（1,2,3,...），若节点 i 有左右孩子，则其左孩子节点为 2*i，右孩子节点为 2*i+1。此性质可用于还原数组中存储的完全二叉树。

二叉树顺序结构存储实现代码：

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 8
using namespace std;
//初始化二叉树
void EmptyTree(int Tree[])
{
    for(int i=0;i<MAX_SIZE;i++)
    {
        Tree[i]=0;
    }
}
//给i节点赋值操作
int setNode(int Tree[],int i,int x)
{
    if(Tree == NULL) {printf("二叉树为空"); return 0;}
    if(i>=MAX_SIZE) {printf("超出数组范围");return 0;}
    Tree[i]=x;
    return 1;
}
//给i节点的左孩子设置值
int setLeftChild(int Tree[],int i,int x)
{
    if(Tree == NULL) {printf("二叉树为空"); return 0;}
    if(i*2 >= MAX_SIZE) {printf("超出数组范围");return 0;}
    Tree[i*2]=x;
    return 1;
}
//给i节点的右孩子设置值
int setRightChild(int Tree[],int i,int x)
{
    if(Tree == NULL) {printf("二叉树为空"); return 0;}
    if(i*2+1 >= MAX_SIZE) {printf("超出数组范围");return 0;}
    Tree[i*2+1]=x;
    return 1;
}
//打印二叉树
void printTree(int Tree[])
{
    for(int i=1;i<MAX_SIZE;i++)
    {
        printf("%d ",Tree[i]);
    }
}
int main()
{
    int Tree[MAX_SIZE];
    EmptyTree(Tree);

    setNode(Tree,1,1);
    setLeftChild(Tree,1,2);
    setRightChild(Tree,1,3);

    setRightChild(Tree,2,4);

    setLeftChild(Tree,3,5);

    printTree(Tree);
}

最后存储的树为：