二叉树的存储表示

数据结构（⼆⼗四）⼆叉树的链式存储结构（⼆叉链表） ⼀、⼆叉树每个结点最多有两个孩⼦，所以为它设计⼀个数据域和两个指针域，称这样的链表叫做⼆叉链表。

⼆、结点结构包括：lchild左孩⼦指针域、data数据域和rchild右孩⼦指针域。

三、⼆叉链表的C语⾔代码实现：#include "string.h"#include "stdio.h"#include "stdlib.h"#include "io.h"#include "math.h"#include "time.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSIZE 100 /* 存储空间初始分配量 */typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 *//* ⽤于构造⼆叉树********************************** */int index=1;typedef char String[24]; /* 0号单元存放串的长度 */String str;Status StrAssign(String T,char *chars){int i;if(strlen(chars)>MAXSIZE)return ERROR;else{T[0]=strlen(chars);for(i=1;i<=T[0];i++)T[i]=*(chars+i-1);return OK;}}/* ************************************************ */typedef char TElemType;TElemType Nil=''; /* 字符型以空格符为空 */Status visit(TElemType e){printf("%c ",e);return OK;}typedef struct BiTNode /* 结点结构 */{TElemType data; /* 结点数据 */struct BiTNode *lchild,*rchild; /* 左右孩⼦指针 */}BiTNode,*BiTree;/* 构造空⼆叉树T */Status InitBiTree(BiTree *T){*T=NULL;return OK;}/* 初始条件: ⼆叉树T存在。

二叉树的顺序存储及基本操作二叉树的顺序存储是将树中的节点按照完全二叉树从上到下、从左到右的顺序依次存储到一个一维数组中，采用这种方式存储的二叉树也被称为完全二叉树。

一、在使用顺序存储方式时，可以使用以下公式来计算一个节点的左右子节点和父节点：
1. 左子节点：2i+1（i为父节点的在数组中的下标）
2. 右子节点：2i+2
3. 父节点：(i-1)/2（i为子节点在数组中的下标）
二、基本操作：
1. 创建二叉树：按照上述公式将节点存储到数组中。

2. 遍历二叉树：可采用递归或非递归方式，进行前序、中序、后序、层次遍历。

3. 插入节点：先将节点插入到数组末尾，然后通过比较节点和其父节点的大小，进行上浮操作直到满足二叉树的性质。

4. 删除节点：先将待删除节点和最后一个节点交换位置，然后通过比较交换后的节点和其父节点的大小，进行下沉操作直到满足二
叉树的性质。

5. 查找节点：根据节点值进行查找，可采用递归或非递归方式。

6. 修改节点：根据节点值进行查找，然后进行修改操作。

树和二叉树树与二叉树是本书的重点内容之一，知识点多且比较零碎。

其中二叉树又是本章的重点。

在本章中我们要了解树的定义、熟悉树的存储结构、遍历；二叉树的定义、性质、存储结构、遍历以及树、森林、二叉树的转换。

哈夫曼树及哈夫曼编码等内容。

算法的重点是二叉树的遍历及其应用。

6.1 树的定义一、树的定义树：树是n(n>0)个结点的有限集合T。

一棵树满足下列条件：（1）有且仅有一个称为根的结点；（2）其余结点可分为m(m>=0)棵互不相交的有限集合T1,T2,T3,…Tm，其中每个集合又是一棵树，并称之为根的子树。

有关树的一些基本概念：1）结点的度：树中每个结点具有的子树数目或后继结点数。

如图中结点A的度为2，B的度为32) 树的度：所有结点的度的最大值为树的度。

（图中树的度为3）3) 分支结点：即：树中所有度大于0的结点。

4) 叶子结点：即：树中度为零的结点，也称为终端结点。

5) 孩子结点：一个结点的后续结点称为该结点的孩子结点。

6) 双亲结点：一个结点为其后继结点的双亲结点。

7) 子孙结点：一个结点的所有子树中的结点为该结点的子孙结点。

