二叉树的定义及基本操作

末蓝、 2022-08-19 00:27 92阅读 0赞

（1）定义二叉树的链式存储结构；

（2）建立一颗二叉链表表示的二叉树；

（3）对其进行前序，中序（非递归），后序输出。

（4）统计二叉树中叶子结点个数和度为2的结点个数。

创建的二叉树为：

![Image 1][]

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #define OK 1
    #define ERROR 0
    #define OVERFLOW 0
    #define STACK_INIT_SIZE 100
    #define STACKINCREMENT 10
    typedef char TElemType;
    typedef int Status;
    //定义二叉链表的结点结构
    typedef struct BiTNode { // 结点结构                            
     TElemType data;
     struct BiTNode  *lchild, *rchild; //左右孩子指针
    } BiTNode, *BiTree;
    typedef BiTree SElemType;
    typedef struct{
     SElemType *base;  //栈底指针
     SElemType *top;   //栈顶指针
     int stacksize;    //栈的容量
    }SqStack; //定义一个顺序栈
    
    Status InitStack(SqStack &S){
     S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
     if (!S.base){
      printf("栈溢出！\n");
      exit(OVERFLOW);
     }
     S.top = S.base;
     S.stacksize = STACK_INIT_SIZE;
     return OK;
    }//初始化一个顺序栈
    
    Status StackEmpty(SqStack S){
     if (S.top == S.base){
      return OK;
     }
     return ERROR;
    }//判断一个栈是否为空
    
    //往栈里面插入元素e
    Status Push(SqStack &S, BiTree p){
     if (S.top - S.base >= S.stacksize){
      S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
      if (!S.base){
       printf("栈溢出!\n");
       return OVERFLOW;
      }
      S.top = S.base + S.stacksize;
      S.stacksize += STACKINCREMENT;
     }//若栈满，追加存储空间
     *S.top++ = p;
     return OK;
    }
    
    //删除栈顶元素，用指针p返回栈里存放的根指针
    Status Pop(SqStack &S, BiTree &p){
     if (StackEmpty(S))
      return ERROR; //判空
     p = *(--S.top);
     return OK;
    }
    Status CreateBiTree(BiTree &T)
    {//按先序次序输入二叉树中结点的值，空格字符表示空树，构造二叉链表表示的二叉树T。
    char ch;
    scanf("%c",&ch);
    if(ch==' ')T=NULL;
    else{
    	if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
    		exit(OVERFLOW);
    	T->data=ch;      //生成根结点
    	CreateBiTree(T->lchild);//构造左子树
    	CreateBiTree(T->rchild);//构造右子树
    }
    return OK;
    }
    
    Status PrintElement(TElemType e)
    	{
    		printf("%c",e)//输出元素e的值;
    		return OK;
    	}
    Status PreOrderTraverse(BiTree T,Status(* Visit)(TElemType e))
    {//采用二叉链表存储结构，Visit是对数据元素操作的应用函数
    	//先序遍历二叉树T的递归算法，对每个数据元素调用Visit函数
    	if(T){
    		if(Visit(T->data))
    			if(PreOrderTraverse(T->lchild,Visit))
    				if(PreOrderTraverse(T->rchild,Visit)) return OK;
    				return ERROR;
    				}
    	else return OK;
    }
    Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e))
    {//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit
    	SqStack S;
    	InitStack(S);
    	BiTree p=T;
    	while(p||!StackEmpty(S))
    	{
    		if(p)
    		{
    			Push(S,p);
    			p=p->lchild;//根指针进栈，遍历左子树
    		}else
    		{//根指针退栈，访问根结点，遍历右子树
    			Pop(S,p);
    			if(!Visit(p->data))
    				return ERROR;
    			p=p->rchild;
    		}
    	}
    	return OK;
    }
    Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e))
    {//后序遍历二叉树T的递归算法，对每个数据元素调用Visit函数
    
    	if(T){
    			if(PreOrderTraverse(T->lchild,Visit))
    				if(PreOrderTraverse(T->rchild,Visit))
    					if(Visit(T->data))return OK;
    				return ERROR;
    				}
    	else return OK;
    }
    void CountLeaf(BiTree T,int& count)
    {//计算叶子结点数
    	if(T)
    	{
    		if((!T->lchild)&&(!T->rchild))
    			count++;
    		CountLeaf(T->lchild,count);
    		CountLeaf(T->rchild,count);
    	}
    }
    void Count(BiTree T,int& n2)
    {//计算度为2的结点数
    	if(T)
    	{
    		if((T->lchild)&&(T->rchild))
    			n2++;
    		Count(T->lchild,n2);
    		Count(T->rchild,n2);
    	}
    }
    int main()
    {
    	int n0=0,n2=0;
    	BiTree T;
    	printf("按先序次序输入一个二叉树的结点值：\n");
    	if(CreateBiTree(T))
    	{
    		printf("创建二叉树成功\n");
    	}
    	else
    		printf("创建二叉树失败\n");
    	printf("先序遍历结果为：\n");
    	if(PreOrderTraverse(T,PrintElement))
    	{
    		printf("\n");
    	}
    	else
    		printf("遍历失败\n");
    	printf("中序遍历结果为：\n");
    	if(InOrderTraverse(T,PrintElement))
    	{
    		printf("\n");
    	}
    	else
    		printf("遍历失败\n");
    		printf("后序遍历结果为：\n");
    	if(PostOrderTraverse(T,PrintElement))
    	{
    		printf("\n");
    	}
    	else
    		printf("遍历失败\n");
    	CountLeaf(T,n0);
    		printf("叶子的结点数位：%d\n",n0);
    	Count(T,n2);
    	printf("度为2的结点个数为：%d\n",n2);
    	return 0;
    }

[Image 1]: