精华内容
下载资源
问答
  • //首先将树的二叉链表存储形式转化为树的顺序存储形式 //首先知道树的顺序存储结构 它利用完全二叉树的性质来定义的 不管一棵二叉树什么结构 它都可以补全成完全二叉树 //其实我们把二叉树的顺序表从1开始 (有些...

     

    //首先将树的二叉链表存储形式转化为树的顺序存储形式

    //首先知道树的顺序存储结构  它是利用完全二叉树的性质来定义的  不管一棵二叉树什么结构 它都可以补全成完全二叉树

    //其实我们把二叉树的顺序表从1开始 (有些也可以从0开始 此时它的左右孩子就变成了 2*i+1 / 2*i+2)

    //它的左右孩子为2*i   2*i+1
     

    可以直接通过树的遍历算法来实现  用树的结点来做索引   每次如果遇到空的情况 直接将该数组值变为‘/’

    接下来看代码演示(函数命名不要介意)

    //T为根节点 K数组用来存放数据  i表示该数据在数组中的下标   在这之前先将K数组全部初始化为‘/’
    
    void TranstoArray(BiTree T, char K[], int i) {
    	if (T) {
    		K[i] = T->data;
    		TranstoArray(T->lchild, K, 2 * i);
    		TranstoArray(T->rchild, K, 2 * i + 1);
    	}
    	else
    	{
    		K[i] = '/';    //若T为空 说明上个结点的左或右孩子中必有空的情况
    	}
    }
    
    
    

     而将树的顺序存储结构转化为树的二叉链式存储结构 和上面相反  

    此时用数组K来索引  每次通过数组K的值来创建二叉树结点  所以要用"指针的指针"或者"指针的引用"来创建一颗新的二叉树结构

    代码如下: 

    //T表示一个在主函数中定义的指针的地址(指针的指针)
    
    //过程类似于二叉排序树 ,AVL的创建
    
    void TranstoTable(BiTree *T, char K[], int i) {
    	if (K[i] != '/') {
    		BiTree temp = new BiNode;   //用来申请新的空间
    		temp->data = K[i];
    		temp->lchild = temp->rchild = NULL;
    		(*T) = temp;
    		TranstoTable(&(*T)->lchild, K, 2 * i);  //每次通过改变左右指针的空间来继续创建
    		TranstoTable(&(*T)->rchild, K, 2 * i + 1);
    	}
    	else
    	{
    		(*T) = NULL;  //此时表示这个结点的位置为空
    	}
    }

     

    展开全文
  • 什么是二叉树呢? 二叉树n(n>=0)个结点的有限集,它或为空树(n=0),或由一个根结点和两棵分别称为左子树和右子树的互不相交...二叉树的二叉链表存储结构的定义 typedef struct BiTNode { // 结点结构 TElemT...

    什么是二叉树呢?

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

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

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

    构建二叉树

    //构建二叉树
    
    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)先序遍历右子树。

    递归算法

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

    非递归算法

    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)中序遍历右子树。

    递归算法

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

    非递归算法

    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)访问根结点。

    递归算法

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

    非递归算法

    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
    

    求二叉树的深度

    //求二叉树的深度
    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;
    	}
    }
    

    求二叉树中结点个数

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

    求二叉树中叶子结点个数

    //求二叉树中叶子结点个数
    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的结点个数

    //求二叉树中度为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));
    }
    

    主函数实现

    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");
    		}
    	
    	}
    }
    
    展开全文
  • 首先我们得了解到这个数据结构的单体是什么样子的,他单体包括了数据和两个指向左右孩子的指针 所以我们用结构体写出来这个二叉树节点: typedef struct treenode { char data; struct treenode* Lchild; struct ...

    上个博客整理了二叉树的基础知识,这里是链接:二叉树的一些基本知识

    了解到基本要点和基本结构后,我们来实现一下这个数据结构:

    首先我们得了解到这个数据结构的单体是什么样子的,他单体包括了数据和两个指向左右孩子的指针
    所以我们用结构体写出来这个二叉树节点:

    typedef struct treenode {
    	char data;
    	struct treenode* Lchild;
    	struct treenode* Rchild;
    }TREE,*LPTREE;
    

    因为这个节点名字太长了,我就起个别名,这里要注意的是我的 treenode*这个类型的起别名方式
    一般来说LPXXXXX代表一个一级指针

    然后就是创建一个这样的节点的函数
    需要的是分配空间,赋值数据,指针置空初始化
    接下来是代码

    LPTREE createnode(char data) {
    	LPTREE newnode = (LPTREE)malloc(sizeof(TREE));
    	newnode->data = data;
    	newnode->Lchild = NULL;
    	newnode->Rchild = NULL;
    	return newnode;
    }
    

    树的节点能够创建,那么就是连接各个节点,成为一个树。
    需要参数的是父节点,左节点,右节点。
    然后就是指针指向的问题,比如a节点作为父节点,b为左孩子,c为右孩子,
    我就需要的是将a的左孩子指针指向b,右孩子指针指向c
    那么实现一下这个代码:

    void tree(LPTREE dad, LPTREE left, LPTREE right) {
    	dad->Lchild = left;
    	dad->Rchild = right;
    }
    

    那么这个树建立需要的函数我们已经实现好了,接下来是,遍历的问题,这节我采用递归的方法实现,虽然不好理解但是代码少,具体我会再注释的:
    先实现一下打印当前节点的函数:

    void printnode(LPTREE node) {
    	printf("%c\t", node->data);
    }
    

    接下来是前序遍历,看我上一个博客,前序遍历是根 左 右,所以我们走到根节点就打印,然后访问左节点,以这个节点作为根节点,打印一下,然后走到没有左节点的时候,访问右节点,右节点作为根节点。。。。。循环往复,这就是递归实现

    void printbypre(LPTREE root) {
    	if (root != NULL) {//根节点不为空的时候
    		printnode(root);//先打印根节点
    		printbypre(root->Lchild);//打印过根节点,然后就访问左节点,吧左节点当作下一个的父节点
    		printbypre(root->Rchild);//这个应该就是没有左节点的时候就返回到这里来了,也就是开始以右节点为根节点往下递归
    	}
    }
    

    我们来创建这样的树来检查一下前序遍历:
    在这里插入图片描述
    主函数:

    int main() {
    	LPTREE A = createnode('A');
    	LPTREE B = createnode('B');
    	LPTREE C = createnode('C');
    	LPTREE D = createnode('D');
    	LPTREE E = createnode('E');
    	LPTREE F = createnode('F');
    	LPTREE G = createnode('G');
    	tree(A, B, C);
    	tree(B, D, NULL);
    	tree(D, NULL, E);
    	tree(C, NULL, F);
    	tree(F, G, NULL);
    	printf("前序遍历:\n");
    	printbypre(A);
    

    在这里插入图片描述
    效果图
    证明是正确的
    那么, 中序遍历是,左 根 右 ,那么就是先是访问到最左边的节点作为根节点打印,然后它的根节点打印,返回到根节点(递归回去),然后访问右孩子的节点,循环往复,那么实现过来其实跟上面的没什么区别
    代码:

    void printbymid(LPTREE root) {
    	if (root != NULL) {
    		printbypre(root->Lchild);
    		printnode(root);
    		printbypre(root->Rchild);
    	}
    }
    

    效果图:
    在这里插入图片描述
    聪明的小伙伴已经发现了一些亮点,只要调换顺序就可以了,当然你可以死背这个模板,但是最好还是理解一下这个递归过程,画画图,理解一下:

    void printbyhou(LPTREE root) {
    	if (root != NULL) {
    		printbypre(root->Lchild);
    		printbypre(root->Rchild);
    		printnode(root);
    	}
    }
    

    效果图:
    在这里插入图片描述


    其实吧,这样的结构跟链表十分相似,所以学过链表结构很容易掌握,不过不容易理解的就是递归遍历这个过程了吧。
    好了今天的数据结构二叉树的博客就到这了。

    展开全文
  • 其他人都复工了 我还在家远程办公中...... ————————————下面正文———————————— 一.... 1.1.... 完全二叉树与其他二叉树不一样的地方每个根结点一定会有左... 那么使用什么存储方法可以更好...

    其他人都复工了

    我还在家远程办公中......

    ——————————下面是正文——————————

    一.存储

           1.1.完全二叉树的存储

            完全二叉树与其他二叉树不一样的地方是每个根结点一定会有左结点和右结点,不存在啥只有一个结点的情况,如以下图即为一个经典的完全二叉树:    

                 

           那么使用什么存储方法可以更好地对完全二叉树进行遍历查找呢?答案是数组。将结点编号当做数组下标进行存储,可通过计算快速得出想要的结点的左右结点、父结点什么的,下面给出一个简易版的使用数组进行存储的代码:

    	int temp = 0;
    	int left, right, father = 0;
    	char Binary_Tree[9] = { 'A','B','C','D','E','F','G','H','I' };
    	printf("请输入想要查询其结点的根结点:");
    	scanf("%d", &temp);
    	left = 2 * temp; if (left >= 10) left = NULL;
    	right = 2 * temp + 1; if (right >= 10) right = NULL;
    	father = temp / 2; if (father >= 10||father <=0) father = NULL;
    
    	printf("左结点为:%d,其值为:%c,右结点为:%d,其值为:%c,其父结点为:%d,其值为:%c\n",left,Binary_Tree[left-1],right,Binary_Tree[right-1],father,Binary_Tree[father-1]);
    	system("pause");

           当然,在选择一些特殊结点,如“7”结点这种没有左右结点的需要设置一些特殊提醒基础,但上面的代码里没有给出。在代码里有个关键的地方是左右结点以及夫结点的计算,这个计算就不详细解释,来观察下编译的结果:

                      

            1.2.一般二叉树的存储

            和完全二叉树不同的是,一般二叉树没有那么“娇贵”,每个结点可有或无左或有结点,如以下二叉树:

                       

             对于这种一般二叉树也是可以用数组来进行数据存储的,但需要将没有的结点进行补齐

                        

             如此,在没有结点的地方手动将其补上,既可以和完全二叉树一样用数组进行存储,但是有个问题是当缺失的结点数量比较多时,数组存在很多空缺,会在一定程度上造成资源空间浪费。所以,更好的办法是使用链表的方法对一般二叉树进行一个存储,链表中设置两个指针分别指向其左右结点:

                                                                  

           创建一个二叉链表的代码网上有很多,在此献上按照本人想法瞎搞的一份代码,代码是通过先序遍历的方法对数据进行存储,先序遍历是二叉树的一种遍历方式,可表现为:

                                                             第一步:访问其父结点

                                                             第二步:访问其左结点

                                                             第三步:访问其右结点

            根据线序遍历的方法,逐个逐个对数据进行输入,但需要注意的是输入的数据是根据先序遍历的方法进行存储的:

    Node* createTree()
    {
    	int temp;
    	printf("请输入第%d个节点:",++i);
    	scanf("%d", &temp);
    	Node *n = NULL;
    
    	if (temp == 0) return NULL;
    	else
    	{
    		n = (Node*)malloc(sizeof(Node));
    		n->data = temp;
    		n->left = createTree();
    		n->right = createTree();
    	}
    
    	return n;
    }

             如有图下这样一幅二叉树:

                                                                   

             则通过以下输入即可得到以上的二叉树:

                                                                        

    展开全文
  • 不过没有什么时间去 尝试 下面我的代码: 头文件 宏定义 和结构: 这里按照题目要求,使用了同时含有双亲和左右孩子的结构,事实证明,有了双亲结点的话,计算结点的层数和寻找它的路径都变得十分简单 #include&...
  • 可以这样考虑,链域一共有2*N个,(每个点有两个鲢鱼),对于除了根节点以外的每个点都有一个父亲节点,所以一共有N-1个指针指向某个节点,形成N-1个有东西的链域(减1即父亲节点)所以一共有2*N-(N-1)=N+1个链...
  • 想了好久,查了不少资料,我这个“采集”终于也弄出来了,希望对需要的人有帮助,有什么不对的地方请私信我!谢谢! #include<stdio.h> #include<stdlib.h> typedef char elemtype;//树中元素的类型 ...
  • 2.什么是双向链表:跟正常链表比 多一个头指针 尾指针 ##二、思路 看到二叉搜索树转换成 一个双向链表,我们可以考虑BST的中序遍历 因为BST中序遍历有序的。但如何将他们链接在一起就是我们需要考虑的 ...
  • 首先什么二叉搜索树? 如果一个节点的左子树不为空,那么左子树上的数字均小于该节点的值;如果右子树不为空,则右子树上的所有节点的值均大于该节点。 怎么转换成一个排序的双向链表? 这一个递归的思想: ...
  • 首先从题目描述来看,不读个3、4遍可能不知道它是什么意思,同时又考察了链表和二叉树这两种结构。嗯不知道牛客难度标记是不是越小越不好做,很魔性。 正题: 先来看一棵简单的二叉搜索树 由他变成一个有序的双向...
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 这道题我本身的思路也递归,但是整个过程没有用到返回值,不知道为什么我总是不太会...
  • ** 有序链表转换二叉搜索树 LeeCode109 ** 算法思想: 考虑有序链表转化为二叉搜索树前,可以先考虑有序数组转化为二叉树。有序数组转化为二叉树的关键在于分治思想,对于...什么是快慢指针? 假设两个指针一个为slo...
  • #二叉搜索树转化为双向链表,不理解29-32为什么一直返回pRootOfTree.left,顺便贴下和老外的聊天记录 #已解决,29-32行的问题:因为这在线测试,他要返回链表头节点才能通过,比如我给出的例子,他要返回1才能通过...
  • 首先什么是二叉搜索树呢?就是根的左子树的值全部小于根节点的值,根的右子树的值全部大于根节点的值(递归下去,其左子树与右子树也满足该性质)巧的是二叉搜索树的中序遍历递增的,刚好满足题目的排序要
  • 什么是二叉搜索树? 二叉搜索树(二叉排序树)或者一颗空树,或者具有一下性质的二叉树: 1、如果左子树不为空,则左子树所有节点小于根节点 2、如果右子树不为空,则右子树所有节点大于根节点 3、它的左右子树...
  • 109 有序链表转换二叉搜索树 给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树指一...首先要了解什么是高度平衡二叉搜索树 题目已经告诉了一个高度平衡二叉树
  • 主要明白什么是二叉搜索树 二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者一棵空树,或者具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;...
  • 这道题将有序链表转化成高度平衡的二叉查找树。 但由于我最开始在服务器那台机器上的网页编辑中写的,出现了一个比较玄学的错误,截图如下: 就算在本地编译器中能跑通,在线上也显示这个错误┓( ´∀` )┏ 百度...
  • 二叉搜索树和排序链表什么关系? 二叉搜索树也一种排序的数据结构,所有的左子节点的值都小于根结点的值,所有右子节点的值都大于根节点的值。那我们可以根据这个特性吧BST转换成排序的双向链表。我们只要把原先...
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。 解题思路:二叉搜索树的特点当前节点的左子树的值小于当前节点,当前节点的右子树的...
  • 几乎每一位码士的编程起点都C,在玩过了Java、C#、PHP、Python之后,...如何创建二叉树如何遍历二叉树如何创建二叉链表怎样使用递归算法 这一道非常老土但又十分经典的数据结构题,或许很多人会说自己...
  • 昨天去了汉口一屠宰场 观看一家公司如何卸猪 宰猪比较血腥的场景我就没看了 至于我会什么会有如此雅兴去捣鼓这事儿 那因为最近参加的一个比赛 ...109-有序链表转换二叉搜索树 给定一个单链表,其中的元...
  • 链表二叉数 之前我们接触过的数据结构有数组和对象。 数组变量的容器,数组在创建的时候就已经规定了大小。如果想要存储更多的数据我们就需要创建一个新的更大的数组,接着把旧数组的内容传递的到新数组,再加上...
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 思路: 中序遍历。 版本1不知道为什么提交上去反馈死循环,样例也没有找到不对的。版本2.。...
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 复杂问题可以分为几个小的简单的问题,并递归的解决。和前几天我没做出来的题有相似之处...
  • 题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的...扩展,什么是双向链表? https://www.cnblogs.com/bigsai/p/11351153.html (转载) -------------------------...
  • 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点,只能调整树中节点的指针的指向。  开始没什么思路。但是想到二叉树的所有题目几乎都可以用递归来做。就想到先找根...
  • 不知道为什么, 之前好几篇博客都被一些不出名的小网站抄了。 其实我写这些博客的目的练手, 但是当知道被人抄了而自己却毫不知情, 还是有些蛋疼的。 代码如下: 1 struct TreeNode; 2 typedef shared_ptr...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 691
精华内容 276
关键字:

二叉链表是什么