8) 祖先结点：从根结点到一个结点的路径上所有结点（除自己外）称为该结点的祖先结点。

（如Ａ和Ｂ为Ｄ结点的祖先结点）9) 兄弟结点：具有同一父亲的结点互相为兄弟结点。

（如Ｂ和Ｃ为兄弟结点）10) 结点的层数：从根结点到该结点的路径上的结点总数称为该结点的层数（包括该结点）。

11) 树的深度（高度）：树中结点的最大层数为树的深度。

（图中树的深度为4）12) 森林：0个或多个互不相交的树的集合。

上图中：树的度为3，树的深度为4。

结点A，B，C，D，E，F，G，H，I，J的度分别为：2, 3, 2, 0 ,2 , 0, 0, 0, 0, 0叶结点有：D, F, G, H, I, JB,C为兄弟，D, E, F为兄弟，F, G为兄弟。

I，J为兄弟。

二、树的表示1. 树的逻辑结构描述Tree=（D，R）其中：D为具有相同性质的数据元素的集合。

数据结构实验报告—二叉树数据结构实验报告—二叉树引言二叉树是一种常用的数据结构，它由节点和边构成，每个节点最多有两个子节点。

在本次实验中，我们将对二叉树的基本结构和基本操作进行实现和测试，并深入了解它的特性和应用。

实验目的1. 掌握二叉树的基本概念和特性2. 熟练掌握二叉树的基本操作，包括创建、遍历和查找等3. 了解二叉树在实际应用中的使用场景实验内容1. 二叉树的定义和存储结构：我们将首先学习二叉树的定义，并实现二叉树的存储结构，包括节点的定义和节点指针的表示方法。

2. 二叉树的创建和初始化：我们将实现二叉树的创建和初始化操作，以便后续操作和测试使用。

3. 二叉树的遍历：我们将实现二叉树的前序、中序和后序遍历算法，并测试其正确性和效率。

4. 二叉树的查找：我们将实现二叉树的查找操作，包括查找节点和查找最大值、最小值等。

5. 二叉树的应用：我们将探讨二叉树在实际应用中的使用场景，如哈夫曼编码、二叉搜索树等。

二叉树的定义和存储结构二叉树是一种特殊的树形结构，它的每个节点最多有两个子节点。

节点被表示为一个由数据和指向其左右子节点的指针组成的结构。

二叉树可以分为三类：满二叉树、完全二叉树和非完全二叉树。

二叉树可以用链式存储结构或顺序存储结构表示。

- 链式存储结构：采用节点定义和指针表示法，通过将节点起来形成一个树状结构来表示二叉树。

- 顺序存储结构：采用数组存储节点信息，通过计算节点在数组中的位置来进行访问和操作。

二叉树的创建和初始化二叉树的创建和初始化是二叉树操作中的基础部分。

我们可以通过手动输入或读取外部文件中的数据来创建二叉树。

对于链式存储结构，我们需要自定义节点和指针，并通过节点的方式来构建二叉树。

对于顺序存储结构，我们需要定义数组和索引，通过索引计算来定位节点的位置。

一般来说，初始化一个二叉树可以使用以下步骤：1. 创建树根节点，并赋初值。

2. 创建子节点，并到父节点。

3. 重复步骤2，直到创建完整个二叉树。

实验5：树（二叉树）（采用二叉链表存储）一、实验项目名称二叉树及其应用二、实验目的熟悉二叉树的存储结构的特性以及二叉树的基本操作。

三、实验基本原理之前我们都是学习的线性结构，这次我们就开始学习非线性结构——树。

线性结构中结点间具有唯一前驱、唯一后继关系，而非线性结构中结点的前驱、后继的关系并不具有唯一性。

在树结构中，节点间关系是前驱唯一而后继不唯一，即结点之间是一对多的关系。

直观地看，树结构是具有分支关系的结构（其分叉、分层的特征类似于自然界中的树）。

