个人主页:仍有未知等待探索_C语言疑难,数据结构,小项目-CSDN博客

专题分栏:数据结构_仍有未知等待探索的博客-CSDN博客

一、前言

树形结构是一类非常重要的非线性结构。树形结构是节点之间有分支,并且具有层次关系的结构,它类似于自然界中的树。

就比如说:电脑中磁盘中的文件储存方式就类似于一颗树。

二、树的定义和基本的术语

在讲二叉树之前,我们要先讲树的定义和树的一些术语。

1、树的定义

树是n(n>=0)个结点的有限集,T为空时称为空树。

非空树的特点:

  • T中有且仅有一个结点K,没有前驱,称K为树的根结点。
  • 除了根结点以外,其余节点有且仅有一个直接前驱。
  • T中各结点可以有0个或者多个后继。
  • 除了根节点以外,其余结点可以分为m个互不相干的有限集合。

2、树的基本术语

  • 一个节点拥有的子树个数称为结点的度
  • 度为零的结点称为叶子节点
  • 树的度是树中所有结点的度的最大值。
  • 结点子树的根称为孩子结点,该结点称为其双亲结点
  • 结点的祖先是从跟到该结点所经分支上的所有结点。
  • 某一结点的子孙是以该结点为根的子树上的任一结点。
  • 结点的层次:根为第一层,以此类推。
  • 树中最大的层次叫做树的深度(高度)
  • 树中结点的个子树可以看作是从左到右有次序的,称为有序树,反之无序树
  • 森林是m(m>=0)棵互不相交的树的集合。

三、二叉树

1、二叉树的5种基本形态

2、二叉树的两种特殊形态

(1)满二叉树

每层结点都是满的,即满二叉树的每层上的结点数都是最大结点数。

一共有2^n-1个结点(n为树的高度)

下图是高度为4的满二叉树

(2)完全二叉树

最多只有一个度为1的结点。

序号和满二叉树的一样。

3、二叉树的性质

  1. 在二叉树的第i层上至多有 2^i – 1 个结点( i >= 1 )。
  2. 深度为k的二叉树至多有 2^k – 1 个结点( k >= 1 )。
  3. 设n0、n1、n2分别为度为0,1,2的结点,则 n0=n2+1
  4. 具有n个结点的完全二叉树的深度[log2n]+1
  5. n个完全二叉树,按照层序编号,i=1,其结点为根节点。若 i > 1,i/2 为其结点的双亲结点,2*i 为其左孩子的编号(2*i > n 无左孩子), 2*i+1为其右孩子的编号(2*i +1 > n 无右孩子)。

4、二叉树的存储结构

(1)顺序存储结构

#define MAX 100typedef int BT;struct BiTree{BT tree[MAX];int n;};

(2)链式存储结构

// 二叉链树typedef int TreeNodeType;struct Bitree{TreeNodeType data;struct Bitree* left, *right;};
// 三叉链树typedef int TreeNodeType;struct Bitree{TreeNodeType data;struct Bitree* left, * right;struct Bitree* parent;};

5、二叉树的遍历

(1)先序遍历

遍历的顺序是:根结点、左结点、右结点。

就比如上图的先序遍历是:A B D E C F

void PreOrder(BiTree bt){//如果bt为空的话,就退出。if (bt == NULL)return;visit();//访问根节点PreOrder(bt->left);//先序遍历左子树,递归调用PreOrder(bt->right);//先序遍历右子树,递归调用}

(2)中序遍历

遍历的顺序是:左结点、根节点、右结点。

上图的中序遍历是:D B E A F C

void InOrder(BiTree bt){//如果bt为空的话,就退出。if (bt == NULL)return;InOrder(bt->left);//中序遍历左子树,递归调用visit();//访问根节点InOrder(bt->right);//中序遍历右子树,递归调用}

(3)后序遍历

遍历的顺序是:左结点、右结点、根节点。

上图的后序遍历是:D E B F C A

void PostOrder(BiTree bt){//如果bt为空的话,就退出。if (bt == NULL)return;PostOrder(bt->left);//中序遍历左子树,递归调用PostOrder(bt->right);//中序遍历右子树,递归调用visit();//访问根节点}

(4)层序遍历

层序遍历的顺序:按二叉树从上到下,从左到右依次访问每个节点中存储的数据。

上图的层序遍历是:A B C D E F

#define MAX 100void LevelOrder(BiTree bt){if (bt == NULL)return;//队列BiTree Queue[MAX] = { 0 };int front = 0, rear = 0;//根节点入队Queue[rear] = bt;rear = (rear + 1) % MAX;while (rear != front){//访问队内第一个元素visit(Queue[front]);//如果队内第一个元素的左孩子不为空的话,入队if (Queue[front]->left != NULL){Queue[rear] = Queue[front]->left;rear = (rear + 1) % MAX;}//如果队内第一个元素的右孩子不为空的话,入队if (Queue[front]->right != NULL){Queue[rear] = Queue[front]->right;rear = (rear + 1) % MAX;}//队内第一个元素出队front = (front + 1) % MAX;}}

6、求二叉树的高度(深度)

用递归的思想:将一个大问题转化为具有相同性质的小问题。

二叉树的高度=max(左子树的高度,右子树的高度)

int BiTreeDepth(BiTree bt){if (bt == NULL){return 0;}int dl = 0, dr = 0, d = 0;dl = BiTreeDepth(bt->left);//求左子树的高度dr = BiTreeDepth(bt->right);//求右子树的高度d = dl > dr " />叶子节点的个数=左子树的叶子节点的个数+右子树的叶子节点的个数

int BiTreeLeaf(BiTree bt){//如果为空树,叶子结点为0if (bt == NULL)return 0;//判断是否是叶子结点if (bt->left == NULL && bt->right == NULL)return 1;//返回总数return (BiTreeLeaf(bt->left) + BiTreeLeaf(bt->right));}

8、根据先序序列和中序序列创建二叉树

也可以根据后序序列和中序序列来进行创建二叉树

//根结点BiTree bt = NULL;BiTree PreInBiTreeCreate(int Pre[], int In[], int i, int j, int k, int h){//开辟空间bt = (BiTree)malloc(sizeof(struct BiTree));assert(bt);//将根结点的数据放入结构体中bt->data = Pre[i];bt->left = NULL;bt->right = NULL;int m = k;//找根结点的位置while (Pre[i] != In[m])m++;//如果m==k,bt没有左孩子if (m == k)bt->left = NULL;elsebt->left = PreInBiTreeCreate(Pre, In, i + 1, i + m - k, k, m - 1);//如果m==h,bt没有右孩子if (m == h)bt->right = NULL;elsebt->right = PreInBiTreeCreate(Pre, In, i + m - k + 1, j, m + 1, h);}

谢谢大家的支持!