树的基本性质和概念
1.p = q +1 ;(其中p为顶点,q为边)
2.结点的度:子树的个数,
树的度:结点度的最大值
3.连通且无圈
由于所有的树都可以转化为二叉树,下列出二叉树的性质
二叉树的性质
1.结点数的最值问题:
(1)第i层的结点数最多为 :2^(i-1)
(2)深度为k的二叉树中,结点数最多为:2^k - 1
2.叶子结点个数 与 度为2的结点的数量关系:
(1)n0=n2+1;
3.数组存储二叉树:
(1)数据结构:datatype bitree[n] :
(2)其中bitree[0]为空结点,则bitree[ i ]的左子结点为bitree[ 2i ],bitree[ i ]的右子结点为bitree[ 2i +1]。
4.链表存储二叉树:
(1)数据结构:
typedef struct Node
{
Datatype data;
struct Node *lchild;
struct Node *rchild;
}bitnode,*bitree;
(2)设结点数为n,边 = 结点数 - 1(即n-1),指针数 = 结点数 * 2 (即2*n);
则空指针的个数 = n+1。(与线索化有关)
二叉树的创建(以先序递归为例)
二叉树创建涉及的知识点
1.关于指针的使用
2.递归的理解
方法一:
传入指向指针的指针**(函数中传递的是形参,函数会新创建一个指针,与主函数中的指针并未改变)**
main函数
bitnode *T;
printf("先序递归创建\n");
createtree(&T);
调用函数
void createtree(bitnode **T)
{
Datatype ch;
scanf("%c",&ch);
while(getchar()!='\n');
if(ch=='#')
*T=NULL;
else
{
*T=(bitnode*)malloc(sizeof(bitnode));
(*T)->data=ch;
createtree(&((*T)->lchild));
createtree(&((*T)->rchild));
}
}
或者写成下面代码
void createtree(bitree *t)
{
Datatype ch;
scanf("%c",&ch);
while(getchar()!='\n');
if(ch==0)
*t=NULL;
else
{
*t=(bitree)malloc(sizeof(bitnode));
(*t)->ch=ch;
createtree(&((*t)->lchild));
createtree(&((*t)->rchild));
}
}
方法二
不传递参数,改为返回地址的方式
bitnode* createtree()
{
bitnode *t;
char x;
scanf("%c",&x);
while(getchar()!='\n');
if(x=='#')
t=NULL;
else
{
t=(bitnode*)malloc(sizeof(bitnode));
t->data=x;
t->lchild=createtree();
t->rchild=createtree();
}
return t;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)