四、主要仪器设备及耗材Window 11、Dev-C++5.11五、实验步骤1.导入库和预定义2.创建二叉树3.前序遍历4.中序遍历5.后序遍历6.总结点数7.叶子节点数8.树的深度9.树根到叶子的最长路径10.交换所有节点的左右子女11.顺序存储12.显示顺序存储13.测试函数和主函数对二叉树的每一个操作写测试函数，然后在主函数用while+switch-case的方式实现一个带菜单的简易测试程序，代码见“实验完整代码”。

实验完整代码：#include <bits/stdc++.h>using namespace std;#define MAX_TREE_SIZE 100typedef char ElemType;ElemType SqBiTree[MAX_TREE_SIZE];struct BiTNode{ElemType data;BiTNode *l,*r;}*T;void createBiTree(BiTNode *&T){ElemType e;e = getchar();if(e == '\n')return;else if(e == ' ')T = NULL;else{if(!(T = (BiTNode *)malloc(sizeof (BiTNode)))){cout << "内存分配错误!" << endl;exit(0);}T->data = e;createBiTree(T->l);createBiTree(T->r);}}void createBiTree2(BiTNode *T,int u) {if(T){SqBiTree[u] = T->data;createBiTree2(T->l,2 * u + 1);createBiTree2(T->r,2 * u + 2); }}void outputBiTree2(int n){int cnt = 0;for(int i = 0;cnt <= n;i++){cout << SqBiTree[i];if(SqBiTree[i] != ' ')cnt ++;}cout << endl;}void preOrderTraverse(BiTNode *T) {if(T){cout << T->data;preOrderTraverse(T->l);preOrderTraverse(T->r);}}void inOrderTraverse(BiTNode *T) {if(T){inOrderTraverse(T->l);cout << T->data;inOrderTraverse(T->r);}}void beOrderTraverse(BiTNode *T){if(T){beOrderTraverse(T->l);beOrderTraverse(T->r);cout << T->data;}}int sumOfVer(BiTNode *T){if(!T)return 0;return sumOfVer(T->l) + sumOfVer(T->r) + 1;}int sumOfLeaf(BiTNode *T){if(!T)return 0;if(T->l == NULL && T->r == NULL)return 1;return sumOfLeaf(T->l) + sumOfLeaf(T->r);}int depth(BiTNode *T){if(!T)return 0;return max(depth(T->l),depth(T->r)) + 1;}bool LongestPath(int dist,int dist2,vector<ElemType> &ne,BiTNode *T) {if(!T)return false;if(dist2 == dist)return true;if(LongestPath(dist,dist2 + 1,ne,T->l)){ne.push_back(T->l->data);return true;}else if(LongestPath(dist,dist2 + 1,ne,T->r)){ne.push_back(T->r->data);return true;}return false;}void swapVer(BiTNode *&T){if(T){swapVer(T->l);swapVer(T->r);BiTNode *tmp = T->l;T->l = T->r;T->r = tmp;}}//以下是测试程序void test1(){getchar();cout << "请以先序次序输入二叉树结点的值，空结点用空格表示:" << endl; createBiTree(T);cout << "二叉树创建成功!" << endl;}void test2(){cout << "二叉树的前序遍历为:" << endl;preOrderTraverse(T);cout << endl;}void test3(){cout << "二叉树的中序遍历为:" << endl;inOrderTraverse(T);cout << endl;}void test4(){cout << "二叉树的后序遍历为:" << endl;beOrderTraverse(T);cout << endl;}void test5(){cout << "二叉树的总结点数为：" << sumOfVer(T) << endl;}void test6(){cout << "二叉树的叶子结点数为：" << sumOfLeaf(T) << endl; }void test7(){cout << "二叉树的深度为：" << depth(T) << endl;}void test8(){int dist = depth(T);vector<ElemType> ne;cout << "树根到叶子的最长路径:" << endl;LongestPath(dist,1,ne,T);ne.push_back(T->data);reverse(ne.begin(),ne.end());cout << ne[0];for(int i = 1;i < ne.size();i++)cout << "->" << ne[i];cout << endl;}void test9(){swapVer(T);cout << "操作成功!" << endl;}void test10(){memset(SqBiTree,' ',sizeof SqBiTree);createBiTree2(T,0);cout << "操作成功!" << endl;}void test11(){int n = sumOfVer(T);outputBiTree2(n);}int main(){int op = 0;while(op != 12){cout << "-----------------menu--------------------" << endl;cout << "--------------1：创建二叉树--------------" << endl;cout << "--------------2：前序遍历----------------" << endl;cout << "--------------3：中序遍历----------------" << endl;cout << "--------------4：后序遍历----------------" << endl;cout << "--------------5：总结点数----------------" << endl;cout << "--------------6：叶子节点数--------------" << endl;cout << "--------------7：树的深度----------------" << endl;cout << "--------------8：树根到叶子的最长路径----" << endl;cout << "--------------9：交换所有节点左右子女----" << endl;cout << "--------------10：顺序存储---------------" << endl;cout << "--------------11：显示顺序存储-----------" << endl;cout << "--------------12：退出测试程序-----------" << endl;cout << "请输入指令编号:" << endl;if(!(cin >> op)){cin.clear();cin.ignore(INT_MAX,'\n');cout << "请输入整数!" << endl;continue;}switch(op){case 1:test1();break;case 2:test2();break;case 3:test3();break;case 4:test4();break;case 5:test5();break;case 6:test6();break;case 7:test7();break;case 8:test8();break;case 9:test9();break;case 10:test10();break;case 11:test11();break;case 12:cout << "测试结束!" << endl;break;default:cout << "请输入正确的指令编号!" << endl;}}return 0;}六、实验数据及处理结果测试用例：1.创建二叉树（二叉链表形式）2.前序遍历3.中序遍历4.后序遍历5.总结点数6.叶子结点数7.树的深度8.树根到叶子的最长路径9.交换所有左右子女10.顺序存储七、思考讨论题或体会或对改进实验的建议通过这次实验，我掌握了二叉树的顺序存储和链式存储，体会了二叉树的存储结构的特性，掌握了二叉树的树上相关操作。

