类似凡科建站的网站,移动外包公司要不要去,WordPress制作小说网站,厦门seo顾问个人主页#xff1a;仍有未知等待探索_C语言疑难,数据结构,小项目-CSDN博客 专题分栏#xff1a;数据结构_仍有未知等待探索的博客-CSDN博客 一、前言
树形结构是一类非常重要的非线性结构。树形结构是节点之间有分支#xff0c;并且具有层次关系的结构#xff0c;它类似于… 个人主页仍有未知等待探索_C语言疑难,数据结构,小项目-CSDN博客 专题分栏数据结构_仍有未知等待探索的博客-CSDN博客 一、前言
树形结构是一类非常重要的非线性结构。树形结构是节点之间有分支并且具有层次关系的结构它类似于自然界中的树。
就比如说电脑中磁盘中的文件储存方式就类似于一颗树。
二、树的定义和基本的术语
在讲二叉树之前我们要先讲树的定义和树的一些术语。
1、树的定义 树是nn0个结点的有限集T为空时称为空树。 非空树的特点 T中有且仅有一个结点K没有前驱称K为树的根结点。除了根结点以外其余节点有且仅有一个直接前驱。T中各结点可以有0个或者多个后继。除了根节点以外其余结点可以分为m个互不相干的有限集合。 2、树的基本术语 一个节点拥有的子树个数称为结点的度。度为零的结点称为叶子节点。树的度是树中所有结点的度的最大值。结点子树的根称为孩子结点该结点称为其双亲结点。结点的祖先是从跟到该结点所经分支上的所有结点。某一结点的子孙是以该结点为根的子树上的任一结点。结点的层次根为第一层以此类推。树中最大的层次叫做树的深度高度。树中结点的个子树可以看作是从左到右有次序的称为有序树反之无序树。森林是mm0棵互不相交的树的集合。 三、二叉树
1、二叉树的5种基本形态 2、二叉树的两种特殊形态
1满二叉树 每层结点都是满的即满二叉树的每层上的结点数都是最大结点数。 一共有2^n-1个结点n为树的高度 下图是高度为4的满二叉树 2完全二叉树 最多只有一个度为1的结点。 序号和满二叉树的一样。 3、二叉树的性质 在二叉树的第i层上至多有 2^i - 1 个结点 i 1 。深度为k的二叉树至多有 2^k - 1 个结点 k 1 。设n0、n1、n2分别为度为012的结点则 n0n21 。具有n个结点的完全二叉树的深度 [log2n]1 。n个完全二叉树按照层序编号i1其结点为根节点。若 i 1i/2 为其结点的双亲结点2*i 为其左孩子的编号2*i n 无左孩子 2*i1为其右孩子的编号 2*i 1 n 无右孩子。 4、二叉树的存储结构
1顺序存储结构
#define MAX 100
typedef 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 100
void 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 ? dl : dr;//求树的高度return d 1;
} 7、求叶子结点的个数 叶子节点的个数左子树的叶子节点的个数右子树的叶子节点的个数 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;//如果mkbt没有左孩子if (m k)bt-left NULL;elsebt-left PreInBiTreeCreate(Pre, In, i 1, i m - k, k, m - 1);//如果mhbt没有右孩子if (m h)bt-right NULL;elsebt-right PreInBiTreeCreate(Pre, In, i m - k 1, j, m 1, h);
} 谢谢大家的支持
