大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

树和二叉树的性质结构-创新互联

树(Tree):是n(n>=0)个结点的有限集。当n=0时为空树。

创新互联主要从事网站设计制作、做网站、网页设计、企业做网站、公司建网站等业务。立足成都服务馆陶,十多年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:028-86922220

森林(Forest):是m(m>=0)棵互不相交的树的集合。

树的存储结构:

双亲表示法

//双亲结点表示法
#define MAX_TREE_SIZE 100

typedef int ElemType;

typedef struct PTNode
{ElemType data;  //结点数据
    int parent;   //双亲位置
}PTNode;

typedef struct
{PTNode nodes[MAX_TREE_SIZE];
    int r;  //根的位置
    int n;  //结点数目
}PTree;

双亲孩子表示法

#define MAX_TREE_SIZE 100

typedef char ElemType;

//孩子结点
typedef struct CTNode
{int child;  //孩子结点的下标
    struct CTNode *next;  //指向下一个孩子结点的指针
}*ChildPtr;

//表头结构
typedef struct
{ElemType data;  //存放在树中的结点的数据
    int parent;    //存放双亲的下标
    ChildPtr firstchild;  //指向第一个孩子的指针
}CTBox;

//树结构
typedef struct
{CTBox nodes[MAX_TREE_SIZE];  //结点数组
    int r,n;
}

二叉树的定义:是n(n>=0)个结点的有限集合,该集合或者为空集,或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

二叉树的五种基本形态

空二叉树

只有根节点的二叉树

根节点只有左子树

根节点只有右子树

根节点既有左子树又有右子树

特殊二叉树

满二叉树:所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上。

请添加图片描述

完全二叉树:是一个深度为k的有n个节点的二叉树,对树中的节点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同。

特点:

  • 叶子结点只能出现在最下两层。
  • 最下层的叶子一定集中在左部连续位置。
  • 倒数第二层,若有叶子结点,一定都在右部连续位置。
  • 如果结点度为1,则该结点只有左孩子。
  • 同样结点的二叉树,完全二叉树深度最小。

注:满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树。

二叉树的性质

在二叉树的第 i 层上至多有 2 i − 1 个结点 ( i > = 1 ) 深度为 k 的二叉树至多有 2 k − 1 个结点 ( k > = 1 ) 对于任何一棵二叉树 T ,如果其终端结点数为 n 0 ,度为 2 的结点数为 n 2 ,则 n 0 = n 2 + 1 具有 n 个结点的完全二叉树的深度为 ⌊ l o g 2 n ⌋ + 1 如果对一棵有 n 个结点的完全二叉树的结点按层序编号,对任一结点 i ( 1 < = i < = n ) 有以下性质: − 如果 i = 1 ,则结点 i 是二叉树的根,无双亲;如果 i > 1 ,则其双亲是结点 ⌊ i / 2 ⌋ − 如果 2 i > n ,则结点 i 无左孩子 ( 结点 i 为叶子结点 ) ;否则其左孩子是 2 i − 如果 2 i + 1 > n ,则结点 i 无右孩子;否则其右孩子是结点 2 i + 1 \begin{align} &在二叉树的第i层上至多有2^{i-1}个结点(i>=1)\\ &深度为k的二叉树至多有2^k-1个结点(k>=1)\\ &对于任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1\\ &具有n个结点的完全二叉树的深度为\lfloor log_2n \rfloor+1\\ &如果对一棵有n个结点的完全二叉树的结点按层序编号,对任一结点i(1<=i<=n)有以下性质:\\ &- 如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲是结点\lfloor i/2 \rfloor\\ &- 如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是2i\\ &- 如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1 \end{align} ​在二叉树的第i层上至多有2i−1个结点(i>=1)深度为k的二叉树至多有2k−1个结点(k>=1)对于任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1具有n个结点的完全二叉树的深度为⌊log2​n⌋+1如果对一棵有n个结点的完全二叉树的结点按层序编号,对任一结点i(1<=i<=n)有以下性质:−如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲是结点⌊i/2⌋−如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是2i−如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1​​

二叉树的存储结构

请添加图片描述

二叉链表

typedef struct BiTNode
{ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
二叉树的遍历

前序遍历

请添加图片描述

中序遍历

请添加图片描述

后序遍历

请添加图片描述

层序遍历

请添加图片描述

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


分享题目:树和二叉树的性质结构-创新互联
链接分享:http://dzwzjz.com/article/codjic.html
在线咨询
服务热线
服务热线:028-86922220
TOP