精华内容
下载资源
问答
  • 采用二叉链表结构实现二叉树,并以递归遍历思想实现二叉树的创建二叉树的遍历(先序、中序、后序和层次遍历)、.../*①二叉树的二叉链表存储结构定义*/ typedef struct BiTNode { ElemType data; struct BiTNode *l

    采用二叉链表结构实现二叉树,并以递归遍历思想实现二叉树的创建、二叉树的遍历(先序、中序、后序和层次遍历)、二叉树叶子节点统计、二叉树深度统计的算法;同时,结合课件和实例代码,实现二叉树的中序非递归遍历算法。存储结构和操作接口定义如下:

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

    typedef struct BiTNode

    {

    ElemType data;

    struct BiTNode *lchild,*rchild;      //左右孩子指针

    }BiTNode,*BiTree;

     

    /*②二叉树操作接口定义*/

    //1-创建二叉树

    //按先序次序输入二叉树中结点的值(一个字符),#字符表示空树,

    BiTree CreateBiTree(BiTree &T);

    //1-创建二叉树

    //按先序次序输入二叉树中结点的值(一个字符),#字符表示空树

    BiTree CreateBiTree(BiTree &T);

    //2-先序遍历二叉树(递归算法)

    //先序遍历二叉树T的递归算法,对每个数据元素调用函数Visit

    Status PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) );

    //3-中序遍历二叉树(递归算法)

    //中序遍历二叉树T的递归算法,对每个数据元素调用函数Visit

    Status InOrderTraverse( BiTree T, Status(*Visit)(ElemType) );

    //4-后序遍历二叉树(递归算法)

    //后序遍历二叉树T的递归算法,对每个数据元素调用函数Visit

    Status PostOrderTraverse( BiTree T, Status(*Visit)(ElemType) );

    //5-中序遍历二叉树(非递归算法)

    //中序遍历二叉树T的递归算法,对每个数据元素调用函数Visit,非递归算法,

    //采用栈作为辅助结构,注意栈中存储的数据类型是指向树结点的指针

    Status InOrderTraverse1( BiTree T, Status(*Visit)(ElemType) );

    //6-层次遍历二叉树

    //层次遍历二叉树T的递归算法,对每个数据元素调用函数Visit,采用队列作为辅助结构

    Status LevelOrderTraverse( BiTree T, Status(*Visit)(ElemType) );

    //7-统计树的叶子结点个数

    Status CountLeafs(BiTree T,int &numofleafs)

    //8-统计树的层次数

    int CountLevels(BiTree T)


    #include<stdlib.h>
    #include<stdio.h>
    #define TRUE   1
    #define FALSE  0
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -1
    typedef  int Status;
    typedef  char ElemType;
    #define STACK_INIT_SIZE 100
    #define STACKINCREMENT 10
    /*①二叉树的二叉链表存储结构定义*/
    typedef struct BiTNode
    {
    	ElemType data;
    	struct BiTNode *lchild,*rchild;      //左右孩子指针
    }BiTNode,*BiTree;
    
    /*栈的顺序存储结构定义*/
    typedef BiTree SElemType;
    typedef struct 
    {
    	SElemType  *base ;
    	SElemType  *top ; 
    	int  stacksize ;    
    }SqStack; 
    
    
    //1-创建二叉树
    //按先序次序输入二叉树中结点的值(一个字符),#字符表示空树
    Status CreateBiTree(BiTree &T);
    //2-先序遍历二叉树(递归算法)
    //先序遍历二叉树T的递归算法,对每个数据元素调用函数Visit
    Status PreOrderTraverse( BiTree T, Status(*Visit)(ElemType e) );
    //3-中序遍历二叉树(递归算法)
    //中序遍历二叉树T的递归算法,对每个数据元素调用函数Visit
    Status InOrderTraverse( BiTree T, Status(*Visit)(ElemType) );
    //4-后序遍历二叉树(递归算法)
    //后序遍历二叉树T的递归算法,对每个数据元素调用函数Visit。
    Status PostOrderTraverse( BiTree T, Status(*Visit)(ElemType) );
    //5-中序遍历二叉树(非递归算法)
    //中序遍历二叉树T的递归算法,对每个数据元素调用函数Visit,非递归算法,
    //采用栈作为辅助结构,注意栈中存储的数据类型是指向树结点的指针
    Status InOrderTraverse1( BiTree T, Status(*Visit)(ElemType) );
    //6-层次遍历二叉树
    //层次遍历二叉树T的递归算法,对每个数据元素调用函数Visit,采用队列作为辅助结构
    Status LevelOrderTraverse( BiTree T, Status(*Visit)(ElemType) );
    //7-统计树的叶子结点个数
    Status CountLeafs(BiTree T,int &numofleafs);
    //8-统计树的层次数
    Status CountLevels(BiTree T);
    //打印元素
    Status PrintElement(BiTree T);
    //构造一个空栈
    Status InitStack(SqStack &S);
    //进栈
    Status Push( SqStack &S, SElemType e );
    //退栈
    Status Pop(SqStack &S, SElemType &e);
    //判断栈是否为空
    Status StackEmpty(SqStack S);
    
    // 按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树,
      // 构造二叉链表表示的二叉树T。
    Status CreateBiTree(BiTree &T)
    {  
      ElemType ch;
      ch=getchar();
      if (ch==' ') T = NULL;
      else 
      {
    	  
        if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))  exit(OVERFLOW);
        T->data = ch;              // 生成根结点
        CreateBiTree(T->lchild);      // 构造左子树
        CreateBiTree(T->rchild);      // 构造右子树
      }
      return OK;
    } // CreateBiTree
    
    
    //打印元素
    Status PrintElement(ElemType e)
    {
    	printf("%c ",e);
    	return OK;
    }
    
    //2-先序遍历二叉树(递归算法)
    //先序遍历二叉树T的递归算法,对每个数据元素调用函数Visit
    Status PreOrderTraverse( BiTree T, Status(*Visit)(ElemType e) )
    {
    	if(T)
    	{
    		if(Visit(T->data)) 
    			if(PreOrderTraverse(T->lchild,Visit))
    				if(PreOrderTraverse(T->rchild,Visit)) return OK;				
    		return ERROR;
    	}
    	else return OK;
    }//PreOrderTraverse
    
    
    
    //3-中序遍历二叉树(递归算法)
    //中序遍历二叉树T的递归算法,对每个数据元素调用函数Visit
    Status InOrderTraverse( BiTree T, Status(*Visit)(ElemType) )
    {
    	if(T)
    	{ 
    		if(InOrderTraverse(T->lchild,Visit))
            	if(Visit(T->data)) 
    				if(InOrderTraverse(T->rchild,Visit))
    					return OK;
    		return ERROR;
    	}else return OK;
    }//PreOrderTraverse
    
    
    //4-后序遍历二叉树(递归算法)
    //后序遍历二叉树T的递归算法,对每个数据元素调用函数Visit。
    Status PostOrderTraverse( BiTree T, Status(*Visit)(ElemType) )
    {
    	if(T)
    	{
    		if(PostOrderTraverse(T->lchild,Visit))
    			if(PostOrderTraverse(T->rchild,Visit))
    				if(Visit(T->data))  return OK;					
    		return ERROR;
    	}else return OK;
    }//PreOrderTraverse
    
    
    //构造一个空栈
    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 Push(SqStack &S, SElemType e)
    {
    	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++ = e;
        return OK;
    }
    
    //出栈
    Status Pop(SqStack &S, SElemType &e)
    {
    	if (StackEmpty(S))
    		return ERROR; //判空
            e = *(--S.top);
        return OK;
    }
    
    //判断栈是否为空
    Status StackEmpty(SqStack S)
    {
    	if( S.top == S.base )
    		return TRUE;
    	else
    		return FALSE;
     }
    
    
    
    //5-中序遍历二叉树(非递归算法)
    //中序遍历二叉树T的非递归算法,对每个数据元素调用函数Visit,
    //采用栈作为辅助结构,注意栈中存储的数据类型是指向树结点的指针
    Status InOrderTraverse1( BiTree T, Status(*Visit)(ElemType) )
    {
        SqStack S;
        BiTree p;
    	p=T;
    	InitStack(S);
    	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;
    } // InOrderTraverse
    
    
    
    //6-层次遍历二叉树
    //层次遍历二叉树T的递归算法,对每个数据元素调用函数Visit,采用队列作为辅助结构
    Status LevelOrderTraverse( BiTree T, Status(*Visit)(ElemType) )
    { 
    	BiTNode  *Queue[100] ,*p=T ;
                   int  front=0 , rear=0 ;
                   if (p!=NULL) 
    	{  
    	       Queue[++rear]=p;    /*   根结点入队  */
                        while (front<rear)
    	   {  
    		   p=Queue[++front];  Visit( p->data );
    		   if (p->lchild!=NULL)
    			   Queue[++rear]=p->lchild;    /*   左结点入队  */
    		   if (p->rchild!=NULL)
    			   Queue[++rear]=p->rchild;    /*   左结点入队  */
    	   }
    	   return OK;
    	}
    	return ERROR;
    }
    
    
    
    //7-统计树的叶子结点个数
    Status CountLeafs(BiTree T,int &numofleafs)
    {
    	if (T) 
       {
          if (T->lchild==NULL&&T->rchild==NULL) numofleafs++;
          CountLeafs(T->lchild,numofleafs); 
          CountLeafs(T->rchild,numofleafs); 
          return OK;
       } 
       else 
    	   return ERROR;
    }
    
    
    //8-统计树的层次数
    Status CountLevels(BiTree T)
    {
       int levelsoflchild=0;
       int levelsofrchild=0;
       if (T) 
       { 
            levelsoflchild=CountLevels(T->lchild);
            levelsofrchild=CountLevels(T->rchild);
            if(levelsoflchild>levelsofrchild)
    		  return 1+levelsoflchild;
                else return 1+levelsofrchild;
    	}
        else   return 0;
    }
    
    
    void main()
    {
    	BiTree T;
    	int n=0;
    	printf("按先序次序输入二叉树中结点的值(一个字符),空格结束:\n");
    	CreateBiTree(T);
    	CountLeafs(T,n);
    	printf("树的叶子结点个数为:%d",n);
        printf("\n树的层次数为:%d\n",CountLevels(T));
        printf("先序遍历二叉树(递归算法):");
    	PreOrderTraverse(T,PrintElement);
        printf("\n中序遍历二叉树(递归算法):");
    	InOrderTraverse(T,PrintElement);
    	printf("\n后序遍历二叉树(递归算法):");
        PostOrderTraverse(T,PrintElement);
    	printf("\n中序遍历二叉树(非递归算法):");
        InOrderTraverse1(T,PrintElement);
    	printf("\n层次遍历二叉树(递归算法):");
        LevelOrderTraverse(T,PrintElement);
    	printf("\n");
    }


    展开全文
  • 创建二叉树的二叉链表存储结构

    千次阅读 2019-06-07 11:05:47
    #include<stdio.h> #include<stdlib.h> #include<string.h> #define MAXLEN 100 typedef char ElemType;...//二叉链表存储结构 typedef struct BiTNode { DataType data; stru...

    在这里插入图片描述

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define MAXLEN 100
    
    typedef char ElemType;
    typedef char DataType;
    
    //二叉链表存储结构
    typedef struct BiTNode
    {
    	DataType data;
    	struct BiTNode *lchild;
    	struct BiTNode *rchild;
    }BiTNode,*BiTree; //BiTNode为结点类型,BiTree为指向二叉链表结点的指针类型
    
    //栈的数据类型
    typedef BiTree QElemType;
    
    //队列的顺序存储,循环队列的数据类型C语言描述
    
    typedef struct
    {
    	int front;				//指向对头的位置
    	int rear;				//指向对尾的下一个元素的位置
    	int queueSize;			//队列的容量
    	QElemType data[MAXLEN]; //存放对量数据元素的数组;
    }SqQueue;
    
    
    //1.初始化操作
    int initSqQueue(SqQueue *LQ)
    {
    	LQ->front=LQ->rear=0;
    	LQ->queueSize=MAXLEN;
    	return 1;
    }
    
    //2.判断队空
    int SqQueueEmpty(SqQueue Q)
    {
    	if(Q.front==Q.rear)return 1;
    	else return 0;
    }
    
    //4.得到队头
    int SqGetHead(SqQueue Q,QElemType *e)
    {
    	if(Q.rear==Q.front)return 0;
    	*e=Q.data[Q.front];
    	return 1;
    }
    
    //5.进队列
    int SqEnQueue(SqQueue *LQ,QElemType e)
    {
    	if((LQ->rear+1)%LQ->queueSize==LQ->front) return 0;
    	LQ->data[LQ->rear]=e;
    	LQ->rear=(LQ->rear+1)%LQ->queueSize;
    
    	printf("after Enqueue %x:front %d,rear %d\n",e,LQ->front,LQ->rear);
    	return 1;
    }
    
    //6.出队列
    BiTree SqDeQueue(SqQueue *LQ,QElemType *e)
    {
    	if(LQ->front==LQ->rear) return 0;
    	*e=LQ->data[LQ->front];
    	LQ->front=(LQ->front+1)%LQ->queueSize;
    	printf("after Dequeue %x:front %d,rear %d\n",*e,LQ->front,LQ->rear);
    }
    
    //创建二叉树的二插链表存储结构,
    //以左子树右子树的字符串形式读入的递归算法
    //按先序遍历顺序读入每个节点值,创建二叉链表
    void crt_tree(BiTree *T)
    {
    	char ch;
    	scanf("%c",&ch);
    	if(ch=='#') *T=NULL;
    	else
    	{
    		*T=(BiTree)malloc(sizeof(BiTNode));
    		(*T)->data=ch;
    		crt_tree(&(*T)->lchild);
    		crt_tree(&(*T)->rchild);
    	}
    }
    
    //读入边创建二叉链表的非递归算法
    //根据层次遍历,按从上到下,从左到右的顺序依次输入二叉树的边
    //即读入边的信息(father,child,lrflag),其中father表示父结点
    //child表示孩子结点,lrflag表示是左孩子还是右孩子,来建立二叉链表
    
    //算法核心:
    //1.每读入一条边,生成孩子结点,并作为叶子结点;之后
    //将该结点的指针保存在队列中
    //2,从对头指针找该结点的双亲结点指针。如果队头不是,出队列,
    //直至队头是该结点的双亲节点。再按rlflag值建立双亲结点的左右孩子关系
    void Create_BiTree(BiTree *T)
    {
    	SqQueue Q;
    	BiTree p,s,t;
    	char fa,ch,lrflag;
    	initSqQueue(&Q);
    	scanf("%c%c%c",&fa,&ch,&lrflag);
    	while(ch!='#')
    	{
    		p=(BiTree)malloc(sizeof(BiTNode));
    		p->data=ch;							//创建孩子结点
    		p->lchild=p->rchild=NULL;			//做成叶子结点
    		SqEnQueue(&Q,p);
    		if(fa=='#') *T=p;					//建根结点
    		else
    		{
    			 SqGetHead(Q,&s);				//取队列头元素
    			 while(s->data!=fa)
    			 {
    				 SqDeQueue(&Q,&t);
    				 SqGetHead(Q,&s);
    			 }							//在队列中找双亲结点
    			 if(lrflag=='0') s->lchild=p; //连接左孩子结点
    			 else s->rchild=p;
    		}
    		scanf("%c%c%c",&fa,&ch,&lrflag);
    	}
    }
    

    在这里插入图片描述

    读入边信息 队列节点的地址 二叉链表
    #A0 20
    AB0 20 40
    BC1 40 50
    CD0 50 80
    CE1 50 80 70
    DF0 80 70 90
    DG1 80 70 90 30
    F#0 队空
    void preorder(BiTree T)
    {
    	if(T)
    	{
    		printf("%c",T->data);
    		preorder(T->lchild);
    		preorder(T->rchild);
    	}
    }
    
    void layer(BiTree bt)
    {
    	BiTree p;
    	SqQueue Q;
    	initSqQueue(&Q);
    	if(bt) SqEnQueue(&Q,bt);
    	while(!SqQueueEmpty(Q))
    	{
    		SqDeQueue(&Q,&p);
    		printf("%c\n",p->data);
    		if(p->lchild) SqEnQueue(&Q,p->lchild);
    		if(p->rchild) SqEnQueue(&Q,p->rchild);
    	}
    }
    
    void main()
    {
    	BiTree T1=(BiTree)malloc(sizeof(BiTNode));
    	BiTree T2=(BiTree)malloc(sizeof(BiTNode));
    	crt_tree(&T1);
    //	Create_BiTree(&T2);    //测试有问题,输入格式不知道用啥
    	printf("先序遍历:");
    //	preorder(T2);
    	preorder(T1);printf("\n");
    /*	//初始化一个二叉树,其根节点是A,没有左右孩子
    	T->data='A';
    	T->lchild=NULL;
    	T->rchild=NULL;
    //	inorder(T);
    	printf("\n");
    
    	T->lchild=(BiTree)malloc(sizeof(BiTNode));
    	T->lchild->data='B';
    	T->lchild->lchild=NULL;
    	T->lchild->rchild=NULL;
    
    	T->rchild=(BiTree)malloc(sizeof(BiTNode));
    	T->rchild->data='C';
    	T->rchild->lchild=NULL;
    	T->rchild->rchild=NULL;
    //	inorder(T);
    	printf("\n");
    
    	T->lchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    	T->lchild->lchild->data='D';
    	T->lchild->lchild->lchild=NULL;
    	T->lchild->lchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    	T->lchild->lchild->rchild->data='G';
    	T->lchild->lchild->rchild->lchild=NULL;
    	T->lchild->lchild->rchild->rchild=NULL;
    
    	T->rchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    	T->rchild->lchild->data='E';
    	T->rchild->lchild->lchild=NULL;
    	T->rchild->lchild->rchild=NULL;
    	T->rchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    	T->rchild->rchild->data='F';
    	T->rchild->rchild->lchild=NULL;
    	T->rchild->rchild->rchild=NULL;
    */	printf("层次遍历\n:");
    	layer(T1);
    }
    

    运行结果
    在这里插入图片描述

    (3)由二叉树的遍历序列确定二叉树
    ①已知二叉树的先序序列和中序序列可唯一确定一棵二叉树,
    若ABC是二叉树的先序序列,可画出5棵不同的二叉树
    在这里插入图片描述

    void CrtBT(BiTree *T,char pre[],char ino[],int ps,int is,in n)
    {
    	//pre为二叉树的先序序列,n是序列字符个数
    	//ino是二叉树的中序序列
    	//ps是先序序列的第一个字符的位置,初值为0
    	//is是中序序列的第一个字符的位置,初值为0
    	if(n==0) *T=NULL;
    	else
    	//在中序序列中查询根,k为-1,没有找到,否则k为根在中序序列中的位置
    	{
    		k=Search(ino,pre[ps]);
    		if(k==-1)*T=NULL;
    		else
    		{
    			if(!(*T=(BiTree)malloc(sizeof(BiTNode))))exit(0);
    			(*T)->data=pre[ps];   //建立根结点
    			if(k==is)(*T)->lchild=NULL;   //没有左子树
    			else CrtBT(&(*T)->lchild,pre,ino,ps+1,is,k-is);//创建左子树
    			if(k==is+n-1)(*T)->rchild=NULL;    //没有右子树
    			else CrtBT(&(*T)->rchild,pre,ino,ps+1,k+1,n-(k-is)-1));//创建右子树
    		}
    	}
    }
    
    

    ②已知二叉树的后序序列和中序序列可唯一确定一棵二叉树,
    ③已知二叉树的先序序列和后序序列不能确定一棵二叉树,

    (4)由原表达式创建儿叉链表
    the contents is a little more,descript later…

    展开全文
  • 二叉树的简单介绍和二叉树的二叉链表存储表示

    千次阅读 多人点赞 2017-11-26 16:45:18
    本文介绍了二叉树的定义和二叉树的一些简单性质,二叉树的二叉链表表示和二叉树的创建、遍历等基本操作简单实现

    二叉树的概念:

    二叉树是度不大于2的有序树,二叉树的每个结点最多有两个子树,分别称为“左子树”和“右子树”。二叉树还常被用于实现二叉查找树和二叉堆。

    二叉树的性质:

    1. 在二叉树的第i层上最多有2i-1个结点(i ≥ 1
    2. 深度为d的二叉树最多有2^d-1个结点(d ≥ 1)
    3. 对于任意一个二叉树,如果度为0的结点个数为n个,度为2的结点为m个,则n = m + 1。
    4. 含n个结点的完全二叉树深度为log2n +1 。
    5. 若对含 n 个结点的完全二叉树从上到下且从左至右进行1至n的编号,则对完全二叉树中编号为i的结点:
    (1) 若i=1,则该结点是二叉树的根,无双亲,否则,编号为 i/2⌋ 的结点为其双亲结点;
    (2) 若2i>n,则该结点无左孩子,否则,编号为2i 的结点为其左孩子结点;
    (3) 若2i+1>n,则该结点无右孩子,否则,编号为2i+1 的结点为其右孩子结点。

    二叉树的二叉链表存储结构的定义及基本操作的实现:

    //库函数头文件包含
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #include <queue>
    
    using namespace std;
    
    //函数状态码的定义
    #define TRUE        1
    #define FALSE       0
    #define OK          1
    #define ERROR       0
    #define OVERFLOW   -2
    
    typedef int Status;
    typedef int TElemType;
    
    //--------二叉树二叉链表存储表示---------------
    typedef struct BiTNode{
        TElemType data;                     //数据域
        struct BiTNode *lchild;             //左孩子指针域
        struct BiTNode *rchild;             //右孩子指针域
    }BiTNode, *BiTree;
    
    
    //---------基本操作函数的简单实现---------------
    
    //构造空的二叉树T
    Status InitBiTree(BiTree &T){
        T = NULL;                       //直接将根结点赋值为NULL即表示为空树
        return OK;
    }
    
    //销毁二叉树T
    Status DestroyBiTree(BiTree &T){
        /*如果树为空,则直接返回OK, 否则,先递归释放左子树,再递归释放右子树,最后释放根结点*/
        if(!T)
            return OK;
        else{
            DestroyBiTree(T->lchild);
            DestroyBiTree(T->rchild);
            free(T);
            T = NULL;
            return OK;
        }
    }
    
    //先序构造二叉树T
    Status CreateBiTree(BiTree &T){
        /*若输入为0,则创建一个空树,否则创建根结点,递归创建左子树,递归创建右子树。*/
        TElemType e;
        scanf("%d", &e);
        if(e == 0)
            T = NULL;
        else{
            T = (BiTNode *)malloc(sizeof(BiTNode));
            if(!T)
                exit(OVERFLOW);
            T->data = e;
            CreateBiTree(T->lchild);
            CreateBiTree(T->rchild);
        }
        return OK;
    }
    
    //判断树是否为空
    bool BiTreeEmpty(BiTree T){
        if(T == NULL)           //根结点为空时表示树为空,返回true,否则返回false
            return true;
        return false;
    }
    
    //返回树的深度
    int BiTreeDepth(BiTree T){
        int depth = 0;
        int depthl, depthr;
        if(!T)
            depth = 0;
        else{
            depthl = BiTreeDepth(T->lchild);
            depthr = BiTreeDepth(T->rchild);
            if(depthl > depthr)
                depth = depthl + 1;
            else
                depth = depthr + 1;
        }
        return depth;
    }
    
    //求二叉树叶子结点的个数
    int LeafCount(BiTree T){
        if(!T)
            return 0;
        else if(!T->lchild && !T->rchild)
            return 1;
        else
            return LeafCount(T->lchild) + LeafCount(T->rchild);
    }
    
    //统计所有结点数
    int NodeCount(BiTree T){
        if(!T)
            return 0;
        else
            return 1 + NodeCount(T->lchild) + NodeCount(T->rchild);
    }
    
    //visit()函数
    Status Print(TElemType e){
        printf(" %d", e);
    }
    
    //中遍历二叉树
    Status InorderTraversal(BiTree T, Status (*visit)(TElemType)){
        /*若树空则误操作,若树不空,则先递归地中序遍历左子树,后访问根结点,再递归地中序遍历右子树*/
        if(!T)
            return OK;
        else{
            InorderTraversal(T->lchild, visit);
            visit(T->data);
            InorderTraversal(T->rchild, visit);
        }
    }
    
    //先序遍历二叉树
    Status PreorderTraversal(BiTree T, Status (*visit)(TElemType)){
        /*树空无操作,若树不空,则先访问根结点,后递归地先序遍历左子树,再递归地先序遍历右子树 */
        if(!T)
            return OK;
        else{
            visit(T->data);
            PreorderTraversal(T->lchild, visit);
            PreorderTraversal(T->rchild, visit);
        }
    }
    
    //后序遍历二叉树
    Status PostorderTraversal(BiTree T, Status (*visit)(TElemType)){
        /*若树空无操作,若树不空,则先递归地后序遍历左子树,后递归地后序遍历,再访问根结点*/
        if(!T)
            return OK;
        else{
            PostorderTraversal(T->lchild, visit);
            PostorderTraversal(T->rchild, visit);
            visit(T->data);
        }
    }
    
    //层序遍历二叉树
    Status LevelorderTraversal(BiTree T, Status (*visit)(TElemType)){
        /*如果树空,则不做任何操作,否则,利用队列,将每个结点的左右孩子入队,由于队列的性质,可按层序遍历二叉树*/
        if(!T){
            printf(" This binary tree is empty!");
            return OK;
        }
        queue<BiTNode*> TreeQueue;
    
        BiTree p = T;
        TreeQueue.push(p);
    
        while(!TreeQueue.empty()){
            p = TreeQueue.front();
            visit(p->data);
            if(p->lchild)
                TreeQueue.push(p->lchild);
            if(p->rchild)
                TreeQueue.push(p->rchild);
            TreeQueue.pop();
        }
        return OK;
    }
    
    //主函数
    int main(){
        BiTree T;
        InitBiTree(T);
        CreateBiTree(T);
        printf("The number of nodes in this binary tree is: %d\n", NodeCount(T));
        printf("The inorder traversal sequence of the binary tree is:");
        InorderTraversal(T, Print);
        printf("\nThe preorder traversal sequence of the binary tree is:");
        PreorderTraversal(T, Print);
        printf("\nThe postorder traversal sequence of the binary tree is:");
        PostorderTraversal(T, Print);
        printf("\nThe levelorder traversal sequence of the binary tree is:");
        LevelorderTraversal(T, Print);
        printf("\nThe number of leaves in this binary tree is: %d", LeafCount(T));
        printf("\nThe depth of this binary tree is: %d", BiTreeDepth(T));
        printf("\nIs the binary empty? ");
        if(BiTreeEmpty(T))
            printf("YES\n");
        else
            printf("NO\n");
        DestroyBiTree(T);
        return 0;
    }

    下面是对代码的简单测试结果:
    输入的二叉树为下图:
    运行结果如下图:

    展开全文
  • **给定一颗二叉树的遍历顺序,创建相应的二叉树链表。这里所说的遍历顺序是一种“扩展的遍历序列”,即用“.”来表示空的子树。下面,我们来构建先序遍历序列为AB.DF..G..C.E.H..的二叉链表。** 先看书上面使用C语言...

    给定一颗二叉树的遍历顺序,创建相应的二叉树链表。这里所说的遍历顺序是一种“扩展的遍历序列”,即用“.”来表示空的子树。下面,我们来构建先序遍历序列为AB.DF..G..C.E.H..的二叉链表。


    先看书上面使用C语言的实现:

     void CreateBiTree(BiTree *bt){
            char ch;
            ch = getchar();
            if('.' == ch) *bt = NULL;
            else{
                *bt = (BiTree)malloc(sizeof(BiTNode));
                (*bt)->data = ch;
                CreatBiTree(&((*bt)->LChild));
                CreatBiTree(&((*bt)->RChild));
        }
     }

    下面用Java来实现上述内容
    首先定义二叉树的存储结构

    class MyBiTree<T> {
        private Node<T> root;
    
        public Node<T> getRoot() {
            return root;
        }
    
        public void setRoot(Node<T> root) {
            this.root = root;
        }
    
        public MyBiTree() {
            root = new Node<T>();
        }
    
        static class Node<T> {
            T data;
            Node<T> lChild;
            Node<T> rChild;
    
            Node() {
                this.lChild = null;
                this.rChild = null;
            }
    
            Node(T data) {
                this.data = data;
                this.lChild = null;
                this.rChild = null;
            }
    
            Node(T data, Node<T> lChild, Node<T> rChild) {
                this.lChild = lChild;
                this.rChild = rChild;
            }
        }
    
        // 树的先序遍历
        public void rootLR(Node<T> root) {
            if (root != null) {
                System.out.println(root.data);
                rootLR(root.lChild);
                rootLR(root.rChild);
            }
        }
    }

    然后开始构建二叉树

    /**
     * 输入树的先序串,构建出一棵树
     * 测试用例:a b . d f . . g . . c . e . h . .
     * */
    public class TreeDemo1 {
        //由于使用递归的方式来构建,所以Scanner类不能定义到方法内,而方法内要使用,所以定义为静态
        static Scanner sc = new Scanner(System.in);
        static MyBiTree<String> tree = new MyBiTree<>();
    
        public static void main(String[] args) {
            CreatTree(tree.getRoot());
            tree.rootLR(tree.getRoot());
        }
    
        private static Node<String> CreatTree(Node<String> node) {
            String str = sc.next();
    
            if(str.equals(".")){
                return null;
            }else{
                Node<String> newNode = new Node<>(str);
                node.data = newNode.data;
                node.lChild = CreatTree(new Node<String>());
                node.rChild = CreatTree(new Node<String>());
                return node;
            }
        }
    }

    我尝试过用书上类似的代码用Java实现,但是发现行不通。深入思考以后才了解,如果使用node = new Node<>(str); 只是将栈内存中方法内的引用指向了一个新的堆内存创建的对象上,没有改变堆内root节点对象,所以应该直接改变堆内存的对象。
    所以可以写下:

    node.data = newNode.data;
    node.lChild = CreatTree(new Node());
    node.rChild = CreatTree(new Node());
    这样每层迭代构建一个新的节点,将新节点的数据赋值给迭代进来的node,然后将node的左右节点分别迭代,最后返回构建的节点。

    为什么在构建左右子树的时候要创建新的节点对象作为参数,而不能直接把newNode作为参数?测试发现不可行。原因有待进一步思考。

    展开全文
  • 编写采用二叉链表形式存储的二叉树创建、先序、中序、后序和按层遍历的算法。 编写将一棵二叉树的所有左右子树进行交换
  • 建立二叉树的二叉链表存储结构并在此结构上实现二叉树的三种遍历算法。 算法思想: 创建一个二叉链表的二叉树结构体,data指向该结点的信息,LChild指向左孩子,RChlid指向右孩子。用先序遍历序列创建二叉树,再分别...
  • 利用二叉链表存储,并且利用递归方法实现二叉树的遍历(前序遍历、中序遍历和后续遍历)操作。 c语言具体实现代码如下: #include #include #include typedef int ElemType;//数据类型 //定义二叉树结构,与...
  • 采用二叉链表的方式进行存储构造一个二叉树类,实现以下算法: 1.创建二叉树 2.对二叉树进行前序、中序、后序遍历 输入 扩展前序序列.在一棵树处理结束后,根据响应判断是否处理下一棵树 输出 前序、...
  • 1 二叉树节点数据类型声明     在数据结构 · 树(二叉树)一文中,详细概述了二叉树的各种分类与特性,同时也用数组(顺序存储)方式来实现了二叉树的存储与遍历。显而易见,使用数组方式实现二叉树,视树情形...
  • 一、线性表 1.数组实现 2.链表二、栈与队列、优先队列三、树与二叉树 1.树 2.二叉树基本概念 3.二叉查找树 4....链表:用一组任意的存储单元存储线性表数据元素(存储单元可以是连续,也可以是不连...
  • 树结点定义(这课树数据域是字符类型,如果需要可以把类型更改为对应Elemtype): typedef struct BiTNode{ char data; struct BiTNode *lchild,*rchild;... //创建一棵二叉树 char ch; sca...
  • 程序特点采用java面向对象语言对二叉树用二叉链表用类进行封装能够创建二叉树并且能够按前序遍历显示输出所创建的二叉树 程序的算法设计 算法一按前序遍历方式建立二叉树算法 逻辑结构与存储结构设计 逻辑结构非线
  • 用层次遍历算法求二叉树的高度 关键: 1、last指针何时指向下一层 代码1: int getBiTreeDepth(BTNode *t){ //1.创建队列 2.初始化工作=>根节点入队 BTNode *que[MAXSIZE]; int front=-1,rear=-1;//front...
  • 展开全部#include#includetypedef int ElemType;typedef struct LNode{ElemType data;struct LNode *lchild,*rchild;...void create(TLNode * Tree){ //创建32313133353236313431303231363533e78988e69d83313...
  • 本题中无论建立还是遍历二叉树,都用到了递归思想,个人感觉跟广义表建立有些像。 代码如下: #include <stdio.h> #include <stdlib.h> typedef struct Node { char data; struct Node *LChild; ...
  • 二叉树部分知识比较简单好理解,就是要注意二叉树的创建遍历等操作均需要递归完成。 具体操作见代码,代码中有部分注释。 题解代码: #include<stdio.h> #include<stdlib.h> typedef struct ...
  • A、链表B、树C、队列D、栈正确答案是:D解析: 校验节点是否闭合时,每读入一个开始标记时,就需要将其作为优先级更高待检验节点并置于待检验节点序列最顶层位置,这样方便匹配消除;每读入一个结束标记时,看...
  • 假设二叉数据元素为字符,采用二叉链式存储结构。请编码实现二叉树ADT,其中包括创建二叉树、遍历二叉树(深度、广度)、求二叉树的深度(高度)、计算二叉树的元素个数、计算二叉树的叶子数、二叉树的格式输出...
  • 1,创建二叉链表 // 根据二叉树的顺序存储,创建并返回二叉链表 BiTree create(char s[]){ BiTree p [MAXSIZE+1]; int i=1; p[1] = (BiTree ) malloc (sizeof(BiTree)); p[1]-&amp;gt;data = s[1]; p[1...
  • 递归函数执行次数#include&lt;stdio.h&gt;void fun(int a[], int n, int k){int i;if (k == n - 1){for (i = 0; i &lt; n; i++){printf("%5d", a[i]);}}else{for (i = k; i &lt; n; i++...
  • 二叉链表

    2019-11-09 10:32:00
    本文总结了严蔚敏老师数据结构二叉树二叉链表存储的创建、判空和遍历。
  • 1、树定义树是n(n>=0)个节点有限集合。...2、树基本概念 双亲孩子、兄弟:节点字数根称为该节点孩子,该节点称为其子节点双亲。具有相同双亲节点互为兄弟节点。如图:A是根节点,B、...

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 373
精华内容 149
关键字:

创建二叉链表存储的二叉树