C++数据结构——树（基础知识篇）
C++数据结构——树（基础知识篇）⽬录
1. 简介
树是数据结构中的重点，也是我们学习数据结构这门课程中的难点，接下来我们会先来介绍⼀下树这种数据结构中的⼀些基础知识，为我们
后⾯的学习打下基础。
本篇博客不涉及代码实现，只有理论知识，所有的代码实现会另起篇幅。
2. 基本结构
⼀棵树是N个节点和N-1条边的集合，其中⼀个节点叫做根节点，每条边都将某个节点连接到它的⽗亲，⽽除去根节点外每个节点都只有⼀
个⽗亲，每个⼦节点之间互不相交。
3. 基础知识
3.1 术语
1.节点的度：节点的⼦节点（⼦树）个数。例如上图中：节点2的度为3，因为它有456三个⼦节点。
2.树的度：树中节点的最⼤的度。
3.叶⼦节点：度为0的节点。上图中节点45678都是叶⼦节点
4.⽗节点：顾名思义，当前节点的⽗亲，就像⼈际关系⼀样，例如：节点1是节点2和节点3的⽗亲。⼦节点，祖⽗节点，兄弟节点等等之类
的以此类推就⾏了。
5.路径和路径长度：路径是⼀个节点序列，是多个节点的集合，⽽路径的长度为路径所包含的边的个数，例如：从节点1到节点4的路径为1-
2-4，路径长度为2。
6.节点的层次：规定根节点在第⼀层，其他的节点层次是其⽗节点的层次+1。
7.树的深度：树中最⼤的层次就是树的深度。
8.树的⾼度：与深度相反，⾼度的第⼀层是深度的最后⼀层，树的⾼度与深度⼀致（深度是从上往下数，⾼度是从下往上数）
3.2 树的表⽰⽅式树有基本的三种表⽰⽅式，分别是双亲表⽰法、孩⼦表⽰法、孩⼦兄弟表⽰法。由于双亲表⽰法和孩⼦表⽰法局限太⼤⽽且不常⽤（有兴趣的读者可以⾃⼰去查阅⼀下其他资料），我们重点介绍⼀下孩⼦兄弟表⽰法。
⼜是这张图，我们已经很清楚图中各个节点之间的关系了，⽽这种树的⼦节点个数并不统⼀，有两个的有三个的，这样我们在创建结构体
（类）的时候会⼗分困难，那么有没有⼀种⽅法可以让他们的结构统⼀起来呢，这就是我们的孩⼦兄弟表⽰法的由来。我们把它稍微变⼀下，它就变成了这样：
数据结构c语言实现
数据结构是计算机科学中重要的一个领域，它研究不同的数据组织方式，以及在这些数据上进行各种操作的算法。常见的数据结构包括数组、栈、队列、链表、树、图等。
在C语言中，数据结构是通过使用结构体来实现的。结构体是由一组数据成员组合而成的自定义数据类型，可以包含不同数据类型的数据成员。以下是如何在C语言中实现不同的数据结构。
数组
数组是数据结构中最基本的数据结构之一。C语言中的数组定义方式如下：
```
int array[5];
```
这个代码定义了一个名为array的数组，其中有5个元素，每个元素的类型是整数。要访问数组中的元素，可以通过下标访问：
这个代码设置了数组中第一个元素的值为1。
栈
栈是一种后进先出（LIFO）的数据结构。使用C语言中的数组可以实现栈。以下是一个简单的栈实现：
```
#define MAXSIZE 100
int stack[MAXSIZE];
int top = -1;
void push(int data){
if(top
stack[++top] = data; //插入数据
} }
int isEmpty(){
return top==-1; //栈是否为空
}
队列
链表
链表是一个由节点组成的数据结构，每个节点包含一个数据成员和一个指向下一个节点的指针。在C语言中，链表可以使用结构体和指针来实现。以下是一个单向链表的实现：
```
struct node{
int data;
struct node *next;
};
struct node *head = NULL;
C++教程1：C++程序结构
下面我们从一个最简单的程序入手看一个C++程序的组成结构。
// my first program in C++
#include
using namespace std;
int main() {
cout << “Hello World!”;
return 0;
} Hello World!
上面左侧显示了我们的第一个程序的源代码，代码文件名称为hellowworld.cpp。右边显示了程序被编译执行后的输出结果。编辑和编译一个程序的方法取决于你用的是什么编译器，根据它是否有图形化的界面及版本的不同，编译方法也有可能不同，具体请参照你所使用的编译器的使用说明。
以上程序是多数初学者学会写的第一个程序，它的运行结果是在屏幕上打出”Hello World!”这句话。 虽然它可能是C++可写出的最简单的程序之一，但其中已经包含了每一个C++程序的基本组成结构。 下面我们就逐个分析其组成结构的每一部分：
// my first program in C++ 这是注释行。所有以两个斜线符号(//)开始的程序行都被认为是注释行，这些注释行是程序员写在程序源代码内，用来对程序作简单解释或描述的，对程序本身的运行不会产生影响。在本例中， 这行注释对本程序是什么做了一个简要的描述。
# include < iostream.h >
以#标志开始的句子是预处理器的指示语句。它们不是可执行代码，只是对编译器作出指示。在本例中这个句子# include < iostream.h > 告诉编译器的预处理器将输入输出流的标准头文件(iostream.h)包括在本程序中。这个头文件包括了C++中定义的基本标准输入-输出程序库的声明。此处它被包括进来是因为在本程序的后面部分中将用到它的功能。
using namespace std;
C++标准函数库的所有元素都被声明在一个名空间中，这就是std名空间。因此为了能够访问它的功能，我们用这条语句来表达我们将使用标准名空间中定义的元素。这条语句在使用标准函数库的C++程序中频繁出现，本教程中大部分代码例子中也将用到它。
1. 设二叉树bt 的存储结构如下，其中bt为树根结点指针，left，right分别为结点的左、右孩子指针，dada为结点的数据域。请完成下列各题：
1） 画出二叉树bt的逻辑结构
2） 写出按先序、中序、后序遍历二叉树所得到的结点序列
3） 画出二叉树bt的后序线索化树
1 2 3 4 5 6 7 8 9 10
0 0 2 3 7 5 8 0 10 1
j h f d b a c e g i
0 0 0 9 4 0 0 0 0 0
2. 二叉树结点数值采用顺序存储结构，如图所示，
1） 画出二叉树表示
2） 写出前序遍历，中序遍历和后序遍历的结果
3） 写出结点值c的父结点，其左、右孩子。
4） 画出将此二叉树还原成森林的图 e a f
d
g
c j
h i
b
3. 已知一棵二叉树的中序序列为cbedahgijk，后序序列为cedbhjifa，画出该二叉树的先序线索二叉树。
4. 有一份电文中共使用五个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、2、9，试画出对应的Huffman树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），求出每个字符的Huffman编码。
5. 设给定权集w={2，3，4，8，9}，试构造关于w的一棵哈夫曼树，并求其加权路径长度WPL。
6. 假设二叉树采用链接存储方式存储，编写一个中序遍历二叉树的非递归过程。
7. 假设二叉树采用链接存储方式存储，root指向根结点，p所指结点为任一给定的结点。编写一个求出从根结点到p所指结点之间路径的函数。
8. 在二叉树中查找值为x的结点，试设计打印值为x的结点的所有祖先的算法，假设值为x的结点不多于1个。
9. 假设二叉树采用链接存储方式存储，试设计一个算法计算一棵给定二叉树的所有结点数。
10. 假设二叉树采用链接存储方式存储，试设计一个算法计算一棵给定二叉树的单孩子结点数。
