树(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个结点的完全二叉树的深度为⌊log2n⌋+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://cdkjz.cn/article/codjic.html