二叉树顺序存储结构和链式存储结构二叉树是一种非常重要的数据结构，它在计算机科学中有着广泛的应用。

在二叉树中，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树可以用两种方式进行存储，分别是顺序存储结构和链式存储结构。

一、二叉树顺序存储结构二叉树顺序存储结构是将二叉树中的节点按照层次顺序依次存储在一个一维数组中。

具体来说，假设二叉树的深度为d，那么数组的长度就应该为2^d-1。

对于任意一个节点i，它的左子节点的下标为2i，右子节点的下标为2i+1，它的父节点的下标为i/2。

二叉树顺序存储结构的优点是可以快速地访问任意一个节点，因为它们在数组中是连续存储的。

同时，由于不需要额外的指针来存储节点之间的关系，因此空间利用率比较高。

但是，它的缺点也很明显，那就是当二叉树的深度比较大时，数组中会存在大量的空节点，造成空间浪费。

二、二叉树链式存储结构二叉树链式存储结构是将二叉树中的每个节点看作一个对象，每个对象包含三个属性，分别是节点的值、左子节点的指针和右子节点的指针。

通过这种方式，可以将二叉树中的节点按照任意顺序存储在内存中。

二叉树链式存储结构的优点是可以有效地利用内存空间，因为只有实际存在的节点才会占用内存。

同时，由于每个节点都有指向左右子节点的指针，因此可以方便地进行节点的插入、删除和查找操作。

但是，它的缺点也很明显，那就是需要额外的指针来存储节点之间的关系，因此空间利用率比较低。

三、二叉树顺序存储结构和链式存储结构的比较二叉树顺序存储结构和链式存储结构各有优缺点，具体使用哪种方式取决于具体的应用场景。

