精华内容
下载资源
问答
  • 先序遍历的顺序创建二叉链表并中序遍历 1.算法步骤: 1)扫描数字序列,读入数字n。 2)如果n是一个 0 数字,则表明该二叉树为空树,即T=NULL;否则执行一下操作。 申请一个节点空间T 将n赋给(*T)->data ...

    先序遍历的顺序创建二叉链表并中序遍历


    1.算法步骤:

       1)扫描数字序列,读入数字n。

       2)如果n是一个 0 数字,则表明该二叉树为空树,即T=NULL;否则执行一下操作。

    •  申请一个节点空间T
    • 将n赋给(*T)->data
    • 递归创建T的左子树
    • 递归创建T的右子树

    2.创建的结果图:

    3.数字的输入顺序:

              1 2 3 0 0 0 4 5 0 0 6 0 0

    4.C语言完整程序

    #include <stdio.h> 
    #include <stdlib.h>
    
    typedef int ElemType; 
    typedef struct BiNode{
    	ElemType data;
    	struct BiNode *leftChild,*rightChild;
    }BiNode,*BiTree;
    
    /*Function:先序遍历的顺序创建二叉链表*/
    void CreateBiTree(BiTree *T){
    	ElemType n;
    	printf("请输入元素:\n");
    	scanf("%d",&n);
    	if(n==0){
    		(*T)=NULL;
    	}else{
    		(*T)=(BiNode *)malloc(sizeof(BiNode));
    		(*T)->data=n;
    		CreateBiTree(&((*T)->leftChild));
    		CreateBiTree(&((*T)->rightChild));
    	}
    }
    /*Function:中序遍历二叉树的递归算法*/ 
    void InOrderTraverse(BiTree T){
    	if(T){
    		InOrderTraverse(T->leftChild);
    		printf("%d",T->data);
    		InOrderTraverse(T->rightChild);
    	}
    } 
    /*主函数*/ 
    void main(){
    	BiTree tree;
    	printf("请输入建立二叉链表的序列:\n");
    	CreateBiTree(&tree);
    	printf("二叉树中序遍历为:\n");
    	InOrderTraverse(tree);
    }

    5.程序中的指针问题:

         在程序中我们会注意到:在创建结构体时定义了结构体指针*BiTree,在CreateBiTree()方法中传入的参数是BiTree *T,没错传入的参数就是二维指针,即指向指针的指针。

         这是因为:在申请根结点空间时,地址可能会发生变化,而这种变化是无法判断的,单个指针就无法找到变化后的地址,所以 ,用指针的指针,找到变化后的地址。

    6.执行结果:

    展开全文
  • #include #include typedef struct Node { char date; struct Node *lchild; struct Node *rchild; }node; void inlist(node *&l) { char ch; ch=getchar(); if(ch=='.') l=NULL; else ...l=(node *)
    #include<stdio.h>
    #include<stdlib.h>
    typedef struct Node
    {
    char date;
    struct Node *lchild;
    struct Node *rchild;
    }node;
    void inlist(node *&l)//取L得地址
    {
    char ch;
    ch=getchar();
    if(ch=='.')
    l=NULL;
    else
    {
    l=(node *)malloc(sizeof(node));
    l->date=ch;
    inlist(l->lchild);
    inlist(l->rchild);
    }
    }
    void prelist3(node *&l)//先序遍历二叉树
    {
         node *root;
    root=l;
    if(root!=NULL)
    {
    if(root->lchild==NULL&&root->rchild==NULL)//输出叶子结点
    printf("%c",root->date);
             prelist3(root->lchild);
    prelist3(root->rchild);
    }
    }
    void prelist1(node *&l)//中遍历二叉树
    {
         node *root;
    root=l;
    if(root!=NULL)
    {
    prelist1(root->lchild);
    printf("%c",root->date); 
    prelist1(root->rchild);
    }
    }
    void prelist2(node *&l)//后序遍历二叉树
    {
         node *root;
    root=l;
    if(root!=NULL)
    {
             prelist2(root->lchild);
    prelist2(root->rchild);
    printf("%c",root->date);
    }
    }
    int main()
    {
        node *l;
    inlist(l);
    prelist3(l);
    printf("\n");
    prelist1(l);
    printf("\n");
    prelist2(l);
    printf("\n");
    return 0;
    }
    展开全文
  • #mermaid-svg-wdqTucBj8NMkWaH6 .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-wdqTucBj8NMkWaH6 .label text{fill:#333}#mermaid...
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define DataType char
    #define MAXSIZE 1000
    int count = 0;  //统计节点数
    
    typedef struct Node
    {
        DataType data;
        struct Node * Lchild;
        struct Node * Rchild;
        // struct Node * Parent;
    } BiTNode,* BiTree;
     
     void CreateBiTree(BiTree * root)
     {
         char ch;
         ch = getchar();
         if(ch == ' ')          //空格代表为空
            * root = NULL;
         else
         {
            *root = (BiTree)malloc(sizeof(BiTNode));
            (*root)->data = ch;
            CreateBiTree(&((*root)->Lchild));
            CreateBiTree(&((*root)->Rchild));
         }
     }
     
     void PreOrder(BiTree root) //先序
     {
         if(root)
         {
             putchar(root->data);
             PreOrder(root->Lchild);
             PreOrder(root->Rchild);
         }
     }
     void InOrder(BiTree root)  //中序
     {
         if(root)
         {
             InOrder(root->Lchild);
             putchar(root->data);
             InOrder(root->Rchild);
         }
     }
     void PostOrder(BiTree root)    //后序
     {
         if(root)
         {
             PostOrder(root->Lchild);
             PostOrder(root->Rchild);
             putchar(root->data);
             count++;       //后序遍历同时计节点数
         }
     }
    int leaf(BiTree root)  //输出叶子节点和统计叶子节点个数
    {
        if(root == NULL) return 0;
        if(!root->Lchild && !root->Rchild) 
        {
            putchar(root->data);
            return 1;    //当前节点无孩子,为叶子节点
        }
        return leaf(root->Lchild) + leaf(root->Rchild);
    }
    int TreeDepth(BiTree root)  //求树高度
    {
        int h,lh,rh;
        if(root == NULL) return 0;
        lh = TreeDepth(root->Rchild);
        rh = TreeDepth(root->Lchild);
        h = (lh>rh ? lh : rh) + 1;
        return h;
    }
    void PrintfTree(BiTree root, int h) //按树状打印二叉树,先右后左中序遍历树
    {                                   //结点的横向位置有结点在树中的层次决定,h表示结点的层次,控制结点输出左右位置
        if(root == NULL) return;
        PrintfTree(root->Rchild,h+4);   //每个层次相隔4个空格
        for (int i = 0; i < h; i++) 
            printf(" ");
        printf("%c\n",root->data);
        PrintfTree(root->Lchild,h+4);
    }
    
    int main(int argc, char **argv) {
    
        int LeafNum,Depth;
        BiTree Tree;
    
        printf("按先序输入建立树:");
        CreateBiTree(&Tree);
        
        printf("先序:");
        PreOrder(Tree);
        
        printf("\n中序:");
        InOrder(Tree);
        
        printf("\n后序:");
        PostOrder(Tree);
        
        printf("\n叶子节点:");
        LeafNum = leaf(Tree);
        printf("\n节点数:%d",count);
        printf("    叶子节点数为%d",LeafNum);
        
        Depth = TreeDepth(Tree);
        printf("\n树高度为:%d\n",Depth);
        
        PrintfTree(Tree,1);
        
        return 0;
    }
    
    
    展开全文
  • 源代码: #include #include #include #define TElemtype char #define Status int #define OK 1 #define ERROR 0 typedef struct BiTNode { TElemtype data;...struct BiTNode *lchild,*rchild;...
  • 二叉链表创建有三种方法,1、用户键盘输入创建 2、根据二叉树的顺序表·来·创建二叉链表 3、读取文件来创建二叉链表

    一、键盘交互创建二叉树

    //键盘交互递归创建二叉树子树函数
    void createSubTree(btNode *&p, int k)
    {
    	//k=1--左子树;k=2--右子树
    	btNode *s;
    	elementType x;
    	cout<<"请输入结点元素数值,'/'表示无子树,x=";
    	cin>>x;
    	if(x!='/')
    	{
    		s=new btNode;
    		s->data=x;
    		s->lChild=NULL;
    		s->rChild=NULL;
    		if(k==1)
    			p->lChild=s;     //s接到p的左孩子
    		if(k==2)
    			p->rChild=s;     //s接为p的右孩子
    		createSubTree(s,1);  //递归创建s的左子树
    		createSubTree(s,2);  //递归创建s的右子树	
    	}
    }
    
    //键盘交互创建二叉树主控函数
    void createBTConsole(btNode *&T)
    {
    	btNode *p;
    	elementType x;
    	cout<<"请按先序序列输入二叉树结点,(‘/’表示无子树):"<<endl;
    	cout<<"请输入结点元素数值,'/'表示无子树,x=";
    	cin>>x;
    	if(x=='/')
    		return;    //空树,退出
    	T=new btNode;
    	T->data=x;
    	T->lChild=NULL;
    	T->rChild=NULL;
    
    	createSubTree(T,1);    //创建根结点的左子树
    	createSubTree(T,2);    //创建根结点的右子树
    }
    

    二、根据二叉树的顺序表存储创建二叉链表

    //完全二叉树顺序存储方式创建二叉链表结构二叉树
    //创建顺序表
    void getCompleteArr(elementType *arr, int &num)
    {
    	    //缺少的结点数值用'/'代替
    	    //用'#'结束结点输入
    	    //arr为结点数组
    	    //num返回实际结点数
    	elementType x;
    	int i=1;   //arr[0]单元不用
    	num=0;
    	cout<<"请按完全二叉树方式输入二叉树结点,‘/’表示缺少结点,'#'结束输入。"<<endl;
    	cout<<"请输入结点元素数值,'/'表示缺少结点,'#'结束输入,x=";
    	cin>>x;
    	while(x!='#')
    	{
    		*(arr+i)=x;
    		i++;
    		num++;
    
    		cin>>x;
    	}
    }
    //创建二叉链表
    void createBtArr(btNode* &T, elementType* InArr, int i, int n)
    {
    	//T--为根结点指针
    	//InArr--为按完全二叉树存储的树的结点数组
    	//i--当前结点序号
    	//n--二叉树结点总数
    	if(i>n)
    		return;
    	if(InArr[i]!='/')       //有效数据创建结点
    	{
    		T=new btNode;       //创建根结点
    		T->data=InArr[i];   //结点赋值
    		T->lChild=NULL;
    		T->rChild=NULL;
    	}
    	createBtArr(T->lChild, InArr, 2*i, n);    //递归创建T的左子树
    	createBtArr(T->rChild, InArr, 2*i+1, n);  //递归创建T的右子树
    }
    
    

    三、读取数据文件创建二叉树

    //删除字符串、字符数组左边空格
    void strLTrim(char* str)
    {
    	int i,j;
    	int n=0;
    	n=strlen(str)+1;
    	for(i=0;i<n;i++)
    	{
    		if(str[i]!=' ')  //找到左起第一个非空格位置
    			break;
    	}
    	    //以第一个非空格字符为手字符移动字符串
    	for(j=0;j<n;j++)
    	{
    		str[j]=str[i];
    		i++;
    	}
    }
    
    //从文本文件数据读入到数组中,同时返回实际结点数量
    bool ReadFileToArray(char fileName[], char strLine[NODENUM][3], int & nArrLen)
    {
    	//读文本文件数据到数组,返回数组及其长度
    	FILE* pFile;      //定义二叉树的文件指针
    	char str[1000];   //存放读出一行文本的字符串
    	char strTemp[10]; //判断是否注释行
    
    	pFile=fopen(fileName,"r");
    	if(!pFile)
    	{
    		cout<<"错误:文件"<<fileName<<"打开失败。"<<endl;
    		return false;
    	}
    
    	while(fgets(str,1000,pFile)!=NULL)  //跳过空行和注释行
    	{
    		   //删除字符串左边空格
    		strLTrim(str);
    		if (str[0]=='\n')               //空行,继续读取下一行
    			continue;
    
    		strncpy(strTemp,str,2);
    		if(strstr(strTemp,"//")!=NULL)  //跳过注释行
    			continue;
    		else                            //非注释行、非空行,跳出循环
    			break;
    	}
               //循环结束,str中应该已经是二叉树数据标识"BinaryTree",判断文件格式
    	if(strstr(str,"BinaryTree")==NULL)
    	{
    		printf("错误:打开的文件格式错误!\n");
    		fclose(pFile);           //关闭文件
    		return false;
    	}
    
    
        
    
    	//nArrLen=0;
    	//while(fscanf(pFile,"%c  %c  %c\n",&strLine[nArrLen][0],&strLine[nArrLen][1],&strLine[nArrLen][2])!=EOF)	
    	//{
    		//printf("%c\n",strLine[nArrLen][0]);
    	//	nArrLen++;
    	//}
    
    	nArrLen=0;     //数组行号初始化为0
    	while(fgets(str,1000,pFile)!=NULL)
    	{
    		    //删除字符串左边空格
    		strLTrim(str);
    		if (str[0]=='\n')  //空行,继续读取下一行
    			continue;
    		
    		strncpy(strTemp,str,2);
    		if(strstr(strTemp,"//")!=NULL)  //注释行,跳过,继续读取下一行
    			continue;
    
    		char* token=strtok(str," ");   //以空格为分隔符,分割一行数据
    		if(token==NULL)  //分割为空串,失败退出
    		{
    			printf("错误:读取二叉树结点数据失败!\n");
    			fclose(pFile); //关闭文件
    			return false;
    		}
    		
    		strLine[nArrLen][0]=*token;  //获取结点数据
    		token = strtok( NULL, " ");  //读取下一个子串,即此结点的左子树信息
    		if(token==NULL)  //分割为空串,失败退出
    		{
    			printf("错误:读取二叉树结点数据失败!\n");
    			fclose(pFile); //关闭文件
    			return false;
    		}
    		strLine[nArrLen][1]=*token;  //获取此结点的左子树信息数据
    		token = strtok( NULL, " ");  //读取下一个子串,即此结点的右子树信息
    		if(token==NULL)  //分割为空串,失败退出
    		{
    			printf("错误:读取二叉树结点数据失败!\n");
    			fclose(pFile); //关闭文件
    			return false;
    		}
    		strLine[nArrLen][2]=*token;  //获取此结点的右子树信息数据
    
    		nArrLen++;  //数组行号加1	
    	}
    
    	fclose(pFile); //关闭文件
    	return true;
    }
    
    
    //从数组创建二叉树--数组中保存的是二叉树的先序序列,及每个结点的子树信息
    bool CreateBiTreeFromFile(btNode* & pBT, char strLine[NODENUM][3],int nLen, int & nRow)
    {
    	//strLine[NODENUM][3]--保存节点数据的二维数组
    	//nLen--数组长度,即:节点个数
    	//nRow--数组当前行号
    
    	if((nRow>=nLen) || (nLen==0))
    		return false;  //数据已经处理完毕,或者没有数据,退出
    
    	//根据数组数据递归创建子树
    	pBT=new btNode;
    	pBT->data=strLine[nRow][0];
    	pBT->lChild=NULL;
    	pBT->rChild=NULL;
    	
    	int nRowNext=nRow;  //保留本次递归的行号	
    
    	if(strLine[nRowNext][1]=='1')  //当前结点有左子树,递归创建左子树,读下一行数据
    	{
    		nRow++;
    		CreateBiTreeFromFile(pBT->lChild, strLine,nLen,nRow);
    	}
    
    	if(strLine[nRowNext][2]=='1')  //当前结点有右子树,递归创建右子树,读下一行数组
    	{
    		nRow++;
    		CreateBiTreeFromFile(pBT->rChild, strLine,nLen,nRow);		
    	}
    
    	return true;
    }
    
    展开全文
  • 利用二叉链表存储,并且利用递归的方法实现二叉树的遍历(前序遍历、中序遍历和后续遍历)操作。c语言具体实现代码如下:#include#include#includetypedef int ElemType;//数据类型//定义二叉树结构,与单链表相似,多...
  • (1)建立二叉树的二叉链表。 (2)写出对用二叉链表存储的二叉树进行先序、中序和后序遍历的递归和非递归算法。 (3)写出对用二叉链表存储的二叉树进行层次遍历算法。 (4)求二叉树的所有叶子及结点总数。 ...
  • 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 #include #define N 20 typedef struct node //节点创建 {  char data;  struct node *lchild,*rchild;  int index;
  • #include#includetypedef struct BiTNode{char data;结构位*rchild、*rchild;...bi树创建树(bi树t ) {//char ch;扫描(' % c ',ch );if(ch==#) T=NULL;else {t=(bi tree ) malloc (sizeof (bitnode ) );...
  • 如何创建一颗二叉链表的二叉树?

    千次阅读 2017-01-01 09:41:54
    如何创建一颗二叉链表的二叉树?非常的简单,就是将二叉树的数组表示,转化为二叉链表。如下如所示的树,其数组表示为: {1,2,3,4,5,6,null,null,null, 7,8}节点的内容保存在数组中,节点间的父子兄弟关系保存在...
  • 树:二叉链表的实现

    千次阅读 多人点赞 2018-02-12 21:41:03
    二叉链表介绍二叉树每个结点最多有2个孩子,...我们用char类型的数据来模拟二叉链表创建和遍历。我们知道二叉链表的遍历有3种,前序遍历,中序遍历,后序遍历。那么创建链表的时候同样我们可以约定是前序、中序...
  • 创建二叉树的二叉链表存储结构

    万次阅读 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...
  • 二叉链表

    2019-11-09 10:32:00
    本文总结了严蔚敏老师数据结构二叉树二叉链表存储的创建、判空和遍历。
  • 二叉链表的链式数据结构为: typedef struct BTreeNode { DataType data; struct BTreeNode * lchild; struct BTreeNode * rchild; }*BTree,BTreeNode; 在对二叉树进行非递归遍历的时候需要用到栈来保存结点或者...
  • 二叉链表和三叉链表

    千次阅读 2016-01-20 10:23:53
    前面创建二叉树时,Node的定义中包含左右连个后继,则这种链表就是二叉链表。 三叉链表在二叉链表节点基础上,增加一个父亲前驱。这样给定任何一个节点,就可以访问到它的父亲。
  • 广义表创建二叉树(二叉链表 1.注意先创建节点再赋值,避免空指针异常 ( t->lc=new BiTNode; t=t->lc; 2.★注意创建节点时先将其左右子树赋为NULL //广义表创建二叉树 void BTreeCreate(BT &t,char a[],...
  • C语言实现二叉链表创建和遍历

    千次阅读 2019-08-06 14:02:15
    typedef struct node{ //二叉链表节点 DataType data; struct node *lchild, *rchild; }BinTNode; typedef BinTNode *BinTree; BinTNode * CreateTree(char *str){ //建立二叉链表 BinTN...
  • 利用二叉链表存储,并且利用递归的方法实现二叉树的遍历(前序遍历、中序遍历和后续遍历)操作。 c语言具体实现代码如下: #include #include #include typedef int ElemType;//数据类型 //定义二叉树结构,与...
  • 创建任意一颗二叉链表树,在输入序列中标明每一个树结点及其两个孩子结点,若孩子结点为空,需要用特殊值标记。 如,若要构造图中的二叉树,
  • 本题要求实现一个函数,给定一棵二叉树的层序序列,创建该树的二叉链表。 函数接口定义: BinTree CreatBinTree(); 函数CreatBinTree从标准输入读入一棵二叉树的层序序列,创建二叉树的二叉链表。函数应返回指向...
  • #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; typedef struct Lnode *T; typedef T Bintree; struct Lnode{ &nbsp;char data; &nbsp;Bintree Left; &nbsp;... t...
  • 程序特点采用java面向对象语言对二叉树用二叉链表用类进行封装能够创建二叉树并且能够按前序遍历显示输出所创建的二叉树 程序的算法设计 算法一按前序遍历方式建立二叉树算法 逻辑结构与存储结构设计 逻辑结构非线
  • 【算法步骤】 扫描字符序列,读入字符ch. ...创建二叉链表如图所示: 代码如下: #include <iostream> using namespace std; typedef struct BiNode { char date; //二叉链表的定义 struct BiNode *lchi
  • 二叉树之二叉链表

    千次阅读 2016-11-30 22:20:16
    利用java语言模拟二叉树的二叉链表的实现
  • 二叉链表创建一棵二叉树并利用递归算法求它的高度
  • 实验三 二叉树的二叉链表表示及实现 实验项目中文名称二叉树的二叉链表表示及实现 实验项目英文名称Definition and Implementation of Binary Tree 实验学时2学时 一实验目的 1深入了解二叉树的特性掌握二叉树的二叉...
  • 本文创建的二叉树采用二叉链表的形式来创建二叉链表定义的树的结点通常包含一个数据域,两个地址域(分别用来指向左右子树),所以在创建树之前需要定义一个表示结点的结构体,具体实现如下: /* 定义一个结构体...
  • 本题要求实现一个函数,给定一棵二叉树的层序序列,创建该树的二叉链表。 函数接口定义: BinTree CreatBinTree(); 函数CreatBinTree从标准输入读入一棵二叉树的层序序列,创建二叉树的二叉链表。函数应返回...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 24,343
精华内容 9,737
关键字:

创建二叉链表