数据结构——树结构与二叉树

大家好，欢迎来到IT知识分享网。

目录

一、树形结构

1. 树的概念

2. 树的特点

3. 树的专有名词

4. 树的表示

二、二叉树

1. 二叉树的概念

2. 特殊的二叉树

3. 二叉树的性质

4. 二叉树的存储结构

5. 二叉树的遍历

6. 计算二叉树的节点数目和叶子节点数目

一、树形结构

1. 树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

如下图就为树结构：

2. 树的特点

• 有一个特殊的结点，称为根结点，根节点没有前驱结点。
• 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。因此，可以用递归来定义一个树。

注：

• 树形结构中，子树之间不能有交集，否则就不是树形结构。
• 除了根结点外，每个结点有且仅有一个父结点。
• 一颗N个结点的树由N-1条边。

3. 树的专有名词

• 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
• 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点
• 非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点
• 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
• 兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
• 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
• 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
• 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
• 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
• 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
• 森林：由m（m>0）棵互不相交的树的集合称为森林；
• 最近公共祖先：距离某些结点最近的祖先，比如P和Q的最近公共祖先为J，K和F的最近公共祖先为F。结点本身也可以成为自己的祖先

4. 树的表示

树的结构比较复杂，既要保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。一般采用孩子兄弟表示法，下面将简单介绍。

孩子兄弟表示法：（左孩子右兄弟）

如何用孩子兄弟表示法表示下面的树。

 物理结构如下：

每个树节点有一个数据域，两个指针域，分别为孩子指针——指向第一个孩子，兄弟指针——指向它右边的兄弟，这样就可以通过第一个孩子找到其他的孩子节点。此法就很好的显示了一个结点有多少个孩子都无所谓，直接让父亲指向第一个孩子，剩下的孩子用孩子的兄弟指针链接起来。

struct TreeNode { struct TreeNode* firstChild; struct TreeNode* pNextBrother; DataType data; };

二、二叉树

1. 二叉树的概念

二叉树：度为2的树，一棵二叉树是结点的一个有限集合，该集合:或者为空，或者由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

 

从上图可以看出：

1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

对于任意的二叉树都是由以下几种情况复合而成的：

2. 特殊的二叉树

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 2^k -1 ，则它就是满二叉树。
完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 
        满二叉树的每个结点的度均为2，满二叉树是完全二叉树的特殊情况。当深度为K时，完全二叉树就是在【1，k-1】层的区间内均为满二叉树，只有最后一层第K层不满，但是最后一层是从左往右连续的。如下 图示：

3. 二叉树的性质

性质1：若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点。

性质2：若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h – 1 。

性质3：对任何一棵非空二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0 ＝n2 ＋1。

性质4：若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log2(N+1) 。

性质5：对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

• 1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
• 2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
• 3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

 

下面为几个经典题目：

 

4. 二叉树的存储结构

二叉树一般有两种结构存储，一种顺序结构，一种链式结构。

1. 顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2.链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，红黑树，平衡二叉树（AVL树）等会用到三叉链。

5. 二叉树的遍历

二叉树的增删改查一般没有重要意义，主要是作为搜索树使用，而此时就需要遍历整个二叉树，所以遍历二叉树比较重要。下面将介绍二叉树的四种遍历方法及其代码实现。如下一颗简单的二叉树所示，四种遍历方法的结果分别是什么呢？

 任何一课二叉树分为跟节点、左子树和右子树。二叉树的遍历一般采用的是分治的思想，将一个树的左子树和右子树也看为一个树再继续遍历。

一般树的遍历分为四种方式：

• 前序遍历(先根遍历)：ABDEC
• 中序遍历(中根遍历)：DBEAC
• 后序遍历(后根遍历)：DEBCA
• 层序遍历：ABCDE

下面为采用代码实现前、中、后序遍历：

#include<stdio.h> //一个二叉树节点结构 typedef char BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNOde* right; BTDataType data; }BTNode; //先序遍历 void PrevOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%c ", root->data); PrevOrder(root->left); PrevOrder(root->right); } //中序遍历 void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%c ", root->data); InOrder(root->right); } //后续遍历 void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); } PostOrder(root->left); PostOrder(root->right); printf("%c ", root->data); } int main() { //创建节点 BTNode* A = (BTNode*)malloc(sizeof(BTNode)); A->data = 'A'; A->left = NULL; A->right =NULL; BTNode* B = (BTNode*)malloc(sizeof(BTNode)); B->data = 'B'; B->left = NULL; B->right = NULL; BTNode* C = (BTNode*)malloc(sizeof(BTNode)); C->data = 'C'; C->left = NULL; C->right = NULL; BTNode* D = (BTNode*)malloc(sizeof(BTNode)); D->data = 'D'; D->left = NULL; D->right = NULL; BTNode* E = (BTNode*)malloc(sizeof(BTNode)); E->data = 'E'; E->left = NULL; E->right = NULL; //将节点链接起来 A->left = B; A->right = C; B->left = D; B->right = E; PrevOrder(A); printf("\n"); return 0; }

下面为中序遍历的结果，一般我们会将空不写。

 层序遍历二叉树：

层序遍历的方法比较复杂，需要使用到队列，核心思想为上一层带下一层，即每次出一个元素时，就将该元素的孩子节点加入队列中，直至队列中元素个数为0时，出队顺序就是该二叉树的层序遍历结果。

二叉树的前中后序遍历为深度优先搜索，层序遍历为广度优先搜索。