一般来说，如果需要频繁地进行节点的插入、删除和查找操作，那么应该选择链式存储结构；如果需要快速地访问任意一个节点，那么应该选择顺序存储结构。

二叉树的存储结构还可以根据具体的应用场景进行优化。

例如，在某些情况下，可以使用哈希表来存储二叉树中的节点，以提高访问速度和空间利用率。

二叉树是一种非常重要的数据结构，它的存储结构对于算法的效率和空间利用率有着重要的影响。

c语言使用括号表示法输入二叉树并转化为二叉树的链式存储结构-回复C语言中二叉树的链式存储结构是一种常见且有效的数据结构，可以以节点的形式表示二叉树，使得对二叉树的操作更加灵活和高效。

在这篇文章中，我们将详细讨论如何使用括号表示法输入二叉树并转化为二叉树的链式存储结构。

第一步：了解二叉树的定义和特点在开始讨论之前，我们需要先明确二叉树的定义和特点。

二叉树是一种树形结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树的链式存储结构利用节点之间的指针连接，将二叉树的节点表示为一个结构体。

typedef struct TreeNode {int data; 节点数据struct TreeNode* leftChild; 左子节点指针struct TreeNode* rightChild; 右子节点指针} TreeNode;第二步：了解括号表示法和二叉树的对应关系括号表示法是一种使用括号和逗号表示二叉树结构的方法。

在括号表示法中，每个节点的左子节点可以被表示为“(”，右子节点可以被表示为“)”，而逗号用于分隔每个节点。

例如，下面是一个使用括号表示法表示的二叉树：((4), ((7), (8, (6)), (9, ()), ()), (2), ((5), ((1), ()), (3, (), (10))))第三步：构建转化函数使用括号表示法输入的二叉树需要经过一定的处理，才能将其转化为二叉树的链式存储结构。

为了完成这个转化过程，我们可以定义一个递归函数，该函数接收一个字符串作为输入，并返回根节点的指针。

TreeNode* convertToBinaryTree(char* str) {static int index = 0;TreeNode* root = NULL;if (str[index] == '(') {index++;if (str[index] != ')') {root = malloc(sizeof(TreeNode));sscanf(&str[index], "d", &root->data);root->leftChild = convertToBinaryTree(str);root->rightChild = convertToBinaryTree(str);}index++;}return root;}第四步：编写测试代码为了验证上述转化函数的正确性，我们需要编写一些测试代码。

二叉树的二叉链表存储及基本操作《二叉树的二叉链表存储及基本操作》一、二叉树的二叉链表表示及存储1．定义二叉树的二叉链表存储表示是把一个二叉树存放在计算机中的一种表示形式，它是由一组以结点对象为元素的链表构成的，结点对象中包括数据域和结构域。

数据域存放结点的数据元素；结构域由两个指针域组成，其中一个指向左孩子，另一个指向右孩子。

