首页 > 代码库 > 二叉树的定义和实现
二叉树的定义和实现
/*
1.节点:节点包括一个数据元素及若干指向其子树的分支
2.节点的度:节点所拥有的子树的个数成为该节点的度
3.叶节点:度为0的节点称为叶结点
4.分支节点:度不为0的节点称为分支节点
5.树的度:树中所有节点的度的最大值
6.二叉树:是n(n>=0)个有限节点构成的集合。n=0的树称为空二叉树;n=1的树只有一个根结点;
n〉1的二叉树由一个根节点和至多两个互不相交的,分别称为左子树和右子树的子二叉树构成
二叉树不是有序树,这是因为,二叉树中某个节点即使只有一个子树也要区分是左子树还是右子树;
而对于有序树来说,如果某个节点只有一个子树就必定是第一个子树
7.二叉树所有结点的形态有5种:空节点,无左右子树节点,只有左子树节点,只有右子树节点和左右子树均存在的节点
8.满二叉树:在一棵二叉树中,如果所有分支节点都存在左子树和右子树,并且所有叶子节点都在同一层,则这样的二叉树称作满二叉树
9.完全二叉树:如果一颗具有n个节点的二叉树的结构与满二叉树的前n个节点的结构相同,这样的二叉树称为完全二叉树
10二叉树的性质:
(1):若规定根节点的层数为0,则一棵非空二叉树的第i层上最多有2^i(i>=0)个节点
(2):
若规定只有根节点的二叉树的深度为0,则深度为k的二叉树的最大节点数是2^(k+1)-1(k>=-1)
(3):
对于一棵非空的二叉树,如果叶节点个数为n0,度为2的节点个数为n2,则有n0=n2+1
(4):
具有n个节点的完全二叉树的深度k为大于或等于ln(n+1)-1的最小整数
(5):
对于具有n个节点的完全二叉树,如果按照从上至下和从左至右的顺序对所有节点序号从0开始顺序编号,则对于序号为i(0<=i<n)的节点有:
如果i〉0,则序号为i节点的双亲节点的序号为(i-1)/2(/为整除);如果i=0,则序号为i节点为根节点,无双亲节点
如果2i+1<n,则序号为i节点的左孩子节点的序号为2i+1;如果2i+1>=n,则序号为i节点无左孩子
如果2i+2<n,则序号为i节点的右孩子节点的序号为2i+2;如果2i+2>=n,则序号为i节点无右孩子
11.二叉树的存储结构
1.二叉树的顺序存储结构
利用性质5,对于完全二叉树可以利用一维数组存储,如果不是完全二叉树,则可以补空节点,使成为完全二叉树在进行存储,
但是对于非完全二叉树,可能要浪费很多的空间。
2.二叉树的链式存储结构
二叉树的链式存储结构就是用指针建立二叉树中节点之间的关系,二叉树最常用的链式存储结构是二叉链。二叉树的二叉链存储结构是一种常用的
二叉树存储结构。二叉链存存储结构的优点时,结构简单,可以方便的构造任何形状的二叉树,并可以方便的实现二叉树的大多数操作。
二叉链存储结构的缺点是,查找当前节点的双亲节点操作实现比较麻烦
3.二叉树的仿真指针存储结构
利用一维数组和结构体实现,利用数组的下标进行仿真指针进行二叉树的操作
*/
<span style="font-size:18px;">#include<stdio.h> #include<malloc.h> typedef char DataType; typedef struct Node{ DataType data;//数据域 struct Node *leftChild;//左子树指针 struct Node *rightChild;//右子树指针 }BiTreeNode;//节点的结构体定义 //初始化 void Initiate(BiTreeNode **root){ *root=(BiTreeNode *)malloc(sizeof(BiTreeNode)); (*root)->leftChild=NULL; (*root)->rightChild=NULL; } //左插入节点 //若当前节点curr非空,则在curr的左子树插入元素值为x的新节点 //原curr所指节点的左子树成为新插入节点的左子树 //若插入成功,则返回新插入节点的指针,否则返回空指针 BiTreeNode *InsertLeftNode(BiTreeNode *curr,DataType x){ BiTreeNode *s,*t; if(curr==NULL){//判断当前节点是否为空 return NULL;//是空则返回NULL } t=curr->leftChild;//保存原curr所指节点的左子树 s=(BiTreeNode *)malloc(sizeof(BiTreeNode));//创建节点空间 s->data=http://www.mamicode.com/x;//赋值>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。