二叉树的创建（C语言）

树的基本性质和概念

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;
1
2
3
4
5

(2)设结点数为n，边 = 结点数 - 1（即n-1），指针数 = 结点数 * 2 （即2*n）；
则空指针的个数 = n+1。（与线索化有关）

二叉树的创建（以先序递归为例）

二叉树创建涉及的知识点
1.关于指针的使用
2.递归的理解

方法一：

传入指向指针的指针**（函数中传递的是形参，函数会新创建一个指针，与主函数中的指针并未改变）**

main函数

 bitnode *T;
 printf("先序递归创建\n"); 
 createtree(&T); //这里传入指针的地址
1
2

调用函数

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));
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

或者写成下面代码

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));
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法二

不传递参数，改为返回地址的方式

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16