精华内容
下载资源
问答
  • 一种C语言字典树创建和搜索示例,可以创建一种无论增加多少单词,搜索速度依然 = 该语言字母数 * 单词长度 效率存储结构。一个demo
  • #include<stdio.h> #include<stack> using namespace std; typedef struct TNode{ char data; struct TNode *left, *right; }TNode, *BTree; void preorder(BTree T){ if(T){ ...
    #include<stdio.h>
    #include<stack>
    using namespace std;
    
    typedef struct TNode{
    	char data;
    	struct TNode *left, *right;
    }TNode, *BTree;
    
    void preorder(BTree T){
    	if(T){
    		printf("%c", T->data);
    		preorder(T->left);
    		preorder(T->right);
    	}
    }
    
    void inorder(BTree T){
    	if(T){
    		inorder(T->left);
    		printf("%c", T->data);
    		inorder(T->right);
    	}
    }
    
    void postorder(BTree T){
    	if(T){
    		postorder(T->left);
    		postorder(T->right);
    		printf("%c", T->data);
    	}
    }
    
    void createPost(BTree &T, char *post);
    
    int eval(BTree T);
    
    int main(){
    	BTree T = NULL;
    	char post[80];
    	scanf("%s", post);
    	createPost(T, post);
    	preorder(T); printf("\n");
    	inorder(T); printf("\n");
    	postorder(T); printf("\n");
    	printf("%d\n",eval(T));
    }
    void createPost(BTree &T, char *post){
    	BTree t;
    	stack<BTree> s;
    	for(char *str=post;*str!='\0';str++)
    	{
    		if (*str>='0'&&*str<='9')
    		{
    			T=new TNode;
    			T->data=*str;
    			T->left=NULL;
    			T->right=NULL;
    			s.push(T); 
    		}
    		else
    		{
    			T=new TNode;
    			T->data=*str;
    			T->right=s.top();s.pop();
    			T->left=s.top();s.pop();
    			s.push(T);
    		}
    	}
    }
    int eval(BTree T){
       if(T==NULL) return NULL;
       else if(T->data>='0'&&T->data<='9') return (T->data-'0');
       //数则是叶,无需再次递归 
       else switch(T->data){//遇到操作符继续递归 
        case '+':
    		return eval(T->left)+eval(T->right);break;
        case '-':
    		return eval(T->left)-eval(T->right);break;
        case '*':
    		return eval(T->left)*eval(T->right);break;
        case '/':
    		return eval(T->left)/eval(T->right);break;
       }
    }
    
    
    展开全文
  • C语言二叉排序树的创建

    千次阅读 2017-09-25 16:11:43
    在实际应用中,很多场合会涉及到数据结构中的树,二叉树作为最简单的树,则有很多重要用处。...下面以一维数组来创建一棵二叉排序。  #include "stdafx.h" #include #include using namespace std; typed

            在实际应用中,很多场合会涉及到数据结构中的树,二叉树作为最简单的树,则有很多重要的用处。而二叉树又细分为好多类型,在此只说二叉排序树,这种类型的树有个比较好的特性就是,中序遍历这棵树,你将得到一个按升序排列的数组。下面以一维数组来创建一棵二叉排序树。

         

    #include "stdafx.h"
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    typedef struct Tree
    {
    	int Data;
    	struct Tree *LeftTree;//左子树
    	struct Tree *RightTree;//右子树
    }TreeNode, *TreeNodeP;
    
    void InsertNode(TreeNodeP &TreeRoot, int Data)
    {
    	//新建一个节点
    	TreeNodeP NodeP;
    	NodeP = (TreeNodeP)malloc(sizeof(TreeNode));
    	NodeP->Data = Data;
    	NodeP->LeftTree = NodeP->RightTree = NULL;
    
    	//如果树根还没创建,那就把当前新建的节点赋给根吧
    	if (TreeRoot == NULL)
    	{
    		TreeRoot = NodeP;
    	}
    	//新插入的节点数值比根的小或等,走根的左边
    	else if (Data <= TreeRoot->Data)
    	{
    		//左子树递归结束处
    		if (TreeRoot->LeftTree == NULL)
    			TreeRoot->LeftTree = NodeP;
    		//左递归
    		else
    			InsertNode(TreeRoot->LeftTree, Data);
    	}
    	//新插入的节点数值比根的大,走根的右边
    	else if (Data > TreeRoot->Data)
    	{
    		//右子树递归结束处
    		if (TreeRoot->RightTree == NULL)
    			TreeRoot->RightTree = NodeP;
    		//右递归
    		else
    			InsertNode(TreeRoot->RightTree, Data);
    	}
    }
    
    void TraveseTreeNode(TreeNodeP TreeRoot, int Mode)
    {
    	if (TreeRoot)
    	{
    		//先序遍历
    		if (Mode == 1)
    		{
    			printf("NodeData=%d\n", TreeRoot->Data);
    			TraveseTreeNode(TreeRoot->LeftTree, Mode);
    			TraveseTreeNode(TreeRoot->RightTree, Mode);
    		}
    		//中序遍历
    		else if (Mode == 2)
    		{
    			TraveseTreeNode(TreeRoot->LeftTree, Mode);
    			printf("NodeData=%d\n", TreeRoot->Data);
    			TraveseTreeNode(TreeRoot->RightTree, Mode);
    		}
    		//后序遍历
    		else if (Mode == 3)
    		{
    			TraveseTreeNode(TreeRoot->LeftTree, Mode);
    			TraveseTreeNode(TreeRoot->RightTree, Mode);
    			printf("NodeData=%d\n", TreeRoot->Data);
    		}
    	}
    }
    
    
    int main()
    {
    	TreeNodeP Tree = NULL;
    
    	int A[11] = { 1, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9 };
    	for (int i = 0; i < 11; i++)
    	{
    		InsertNode(Tree, A[i]);
    	}
    	TraveseTreeNode(Tree, 2);
    	
    	return 0;
    }
    
    
           运行程序,将得到:1 2 3 4 6 7 9 13 17 18 20 。不过二叉排序树有个不好的方面是,每个节点上左右树的深度可能差别比较大,比如有个数组为 1 2 3 4 6 7 9 13 17 18 20,它的树就是1→ 2 →34 6913171820

    这棵树根本没左子树啥事。即节点上的左右子树的深度失衡,这个问题将由平衡二叉树来解决。后面有时间写一下。

    展开全文
  • C语言版字典树的 创建与 搜索

    千次阅读 2018-11-12 00:14:25
    那~我学习字典树的时候恰好也在学习数据结构树这一章节所以接受起来还是蛮快的,我瞧得不好,也不快,我比较期待学习哈希表和图的 ,尤其是图 因为之前建模的时候有过图的题,那时候还没学离散数学的图论,很瞎。...

    这个由来是我写了KMP,然后看了AC自动机,别人提到AC自动机还需要字典树,所以我就看了。(给自己提个醒勤于复习,还有  先生你还没看 KMP的优化算法 )

    那~我学习字典树的时候恰好也在学习数据结构树这一章节所以接受起来还是蛮快的,我瞧得不好,也不快,我比较期待学习哈希表和图的 ,尤其是图 因为之前建模的时候有过图的题,那时候还没学离散数学的图论,很瞎。学校其实也没有细细的将数据结构。唉不说了,每个人都有自己的经历;

    这个树很多东西,像什么前缀后缀我都只是了解了还有细看;
     

    树根结点是不保存字符(一般是这样额);

    那~简要介绍一下我的这个代码吧:

    我是想要若干输入单词,然后输入单词再查一下该单词在不在里面;

    我用结构体来存储结点,其中有一个结构体指针类型的数组,(这个数组的每一个元素都是一个指针,结构体类型的,呵呵)

    结构体数组只有26个存储26个小写字母只能是小写字母!!!只能是小写字母!!!只能是小写字母!!!

    然后一个v:可以表示当前是第几个单词,一个b;

    然后我说一下:它并非真正的将 单词的字符 存到节点上,而是利用每一个小写字母与a之间的相对大小,这样默认的就将26个小写字母的位置固定下来了;

    我先创建了一个根节点,利用单独的一个函数Creatgen:

    每次输入一个字符串都调用一次Insert_DanCi()函数;

    Insert_DanCi()函数:先 以 输入第一个字符串 为例 :

    一个字符串进来先求他的长度,然后以长度为限制做循环,因为是第一个字符串,在循环过程中只会经历if ,结束;

    在if里面,他实现开辟一个空间并用q指向这块空间,会将这个新的还未连接的结点 的结构体数组全变成NULL 然后 v进行相应的变化···················第一个字符保存的时候,v在该节点的值是1;

    然后第二个字符串回传递过来:

    这时就会从第一个字符查看它的位置是否已经被占据(被占据的话就是相同的前缀),进行else;

     

    进行若干步之后一个树就算  建好了~~~

     

    现在,要记住这棵树已将成型了,是作为样本给我们检测的了;

    在搜索的时候,从将传过来的s字符串从 数组的第一个字符 (s[0])开始,如果该位置是空表示没有这个字符直接退出就行了;

    若果第一个有的话就依次往下遍历字符串;

    就这样吧 ~~~~

    对了我在输入的时候出现过一个问题:我一开始有个m值想让m=3,然后循环输入三个字符串,但是只能输入两个!!! 后来我找了 一下资料知道是之前对 gets()函数理解不深导致的;

    我在这里再单独的说一下吧:

     

    Gets(a);

    Gets(b);

    Gets(c);

    当输入了a数组的最后输入回车符,这是a数组就输入结束了,回车符保存在缓冲区中;

    让b数组接受这个回车符,然后b就会 胎死腹中 只有一个 b[0]=’\0’  ;

    这时通过键盘输入字符会全部存到c数组中直到遇到一个回车符或者EOF ,同样,最后的回车符也是放在缓冲区中;

      赵先生,请。

     

     

     

    #include <stdio.h>
    #include <stdlib.h>
    #define Max 26
    struct Tree{
        struct Tree *next[Max];//next[0],next[1]每个数组元素都是一个指针即地址;
        int v;
        int b;
    };
    
    
    
    struct Tree* Creatgen(){
        int i=0;
        struct Tree *p,*root,*q;
        root=(struct Tree *)malloc(sizeof(struct Tree));
        for(i=0;i<Max;i++){
            root->next[i]=NULL;
            root->v=0;
        }
        return root;
    }
    
    //这是仅仅的  单纯26个小写字母或者26个大写字母
    //并非真是存储而是采用相对位置;
    int Insert_DanCi(char s[],struct Tree *root){
        int i,j,m,n,id;
        struct Tree *p,*q;
        p=root;
        m=strlen(s);
        for(i=0;i<m;i++){
            id=s[i]-'a'; //以a为标准 看一看 当前字符应该在指针数组的哪个位置。
            //表示该位置还没有被占据,意思就是该字符在当前的这行是首次出现
            if(p->next[id]==NULL){
                q=(struct Tree *)malloc(sizeof(struct Tree));
                q->v=1;//可以看到并没有向节点内存储 字符串中的而字符,而是按照相对位置进行安排,已经默认0—a,1-b,2-c
                for(j=0;j<Max;j++){
                    q->next[j]=NULL;
                }
                //*接受上一个结点的v值,要记住在for循环中执行if语句表示这是一个单词还没存储结束。
                q->v=p->v;
                q->v++;
                //*
                p->next[id]=q;
                p=p->next[id];
                //p=q;
            }
            //当参数传来第一条字符串的时候,只会执行if语句;当第二条字符串传来时,才会查看是不是有公共前缀
            //当单词的该位置的字符与当前节点存储的字符相同时,就表达为该节点  被占领,然后  p会指向被占领的结点
            //为'a'为标准的相对位置,默认的规定了每个字符的位置,这也是判断一个字符有没有占据一个空间位置的 要领。
            else{
                p=p->next[id];
            }
        }
        p->b='&';
        return 0;
    }
    
    
    int Search(char s[],struct Tree *root){
        int i=0,j,m,n;
        int id=0,con[id];
        struct Tree *p,*q;
        p=root;
        m=strlen(s);
        for(i=0;i<m;i++){
            id=s[i]-'a';
            //表示这棵树的这个位置已经未被占据,即没有单词
            if(p->next[id]==NULL){
                    printf("查无此人\n");
                    break;
            }
            //表示这棵树的这个位置已经被占据,也表示和这个单词的这个字母相同
            else{
                p=p->next[id];
            }
        }
        if(i==m){
            printf("欢迎大人,大驾光临!!!\n");
        }
        return 0;
    }
    
    
    int main(){
        int k=0;
        int i=0,j=0,m=0,id=0;
        char s[123];
        int con[1234];
        struct Tree *p,*root;
        //创建树根;
        root=Creatgen();
        scanf("%d",&m);
        //插入单词,每输入一个单词,调用一次插入单词函数;
    
    
        //下面这种输入方式:只能输入m-1个字符串,这是为什么呢?
        // 因为:输入第一个字符串的时候没有问题,直到第一次输入回车符,将回车符保存在缓冲区并被第二个gets()函数是被,第二个gets()函数就胎死腹中了 只有一个'\0';
        //所以,他的数目少一个只有m-1个;;;下面是我改良的;
        //for(i=1;i<=m;i++){
        //    gets(s);
        //    Insert_DanCi(s,root);
        //    memset(s,'0',sizeof(s));
        //}
    
    
        //这样虽然 回车符 也会被 字符数组接受 并作为为一个字符串 (胎死腹中的字符串)
        //同样我把这种方法用在 寻找 单词上面;
            while(gets(s)!=NULL){
                Insert_DanCi(s,root);
                memset(s,'0',sizeof(s));
            }
    
    //还要注意 while(!=EOF)和while(!=NULL)都是输入CTRL + Z结束
    
        //怎么遍历输出树(单词)?
        //接下来就是了
        //输入一个要查找的单词
            //gets(s);
            //Search(s,root);
        while(gets(s)!=NULL){
            Search(s,root);
        }
    
        return 0;
    }
    

     

     

     

    展开全文
  • c语言 树的层序遍历

    2021-05-05 20:05:26
    运行结果正确 层序遍历比先序递归和非递归都要简单。 #include <stdio.h> #include <stdlib.h> typedef struct tree_...//创建 int creat_tree(tree **t){ int val; scanf("%d",&val); if

    运行结果正确
    层序遍历比先序递归和非递归都要简单。
    在这里插入图片描述

    #include <stdio.h>
    #include <stdlib.h>
    typedef struct tree_node{
    	int val;
    	struct tree_node *left;
    	struct tree_node *right;
    }tree,*tree_point;
    //创建新树
    int creat_tree(tree **t){
    	int val;
    	
    	scanf("%d",&val);
    	if(val==-1){
    		*t=NULL;
    	}
    	else{
    		*t=(tree*)malloc(sizeof(struct tree_node));
    		(*t)->val=val;
    		printf("输入%d左节点\n",val);
    		creat_tree(&((*t)->left));
    		printf("输入%d右节点\n",val);
    		creat_tree(&((*t)->right));
    		
    	}
    	return 1;
    } 
    //层序遍历
    void se_tra(tree_point	 t){
    	//创建队列
    	 tree_point base[20],temp;
    	 int front=0;
    	 int rear=-1;
    	 tree_point t1=t;
    	 //将根节点塞进去
    	base[++rear]=t1;
    	while(rear>=front){
    		temp=base[front++];
    		printf("%d ",temp->val);
    		if(temp->left){
    			base[++rear]=temp->left;
    		};
    		if(temp->right){
    			base[++rear]=temp->right;
    		}
    	}
    	printf("\n");
    	 
    } 
    int main(){
    	tree *t;
    	printf("输入根节点\n");
    	creat_tree(&t);
    	printf("\n层序遍历结果为\n");
    	se_tra(t);
    	return 0;
    }
    
    展开全文
  • /* *创建哈弗曼树 *创建树 *每次遍历最小的两个节点 *译码 *遍历树(解码的过程) */ #include<stdio.h> #include<...#define m (2*n-1)//树的节点总数 #define MAXVALUE 1000 //权重最大值...
  • 数据结构c语言版哈夫曼与select()函数
  • 1. 课程设计题目标题: B树的基本操作算法(创建、插入、删除) 问题描述:  在计算机科学中,B树在查找、访问、插入、删除操作上时间复杂度为O(log2~n),与自平衡二叉查找树不同的是B树对大块数据读写的操作有更...
  • AVL树的创建--C语言实现

    千次阅读 2018-03-08 11:52:04
    AVL树是一种自平衡(Self-balancing)二叉查找树(Binary Search Tree),要求任何一个节点的左子树和右子树的高度之差不能超过1。 AVL树的插入操作首先会按照普通二叉查找树的插入操作进行,不同的是在成功插入一个...
  • C语言——动态创建二叉树 什么是就是一种数据结构,常见数据结构分为散列式、线性、树状、图状。而二叉树是树状数据结构中典型代表。它为什么特殊呢?因为它最多有两个分支,它有5种基本类型,分为空...
  • 2.右子树的所有节点大于根节点 3.左右子树均为二叉查找树 思想: 1.各种操作均利用递归来实现 2。基本操作有创建,插入,删除,查找元素,最大值最小值这里对删除操作进行解释 删除: (1)若所要删除的节点为叶子...
  • 这里的二叉排序树的创建是根据课本上写的,其中掺杂了递归思想,之前的写的二叉树的创建是为非递归的方法https://blog.csdn.net/qq_43402544/article/details/109228383。 完整代码如下: #include <stdio.h> ...
  • 1.二叉搜索树的概念 二叉搜索树又称二叉排序树,它或者是一棵空数,或者是具有以下性质的二叉树: 1. 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值. 2. 若它的右子树不为空,则右子树上所有节点...
  • C语言二叉树创建(一定看懂)

    万次阅读 多人点赞 2018-06-02 14:01:36
    先贴一个百度出来的二叉树的图 二叉树 就是首先得有一个根节点....创建一棵树得现有这棵树的结点和树根     首先来声明一个树的结点   typedef struct node{ //树的结点 int data; struct no...
  • 我们已经成功解析了C语言的语法,接下来我们计划分两步走,一是开发一个C语言的解释器,也就是不编译,读取足够源代码后直接执行。二是开发一个C语言的编译器,将C语言转换为java字节码,然后用java虚拟机来执行...
  • 红黑树创建和插入—C语言

    千次阅读 2018-09-12 22:45:04
    红黑树—C语言 绝望ing…… 先知道红黑树是啥:每个节点带颜色(红/黑)的二叉查找树。 红黑树的特性:①每个节点非红即黑;②根和叶子(哨兵NIL)是黑色;③每个红色节点的俩娃都是黑色;④每个节点到其所有后代...
  • 代码如下。具体处理见注释。个人原创,非官方。 转载请注明出处。如果发现错误,欢迎大家给我留言。 #include .../**定义形结构*/ typedef struct Tree { TREE_TYPE value; struct Tree *left;
  • 为了方便理解二叉树,我简单的介绍一下树,树顾名思义有根和树杈,叶子,比如: 这是一颗以 A为根结点(根节点:没有前驱),I,J,G,K 为...C为F,G的双亲结点,A为E,F,G,H的祖先,树的度:每一个结点的孩子结点...
  • [] 哈夫曼创建 | 编码)-C语言

    千次阅读 2018-11-07 10:05:01
    文章目录编码问题哈夫曼相关概念哈夫曼二叉树哈夫曼二叉树特点代码哈夫曼n叉构造 编码问题 等长码 权值相同时,效率最高 翻译很方便,定长 不等长码 缺点:有二义性,翻译时候有困惑,不...
  • printf("请输入要查找值\n"); scanf("%d",&n); // printf("递归查找:\n") ; //(s=searchbst1(bstree,n))==NULL ?printf("未找到\n"):printf("找到%d\n",s->key); printf("非递归查找:\n") ; // (s=...
  • 创建二叉搜索树的过程很简单,第一个数字作为根,第二个数字,如果比根大,则作为根的右子树,如果比根小,则作为根的左子树。一次类推。对一棵二叉搜索树进行中序遍历,可以的到一个有序的序列。 代码 #include <...
  • 二叉排序树的c语言实现,创建、插入、删除、查找……
  • 3)最后按照前序遍历方式访问根节点右子 二叉树中序遍历: 1)首先按照中序遍历方式访问根节点左子树 2)然后访问根节点 3)最后按照中序遍历方式访问根节点右子 二叉树后序遍历: 1)首先按照后序...

空空如也

空空如也

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

c语言树的创建

c语言 订阅