具体思想见下面的图解：

 代码实现层序遍历：

需要用到之前学习过的队列结构，直接将写好队列加入到工程中即可，队列中的元素为一个二叉树节点（结构体），所以再队列元素前需要先声明二叉树结构体，以免报错。如下所示：

 层序遍历核心代码：

//层序遍历 void LevelOrder(BTNode* root) { Queue q;//定义队列 QueueInit(&q);//初始化队列 if (root) { QueuePush(&q, root);//将根节点入队 while (!QueueEmpty(&q))//队列不为空就继续 { BTNode* front = QueueFront(&q);//取出根节点 QueuePop(&q);//根节点出队——节点还在 printf("%c ", front->data); if (front->left) { QueuePush(&q, front->left); } if (front->right) { QueuePush(&q, front->right); } } printf("\n"); QueueDestory(&q); } } 

包含队列的总代码如下：

Queue.h

#pragma once #include<stdio.h> #include<Stdlib.h> #include<assert.h> #include<stdbool.h> //前置声明——防止报错 struct BinaryTreeNode;//声明BinaryTreeNode为一个结构体，具体使用时再调用 typedef struct BinaryTreeNode* QDataType;//队列的数据类型定义为树的的节点结构体类型 //数据类型 //typedef int QDataType; //一个节点 typedef struct QueueNode { QDataType data; //存储数据 struct QueueNode* next; //记录下一个节点 }QNode; //保存队头和队尾 typedef struct Queue { QNode* head; //头指针 QNode* tail; //尾指针 }Queue; //初始化队列 void QueueInit(Queue* pq); //销毁队列 void QueueDestory(Queue* pq); //入队 void QueuePush(Queue* pq, QDataType x); //出队 void QueuePop(Queue* pq); //判空 bool QueueEmpty(Queue* pq); //获取有效元素个数 size_t QueueSize(Queue* pq); //获取队头元素 QDataType QueueFront(Queue* pq); //获取队尾元素 QDataType QueueBack(Queue* pq);

Queue.c

#include"Queue.h" //初始化队列 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } //销毁队列 void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL;//指针置空 } //入队 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建一个新节点 assert(newnode); newnode->next = NULL; newnode->data = x; if (pq->tail == NULL)//空队列则两其头尾均指向新节点 { assert(pq->head == NULL); pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } } //出队 void QueuePop(Queue* pq) { assert(pq); assert(pq->head && pq->tail);//头尾均不能为空 if (pq->head->next == NULL)//当只有一个节点时 { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } } //判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL;//队列为空返回0 } //获取有效元素个数 size_t QueueSize(Queue* pq) { assert(pq); QNode* cur = pq->head; size_t size = 0; while (cur) { size++; cur = cur->next; } return size; } //获取队头元素 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head);//头不能为空才可以获取头部数据 return pq->head->data; } //获取队尾元素 QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->tail); return pq->tail->data; }

Test.c

#include<stdio.h> #include<stdlib.h> #include "Queue.h" //一个二叉树节点结构 typedef char BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNOde* right; BTDataType data; }BTNode; //层序遍历 void LevelOrder(BTNode* root) { Queue q;//定义队列 QueueInit(&q);//初始化队列 if (root) { QueuePush(&q, root);//将根节点入队 while (!QueueEmpty(&q))//队列不为空就继续 { BTNode* front = QueueFront(&q);//取出根节点 QueuePop(&q);//根节点出队——节点还在 printf("%c ", front->data); if (front->left) { QueuePush(&q, front->left); } if (front->right) { QueuePush(&q, front->right); } } printf("\n"); QueueDestory(&q); } } int main() { //创建节点 BTNode* A = (BTNode*)malloc(sizeof(BTNode)); A->data = 'A'; A->left = NULL; A->right =NULL; BTNode* B = (BTNode*)malloc(sizeof(BTNode)); B->data = 'B'; B->left = NULL; B->right = NULL; BTNode* C = (BTNode*)malloc(sizeof(BTNode)); C->data = 'C'; C->left = NULL; C->right = NULL; BTNode* D = (BTNode*)malloc(sizeof(BTNode)); D->data = 'D'; D->left = NULL; D->right = NULL; BTNode* E = (BTNode*)malloc(sizeof(BTNode)); E->data = 'E'; E->left = NULL; E->right = NULL; //将节点链接起来 A->left = B; A->right = C; B->left = D; B->right = E; LevelOrder(A); return 0; }

6. 计算二叉树的节点数目和叶子节点数目

计算二叉树节点个数：

有两种方法，一种是递归方法，一种是遍历方法。

递归方法：

//分治思想计算节点个数 int TreeSize(BTNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; }

递归的方法比较难理解，一般画递归分解图，主要思想就是每次递归都会带回来一个数。

遍历方法：

遍历方法需要定义一个变量size，每次遍历一个节点size加一。

//遍历计算节点个数 void TreeSize(BTNode* root, int* psize) { if (root == NULL) { return; } else { ++(*psize); } TreeSize(root->left, psize); TreeSize(root->right, psize); }

计算叶子节点个数：

采用递归方法，只有当左右子树均为空时才返回1

//计算叶子节点个数 int TreeLeafSize(BTNode* root) { //空树为0 if (root == NULL) { return 0; } //一个节点为1 if (root->left == NULL && root->right == NULL) return 1; return TreeLeafSize(root->left) + TreeLeafSize(root->right); }