c二叉树搜索文件|C语言二叉树遍历查找问题

㈠ C/C++ 搜索二叉树相关

#include "iostream"#include "string"using namespace std;string pro;string origin;struct Tree{ char name; Tree* l; Tree* r; Tree() { l=r=NULL; }};bool equal(Tree *a,Tree *b){ if(a==NULL&&b==NULL) return true; else if(a==NULL&&b!=NULL||a!=NULL&&b==NULL) return false; if (a->name==b->name) return equal(a->l,b->l)&&equal(a->r,b->r); return false;}void insert(Tree** root,char c){ if (*root==NULL) { *root=new Tree; (*root)->name=c; } else { if (c<(*root)->name) insert(&(*root)->l,c); else insert(&(*root)->r,c); }}int main(){ int n,in; while (scanf("%d",&n)!=EOF&&n!=0) { cin>>origin; Tree *t1=NULL; for(in=0;in<origin.length();in++) insert(&t1,origin[in]); for (int i=0;i<n;i++) { cin>>pro; Tree *t2=NULL; for(in=0;in<pro.length();in++) insert(&t2,pro[in]); if(equal(t1,t2)) cout<<"YES"<<endl; else cout<<"NO"<<endl; } }}——来自网络。。

㈡ C语言二叉树遍历查找问题

二叉树的遍历分为以下三种:

先序遍历:遍历顺序规则为【根左右】

中序遍历:遍历顺序规则为【左根右】

后序遍历:遍历顺序规则为【左右根】

什么是【根左右】?就是先遍历根,再遍历左孩子,最后遍历右孩子;

举个例子,看下图:

先序遍历:ABCDEFGHK

中序遍历:BDCAEHGKF

后序遍历:DCBHKGFEA

以中序遍历为例:

中序遍历的规则是【左根右】,我们从root节点A看起;

此时A是根节点,遍历A的左子树;

A的左子树存在,找到B,此时B看做根节点,遍历B的左子树;

B的左子树不存在,返回B,根据【左根右】的遍历规则,记录B,遍历B的右子树;

B的右子树存在,找到C,此时C看做根节点,遍历C的左子树;

C的左子树存在,找到D,由于D是叶子节点,无左子树,记录D,无右子树,返回C,根据【左根右】的遍历规则,记录C,遍历C的右子树;

C的右子树不存在,返回B,B的右子树遍历完,返回A;

至此,A的左子树遍历完毕,根据【左根右】的遍历规则,记录A,遍历A的右子树;

A的右子树存在,找到E,此时E看做根节点,遍历E的左子树;

E的左子树不存在,返回E,根据【左根右】的遍历规则,记录E,遍历E的右子树;

E的右子树存在,找到F,此时F看做根节点,遍历F的左子树;

F的左子树存在,找到G,此时G看做根节点,遍历G的左子树;

G的左子树存在,找到H,由于H是叶子节点,无左子树,记录H,无右子树,返回G,根据【左根右】的遍历规则,记录G,遍历G的右子树;

G的右子树存在,找到K,由于K是叶子节点,无左子树,记录K,无右子树,返回G,根据【左根右】的遍历规则,记录F,遍历F的右子树;

F的右子树不存在,返回F,E的右子树遍历完毕,返回A;

至此,A的右子树也遍历完毕;

最终我们得到上图的中序遍历为BDCAEHGKF,无非是按照遍历规则来的;

根据“中序遍历”的分析,相信先序遍历和后序遍历也可以轻松写出~

㈢ C语言写二叉树查找,帮忙给看看~不知道错误在哪里

你的创建函数很有问题,人家一般两种格式:T = Creat();或者:Create(T); //T应该为指针,不应该为非指针你怎么把这两种混用了?即是要么在Create()里分配内存然后返回该树的地址,要么就是把T作为参数传进入,再分配,但这种只能是把指针传进去,不把指针传进去不行,值传递该知道不会改变实参的内容吧?还有,没有分配到内存的判断时,是应该退出的,你怎么还继续操作了呢?没分配到内存再操作肯定会出现异常的PS:本来想帮你改一下的,但复制粘贴到VS没换行,用word改有点麻烦,你自己再改改吧

㈣ 二叉树结点的查找C语言实现

