二叉树的二叉链表存储结构的建立及操作的实现_二叉链表的存储和基本操作的实现

什么是二叉树呢？

二叉树是n(n>=0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成（递归定义）
特点：
1）每个结点至多有二棵子树(即不存在度大于2的结点)
2）二叉树的子树有左、右之分，且其次序不能任意颠倒

二叉树的二叉链表存储结构的定义

typedef struct BiTNode { // 结点结构
    TElemType      data;
    struct BiTNode  *lchild, *rchild;   // 左右孩子指针
} BiTNode, *BiTree;

1
2
3
4
5

构建二叉树

//构建二叉树

void CreateBiTree(BiTree &T)
{//按先序次序输入二叉树中结点的值，创建二叉链表表示的二叉树T
	
	TElemType n;
	scanf("%d",&n);
	if(n==0)//递归结束条件
	{
		T=NULL;	
	}
	else
	{
		T = new BiTNode;//生成根节点
		T->data = n;
		CreateBiTree(T->lchild);//递归创建左子树
		CreateBiTree(T->rchild);//递归创建右子树
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

遍历二叉树

先序遍历

若二叉树为空树，则空操作；否则，
（1）访问根结点；
（2）先序遍历左子树；
（3）先序遍历右子树。

递归算法

void PreOrderTraverse (BiTree T)
{ // 先序遍历二叉树 ，假设遍历是输出结点的值
   if (T) 
    {
       printf(T->data); // 访问根结点 , visit(T->data);  
       PreOrderTraverse(T->lchild ); //先序遍历左子树
       PreOrderTraverse(T->rchild );//先序遍历右子树
     }
}
1
2
3
4
5
6
7
8
9

非递归算法

void PreOrderTraverse (BiTree T)
{ // 先序遍历二叉树的非递归算法
  InitStack(S);   Push(S,T);
  while (! StackEmpty(S))
   {  while(GetTop(S, P)&&P)
        {printf(P->data); Push(S, P->lchild);}
      Pop(S,P)；   //空指针出栈
      if(! StackEmpty(S)) 
        {  Pop(S,P);  
           Push(S,P->rchild);
        }//if
   }//while
Destroy(S);
 }// PreOrderTraverse
1
2
3
4
5
6
7
8
9
10
11
12
13
14

中序遍历

若二叉树为空树，则空操作；否则，
（1）中序遍历左子树；
（2）访问根结点；
（3）中序遍历右子树。

递归算法

void InOrderTraverse (BiTree T  )
{ // 中序遍历二叉树 
   if (T) 
    {
       InOrderTraverse(T->lchild ); //中序遍历左子树
        printf (T->data);            // 访问根结点     
        InOrderTraverse(T->rchild ); //中序遍历右子树
    }    
}// InOrderTraverse
1
2
3
4
5
6
7
8
9

非递归算法

void InOrderTraverse (BiTree T   )    //P124
{ // 中序遍历二叉树 的非递归算法
  InitStack(S);   Push(S,T);
  while (! StackEmpty(S))
   {  while(GetTop(S, P)&&P) Push(S, P->lchile);
       Pop(S,P);       //空指针出栈
       if(! StackEmpty(S))  
        {  Pop(S,P); 
            printf (P->data);   //访问结点
           Push(S,P->rchild);
        }//if
   }//while
 Destroy(S);
}// InOrderTraverse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

后序遍历

若二叉树为空树，则空操作；否则，
（1）后序遍历左子树；
（2）后序遍历右子树；
（3）访问根结点。

递归算法

void  PostOrderTraverse (BiTree T)
{ // 后序遍历二叉树 
   if (T)
    {  
      PostOrderTraverse(T->lchild ); //后序遍历左子树
       PostOrderTraverse(T->rchild );//后序遍历右子树
      printf (T->data);            // 访问根结点
     }
}//PostOrderTravers

1
2
3
4
5
6
7
8
9
10

非递归算法

void PostOrderTraverse (BiTree  T)
{ // 后序遍历二叉树 的非递归算法
  InitStack(S);  //栈元素的类型为
   Pt=T; 
   while(Pt||StackEmpty(S))
     {  
       if (Pt)    { Push(S,(Pt,0)); Pt=Pt->lchild; }
       else  { Pop(S,P) ; 
                  if( P.Tag==0)
                      { P.Tag=1;Push(S,P); Pt=P.Bit->rchild;}
                  else {printf(P.Bit->data) ; Pt==NULL;}
                 }
     }
 Destroy(S);
}// PostOrderTraverse
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

求二叉树的深度

//求二叉树的深度
int Depth(BiTree T)
{
	TElemType m,n;
	if(T==NULL)
		return 0;
	else
	{
		m = Depth(T->lchild);
		n = Depth(T->rchild);
		return (m > n ? m : n)+1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

求二叉树中结点个数

//求二叉树中结点个数
int NodeCount(BiTree T)
{
	if(T==NULL)
		return 0;
	else
		return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
1
2
3
4
5
6
7
8

求二叉树中叶子结点个数

//求二叉树中叶子结点个数
int LeaveCount(BiTree T)
{
	if(T==NULL)
		return 0;
	else if(!T->lchild&&!T->rchild)//只要有一个子树为空，就返回1
		return 1;
	else
		return (LeaveCount(T->lchild)+LeaveCount(T->rchild));
}
1
2
3
4
5
6
7
8
9
10

求二叉树中度为1的结点个数

//求二叉树中度为1的结点个数
int NodeCount_1(BiTree T)
{
	if(T==NULL)
		return 0;
	else if(!T->lchild&&T->rchild||T->lchild&&!T->rchild)
		return (NodeCount_1(T->lchild)+NodeCount_1(T->rchild))+1;
	else
		return (NodeCount_1(T->lchild)+NodeCount_1(T->rchild));
}
1
2
3
4
5
6
7
8
9
10

主函数实现

int main(){
	BiTree T;
	int option,depth,Lcount,Ncount,N_1count;
	while(true){
		printf("\n--二叉树的二叉链表--\n--功能如下--\n");
		printf("1.构建\n2.中序遍历\n3.求深度\n4.求叶子结点个数\n5.求结点个数\n6.求度为1的结点个数\n7.退出\n请输入序号：");
		scanf("%d",&option);
		switch(option){
			case 1:
				CreateBiTree(T);
				printf("二叉树创建成功。\n");
				break;
			case 2:
				InOrderTraverse(T);
				break;
			case 3:
				depth=Depth(T);
				printf("二叉树的深度为：%d\n",depth);
				break;
			case 4:
				Lcount=LeaveCount(T);
				printf("二叉树的叶子结点个数为：%d\n",Lcount);
				break;
			case 5:
				Ncount=NodeCount(T);
				printf("二叉树的结点个数为：%d\n",Ncount);
				break;
			case 6:
				N_1count=NodeCount_1(T);
				printf("二叉树的度为1的结点个数为：%d\n",N_1count);
				break;
			case 7:
				exit(0);
			default:
				printf("输入的指令有误，请重新输入！\n");
		}
	
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39