二叉树的存储结构（数据结构）

港控/mmm° 2022-06-09 06:48 202阅读 0赞

#     #

# 1. 链式存储结构 #

即单链表结构或双链表结构（同树）。

数据结构修改如下：

typedef struct node;
    typedef node *tree;
    struct node{
    	char data;
    	tree lchild,rchild;
    };
    tree bt;

typedef struct node;
    typedef node *tree;
    struct node{
    	char data;
    	tree lchild,rchild,father;
    };
    tree bt;

如下图的一棵二叉树用单链表就可以表示成右边的形式：

![20170830125517109][]

#     #

# 2.顺序存储结构。 #

即几个数组加一个指针变量。数据结构修改如下：

const int n=10;
    char data[n];
    char lchild[n];
    char rchild[n];
    int bt;//根节点指针

二叉树在处理表达式时经常用到，一般用叶结点表示运算元，分支结点表示运算符。这样的二叉树称为表达式树。如现在有一个表达式：（a+b/c）\*(d-e)。可以用以图表示：

![20170830132627997][]

数据结构定义如下：

按表达式的书写顺序逐个编号，分别为1..9，注意表达式中的所有括号在树中是不出现的，因为表达式树本身就是有序的。叶结点的左右子树均为空（用0表示）。

char data\[9\] = \{'a', '+', 'b','/', 'c', '\*', 'd', '-', 'e'\};

intlchild\[9\] = \{0,1,0,3,0,2,0,7,0\};

int rchild\[9\] =\{0,4,0,5,0,8,0,9,0\};

int bt; //根结点指针,初值=6，指向'\*'

![20170830133612325][]

二叉树的操作:最重要的是遍历二叉树，但基础是建一棵二叉树、插入一个结点到二叉树中、删除结点或子树等。

[20170830125517109]: /images/20220609/8b3990c2311a477db6142ff0429c7d88.png
[20170830132627997]: /images/20220609/78bede7c953b4721be0052ea774fb655.png
[20170830133612325]: /images/20220609/0a9830d11d08470eb0d2d8ffe56e7610.png

发表评论取消回复

表情：

评论列表（有 0 条评论，202人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构-顺序存储二叉树

文章目录目录文章目录前言一 . 什么是顺序存储二叉树二 . 模拟实现前序遍历总结 -------------------- 前言 >

爱被打了一巴掌/ 2024年03月01日 07:45/ 0 赞/ 7 阅读

相关【数据结构】图解二叉树的存储结构

文章目录二叉树的顺序存储结构二叉链表二叉树的顺序存储结构二叉树的存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也

迷南。/ 2023年02月19日 11:24/ 0 赞/ 80 阅读

相关二叉树的存储结构（数据结构学习笔记）

文章目录顺序存储结构完全二叉树的顺序存储结构非完全二叉树的顺序存储结构顺序存储结构的类

缺乏、安全感/ 2022年12月28日 04:22/ 0 赞/ 164 阅读

相关数据结构二叉树的线索存储

include <stdio.h> include <stdlib.h> include <iostream.h>

喜欢ヅ旅行/ 2022年09月19日 01:44/ 0 赞/ 141 阅读

相关二叉树的存储结构（数据结构）

1. 链式存储结构即单链表结构或双链表结构（同树）。数据结构修改如下： typedef struct node; type

港控/mmm°/ 2022年06月09日 06:48/ 0 赞/ 203 阅读

相关数据结构——树—— 二叉树及存储结构

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查

电玩女神/ 2022年04月16日 04:06/ 0 赞/ 231 阅读

相关数据结构(9) 树[三]（二叉树存储结构）

数据结构——二叉树的存储结构之前已经谈过了树的存储结构，并且说到顺序存储对树这一种一对多的关系的结构实现起来比较困难。但是二叉树是一种特殊的树，由于它的特殊性，使得用顺

男娘i/ 2022年02月03日 06:55/ 0 赞/ 204 阅读

相关数据结构--二叉树的存储结构

文章目录顺序存储表示链式存储表示二叉链表三叉链表顺序存储表示以存储的数据是整型为例。 // 二叉树的最

r囧r小猫/ 2022年01月07日 17:53/ 0 赞/ 298 阅读

相关二叉树的存储结构

二叉树的存储-顺序存储完全二叉树：对结点按照上至下、从左到右的次序进行存储 ![1736739-20190719222741456-1034916964.png][]

深藏阁楼爱情的钟/ 2021年10月18日 12:00/ 0 赞/ 422 阅读

相关【数据结构】二叉树顺序存储结构实现

二叉树顺序结构的存储实现是用数组存储的，使用下标存储第i个节点。二叉树的顺序存储结构非常适合存储满二叉树，这使得二叉树的存储占用最少。在数组中完全二叉树中没有双亲节点的值用

r囧r小猫/ 2021年09月21日 08:18/ 0 赞/ 411 阅读