2．存储形式二叉树的二叉链表存储表示可以用如下的存储形式表示：typedef struct BTNode {TElemType data; // 结点的数据域struct BTNode *lchild; // 指向左孩子的指针域struct BTNode *rchild; // 指向右孩子的指针域} BTNode; // 树结点的定义typedef BTNode *BiTree; // 定义二叉树的指针类型3．空的二叉树把一个指向树结点的指针设为NULL，称为一个空的二叉树。

一般在某个树被销毁后，都要把该树设置成空树。

二、二叉树的基本操作1．求二叉树的结点数要求二叉树的结点数，可以用递归的方法求解。

求n个结点的二叉树的结点数，可以先求出它的左子树结点数，右子树结点数，再加上根结点的数量就得到了结点数。

// 求二叉树的结点数int CountBTNode(BiTree T){if (T == NULL) // 空树，结点数为0return 0;else // 左子树结点数 + 右子树结点数 + 1return CountBTNode(T -> lchild) + CountBTNode(T -> rchild) + 1;}2．求二叉树叶结点数要求二叉树叶结点数，也可以用递归的方法求解。

当一个结点的左子树为空树，右子树也为空树时，它就是一个叶结点，则叶结点数加1；如果结点不是叶结点，则继续求它的左子树叶结点数和右子树叶结点数，再把它们加起来就是该二叉树的叶结点数。

// 求二叉树叶结点数int CountBTLeaf(BiTree T){if (T == NULL) // 空树，叶结点数为0return 0;else if (T -> lchild == NULL && T -> rchild == NULL) //判读是否是叶结点return 1;else // 左子树叶结点数 + 右子树叶结点数return CountBTLeaf(T -> lchild) + CountBTLeaf(T -> rchild);}3．求二叉树深度要求二叉树深度，也可以用递归的方法求解。

二叉树的定义、定义、存储二叉树的定义二叉树是每个节点最多有两个子树的树结构。

通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

二叉树常被用于实现二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。

特殊二叉树1. 斜树所有结点都只有左子树的二叉树叫左斜树，所有结点都只有右子树的二叉树叫右斜树。

斜树的每一层都只有一个结点，结点的个数与斜树的深度相同。

2. 满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。

（上图中所示的二叉树，就是一棵满二叉树）3. 完全二叉树对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中的编号为i的结点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。

二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点（i≥1）。

（数学归纳法可证）性质2：深度为k的二叉树最多有2k-1个结点（k≥1）。

（由性质1，通过等比数列求和可证）性质3：一棵二叉树的叶子结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。

证：结点总数n = n0 + n1 + n2。

设B为分支总数，因为除根节点外，其余结点都有一个分支进入，所以n = B + 1。

又因为分支是由度为1或2的结点射出，所以B = n1 + 2n2。

综上：n = n0 + n1 + n2 = B + 1 = n1 + 2n2 + 1，得出：n0 = n2 + 1。

性质4：具有n个结点的完全二叉树的深度为floor(log2n) + 1 。

性质5：如果对一棵有n个结点的完全二叉树（其深度为floor(log2n) + 1 ）的结点按层序编号，则对任一结点i（1≤i≤n）有：（1）如果i = 1，则结点i是二叉树的根，无双亲；如果i > 1，则其双亲PARENT(i)是结点 floor((i)/2)。

二叉树的顺序存储结构代码介绍二叉树是一种常用的数据结构，它由节点组成，每个节点最多有两个子节点。

在计算机中，我们通常使用顺序存储结构来表示二叉树。

顺序存储结构是将二叉树的节点按照从上到下、从左到右的顺序依次存储在一个数组中。

本文将详细介绍二叉树的顺序存储结构代码，包括初始化、插入节点、删除节点以及遍历等操作。

二叉树的顺序存储结构代码实现初始化二叉树首先，我们需要定义一个数组来存储二叉树的节点。

假设数组的大小为n，则二叉树的最大节点数量为n-1。

# 初始化二叉树，将数组中所有元素置为空def init_binary_tree(n):binary_tree = [None] * nreturn binary_tree插入节点在二叉树的顺序存储结构中，节点的插入操作需要保持二叉树的特性，即左子节点小于父节点，右子节点大于父节点。

插入节点的算法如下：1.找到待插入位置的父节点索引parent_index。

2.如果待插入节点小于父节点，将其插入到父节点的左子节点位置，即数组索引2*parent_index+1处。

3.如果待插入节点大于父节点，将其插入到父节点的右子节点位置，即数组索引2*parent_index+2处。

# 插入节点def insert_node(binary_tree, node):index = 0 # 当前节点的索引值，初始值为根节点的索引值while binary_tree[index] is not None:if node < binary_tree[index]:index = 2 * index + 1 # 插入到左子节点else:index = 2 * index + 2 # 插入到右子节点binary_tree[index] = node删除节点删除节点需要保持二叉树的特性，即在删除节点后，仍然满足左子节点小于父节点，右子节点大于父节点的条件。

删除节点的算法如下：1.找到待删除节点的索引delete_index。