#include <stdio.h>#include <stdlib.h>#include <malloc.h>typedef struct bitnode{char data;struct bitnode *lchild, *rchild;}bitnode, *bitree;void createbitree(t,n)bitnode ** t;int *n;{char x;bitnode *q;*n=*n+1;printf("\n Input %d DATA:",*n);x=getchar();if(x!=’\n’) getchar();if (x==’\n’)return;q=(bitnode*)malloc(sizeof(bitnode));q->data=x;q->lchild=NULL;q->rchild=NULL;*t=q;printf(" This Address is: %o, Data is: %c,\n Left Pointer is: %o, Right Pointer is: %o",q,q->data,q->lchild,q->rchild);createbitree(&q->lchild,n);createbitree(&q->rchild,n);return;}void visit(e)bitnode *e;{printf(" Address: %o, Data: %c, Left Pointer: %o, Right Pointer: %o\n",e,e->data,e->lchild,e->rchild);}void preordertraverse(t)bitnode *t;{if(t){visit(t);preordertraverse(t->lchild);preordertraverse(t->rchild);return ;}else return ;}void countleaf(t,c)bitnode *t;int *c;{if(t!=NULL) { if (t->lchild==NULL && t->rchild==NULL) {*c=*c+1; } countleaf(t->lchild,c); countleaf(t->rchild,c); } return;}int treehigh(t)bitnode *t;{int lh,rh,h; if(t==NULL) h=0; else{ lh=treehigh(t->lchild); rh=treehigh(t->rchild); h=(lh>rh ? lh:rh)+1; } return h;}main(){bitnode *t; int count=0;int n=0;printf("\n Please input TREE Data:\n");createbitree(&t,&n);printf("\n This is TREE Struct: \n");preordertraverse(t);countleaf(t,&count);printf("\n This TREE has %d leaves ",count);printf(" , High of The TREE is: %d\n",treehigh(t));}

㈤ 数据结构与算法分析 —— C 语言描述:二叉树

二叉树(binary tree)是一棵树,其中每个节点的儿子都不能多于两个。

二叉树的一个性质是平均二叉树的深度要比 N 小的多,这个性质有时很重要。分析表明,这个平均深度为 ,而对于特殊类型的二叉树,即二叉查找树(binary search tree)。其深度的平均值是 。不幸的是,在最坏情况下,这个深度可以大到 N-1 的。

因为一棵二叉树最多有两个儿子,所以我们可以用指针直接指向它们。树节点的声明在结构上类似于双链表的声明,在声明中,一个节点就是由 key(关键字)信息加上两个指向其他节点的指针(Left 和 Right)组成的结构。

应用于链表上的许多法则也可以应用到树上。特别地,当进行一次插入时,必须调用 malloc 创建一个节点。节点可以在调用 free 删除后释放。

我们可以用在画链表时常用的矩形框画出二叉树,但是,树一般画成圆圈并用一些直线连接起来,因为二叉树实际上就是图(graph)。当涉及树时,我们也不显示地画出 NULL 指针,因为具有 N 个节点的每一棵二叉树都将需要 N+1 个 NULL 指针。

二叉树有许多与搜索无关的重要应用。二叉树的主要用处之一是在编译器的设计领域。

上图就是一个表达式树(expression tree)。表达式树的树叶是操作树(operand),比如常数或者变量,而其他的节点为操作符(operator)。由于这里所有的操作都是二元的,因此这棵特定的树正好是二叉树,虽然这是最简单的情况,但是节点含有的儿子还是有可能多于两个的。一个节点也有可能只有一个儿子,如果有一目减算符(unary minus operator)的情形。可以将通过递归计算左子树和右子树所得到的值应用在根处的算符操作中而算出表达式树 T 的值。上面里的例子中,左子树的值是“((3+1) 3)/((9-5)+2)”,右子树的值是“(3 (7-4)+6)”,因此整棵树的表达式就是图上的结果。

我们可以通过递归产生一个带括号的左表达式,然后打印出在根处的运算符,最后再递归地产生一个带括号的右表达式而得到一个(对两个括号整体进行计算的)中缀表达式(infix expression)。这种一般的方法(左,节点,右)称为中序遍历(inorder traversal);由于其产生的表达式类型,这种遍历很容易记忆。

另一个遍历策略是递归打印出左子树、右子树,然后打印运算符。如果我们应用这种策略于上面的树,则输出将是“31+3 95-2+/743- 6+-”。这种遍历策略一般称为后序遍历(postorder traversal)。

第三种遍历策略是先打印出运算法,然后递归地打印出右子树和左子树。同样的,应用这种策略于上面的树,则输出将是“-/ ++313-952+ 3-746”,这是一种不太常用前缀(prefix)记法,这种遍历策略为先序遍历(preorder traversal)。

这里我们只给出一种算法,来把后缀表达式转变成表达式树。这里的要点是,一次一个符号地读入表达式。如果符号是操作符,那么我们就建立一个单节点树并将一个指向它的指针推入栈中。如果符号是操作符,那么我们就从栈中弹出指向两棵树 和 的那两个指针( 的先弹出)并形成一棵新的树,该树的根就是操作符,它的左、右儿子分别指向 和 。然后将这棵新树的指针压入栈中。


赞 (0)