完整正确的C语言二叉树程序
#include
#include
#include
const int MaxLength=10;//结点个数不超过10个
typedef struct tree
{
char data;
struct tree *lchild,*rchild;
}tree;
//先序递归 建立二叉树
void Createbitree(tree* &T)
{
char ch;
ch=getchar();
if(ch=='#')
T=NULL;
else
{
T=(tree*)malloc(sizeof(tree));
T->data =ch;
Createbitree(T->lchild );
Createbitree(T->rchild );
}
}
//先序递归遍历
void PreOrderTraverse(tree* T)
{
if(T)
{
coutdata;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
//中序递归遍历
void InOrderTraverse(tree* T)
{
if(T)
{
InOrderTraverse(T->lchild);
coutdata;
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(tree* T)
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
coutdata;
}
}
//层序遍历
void LevelOrderTraverse(tree* T)
{
tree* Q[MaxLength];
int front=0,rear=0;
tree* p;
if(T)//根结点入队
{
Q[rear]=T;
rear=(rear+1)%MaxLength;
}
while(front!=rear)
{
p=Q[front]; //队头元素出队
front=(front+1)%MaxLength;
coutdata;
if(p->lchild)//左孩子不为空,入队
{
Q[rear]=p->lchild;
rear=(rear+1)%MaxLength;
}
if(p->rchild)//右孩子不为空,入队
{
Q[rear]=p->rchild;
rear=(rear+1)%MaxLength;
}
}
}
//主函数
void main()
{
cout<<"请按先序次序输入二叉树的数据:"<<endl;
tree* T;
Createbitree(T);
cout<<"二叉树的先序序列为:"<<endl;
PreOrderTraverse(T);
cout<<endl<<"二叉树的中序序列为:"<<endl;
InOrderTraverse(T);
cout<<endl<<"二叉树的后序序列为:"<<endl;
PostOrderTraverse(T);
cout<<endl<<"二叉树的层序序列为:"<<endl;
LevelOrderTraverse(T);
cout<<endl;
}
比如 1
2 3
4 5 6 7
按先序输入是124##5##36##7##
int TreeDelete(TreeNode *root,EleType data) //删除二叉树的结点
{
TreeNode *delp;
if(!root) return 0;
delp=Find(root,data);
if(!delp) return 0;
if(delp==root)
{
Destroy(root);
printf("Destroy the tree...");
exit(0);
}
if(delp->parent->lchild==delp) delp->parent->lchild=0;
if(delp->parent->rchild==delp) delp->parent->rchild=0;
Destroy(delp);
return 2;
}
int Destroy(TreeNode *root) //销毁二叉树
{
if(!root) return 0;
Destroy(root->lchild);
Destroy(root->rchild);
free(root);
printf("Destroy the tree...");
exit(0);
}
#include<stdio.h>
#include<stdlib.h>
#define maxsize 100
typedef struct btnode
{
int data ; //结点数据类型
struct btnode *lchild, *rchild; //定义左、右孩子为指针型
} bitree;
bitree *creat(bitree *t) //创建二叉树
{
bitree *s,*p,*q;
int x;
scanf("%d",&x);
while(x!=0)
{
s= ( bitree *)malloc(sizeof(bitree));
s->data=x;
s->lchild=s->rchild=NULL;
if(t==NULL)
t=s;
else
{
p=t;
while(p)
{
q=p;
if(s->data<p->data)
p=p->lchild;
else
p=p->rchild;
}
if(s->data<q->data)
q->lchild=s;
else
q->rchild=s;
}
scanf("%d",&x);
}
return(t);
}
bitree *insert(bitree *t) //插入结点
{
bitree *s,*p,*q;
int x;
scanf("%d",&x);
while(x!=0)
{
s= ( bitree *)malloc(sizeof(bitree));
s->data=x;
s->lchild=s->rchild=NULL;
if(t==NULL)
t=s;
else
{
p=t;
while(p)
{
q=p;
if(s->data<p->data)
p=p->lchild;
else
p=p->rchild;
}
if(s->data<q->data)
q->lchild=s;
else
q->rchild=s;
}
scanf("%d",&x);
}
return(t);
}
void search(bitree *t,int k) //查找数据
{
int flag=0;
while(t!=NULL)
{
if(t->data==k)
{
printf("已查到要找的数!\n");
flag=1;
break;
}
else
if(t->data<k)
t=t->rchild;
else
t=t->lchild;
}
if(flag!=1)
printf("没有找到要查找的数据!\n");
}
bitree *dele(bitree *t,int k) //删除数据
{
int flag;
bitree *p,*q,*s=NULL,*f;
f=t;
while(t!=NULL) //查找数据
{
if(t->data==k)
{
printf("已找到所查找的数!\n");
break;
}
else
if(t->data<k)
{
p=t;
t=t->rchild;
flag=0;
}
else
{
p=t;
t=t->lchild;
flag=1;
}
}
if(t->lchild==NULL&&t->rchild==NULL) //删除叶子结点
{
free(t);
if(flag==0)
p->rchild=NULL;
else
p->lchild=NULL;
}
else
{
if(t->lchild==NULL&&t->rchild!=NULL) //删除只有右子树的结点
{
if(flag==0)
p->rchild=t->rchild;
else
p->lchild=t->rchild;
free(t);
}
else
{
if(t->lchild!=NULL&&t->rchild==NULL) //删除只有左子树的结点
{
if(flag==0)
p->rchild=t->lchild;
else
p->lchild=t->lchild;
free(t);
}
else //删除左右子树都有的结点
{
p=t;
t=t->lchild;
q=t;
while(t->rchild)
{
q=t;
t=t->rchild;
}
if(t==q)
{
p->data=t->data;
p->lchild=t->lchild;
free(t);
}
else
{
p->data=t->data;
q->rchild=t->lchild;
free(t);
}
}
}
}
return(f);
}
void output(bitree * t) //实现二叉树的遍历
{
bitree *q[maxsize],*p;
int f,r;
q[0]=t;
f=r=0;
while (f<=r)
{
p=q[f];
f++;
printf("%d ",p->data);
if(p ->lchild!=NULL)
{
r++;
q[r]=p->lchild;
}
if (p->rchild!=NULL)
{
r++;
q[r]=p->rchild;
}
}
}
void main()
{
bitree *q=NULL,*r;
int m,n,x=1;
while(x==1)
{
system("cls");
printf(" ********************************\n");
printf(" 创建请按1\n");
printf(" 插入请按2\n");
printf(" 查找请按3\n");
printf(" 删除请按4\n");
printf(" 显示请按5\n");
printf(" 退出请按0\n");
printf(" ********************************\n");
scanf("%d",&m);
switch(m)
{
case 1:printf("请输入数据并以'0'结束\n");
r=creat(q);system("pause");break;
case 2:printf("请输入数据并以'0'结束\n");
r=insert(r);break;
case 3:printf("请输入要查找的数:");
scanf("%d",&n);
search(r,n);
system("pause");
break;
case 4:printf("请输入要删除的数:");
scanf("%d",&n);
r=dele(r,n);
printf("已删除输入数据!\n");
system("pause");
break;
case 5:output(r);system("pause");printf("\n");
break;
case 0:x=0;break;
}
}
}
#include<iostream>
using namespace std;
class Node
{
private:
char data;
Node* left;
Node* right;
public:
Node(int index,Node* lptr=NULL,Node* rptr=NULL)
{
data=index;
left=lptr;
right=rptr;
}
~Node(){}
Node* Getleft(){return left;}
void Setleft(Node* l){left=l;}
Node* Getright(){return right;}
void Setright(Node* r){right=r;}
char& Getdata(){return data;}
void Setdata(const int& index){data=index;}
friend class BinTree;
};
class BinTree
{
private:
Node* root;
char stop;
public:
BinTree(Node* t=NULL){root=t;}
virtual ~BinTree(){Del(root);};
Node* Father(Node* t,Node* p);//在以t为根的子树中寻找p的父结点
Node* Find(Node* t,const char& item)const;//在以t为根的子树中寻找data域为item的结点
void DelSubTree(Node* t);//从树中删除节点t及其左右子树
void Del(Node* t);//删除节点t及其左右子树
void Preorder(Node* t)const;//先根
void InOrder(Node* t)const;//中根
void PostOrder(Node* t)const;//后根
void LeverOrder(Node* t,Node**& b,int& length);//层次遍历
void CreatBinTree(int tostop);//创建二叉树
Node* Creat();
Node* GetRoot(){return root;}
void SetRoot(Node* t){root=t;}
int GetStop(){return stop;}
void SetStop(char tostop){stop=tostop;}
int IsEmpty(){return root==NULL?1:0;}
bool Comptree(Node* t);
};
//先根创建二叉树
void BinTree::CreatBinTree(int tostop)
{
SetStop(tostop);cout<<"根节点是:";
root=Creat();cout<<endl;
}
Node* BinTree::Creat()
{
Node* t,*t1,*t2;
char item;cin>>item;
if(item==stop){t=NULL;return t;}
else
{
if(!(t=new Node(item,NULL,NULL))) return NULL;
cout<<item<<"左儿子是:";t1=Creat();
t->Setleft(t1);
cout<<item<<"右儿子是:";t2=Creat();
t->Setright(t2);
return t;
}
}
//先根遍历输出二叉树
void BinTree::Preorder(Node* t)const
{
//if(t==NULL) return;
if(t!=NULL)
{
cout<<t->Getdata()<<" ";
Preorder(t->Getleft());
Preorder(t->Getright());
}
}
int main()
{
LinkedList l1;
cout<<"1.InsertFront(item)"<<endl;
cout<<"2.InsertRear(item)"<<endl;
cout<<"3.InsertAt(item)"<<endl;
cout<<"4.DeleteFont()"<<endl;
cout<<"5.DeleteRear()"<<endl;
cout<<"6.DeleteAt()"<<endl;
cout<<"7.Search(int& item)"<<endl;
cout<<"8.Find(int k,int &item)"<<endl;
cout<<"9.FindCur(item)"<<endl;
cout<<"10.Print()"<<endl;
cout<<"请选择操作:";
int c=0;
while(cin>>c){
switch(c)
{
case 1:{
cout<<"请输入要插入的数:";
int a;
cin>>a;
l1.InsertFront(a);
}
break;
case 2:{
cout<<"请输入要插入的数:";
int a;
cin>>a;
l1.InsertRear(a);
}
break;
case 3:{
cout<<"请输入要插入的数:";
int a;
cin>>a;
l1.InsertAt(a);
}
break;
case 4:
{
l1.DeleteFront();
}
break;
case 5:
{
l1.DeleteRear();
}
break;
case 6:
{
l1.DeleteAt();
}
break;
case 7:{
cout<<"请输入要查找的数:";
int a;
cin>>a;
int b=l1.Search(a);
cout<<"要查找的数的位置是:"<<b<<endl;
}
break;
case 8:{
cout<<"请输入要查找位置:";
int a;
cin>>a;
int b;l1.Find(a,b);
cout<<"要查找的数是:"<<b<<endl;
}
break;
case 9:{
int b;l1.FindCur(b);
cout<<"要查找的数的位置是:"<<b<<endl;
}
break;
case 10:
l1.Print();
break;
}
cout<<"请选择操作:";
}
return 0;
}
看着不需要的地方删掉就行 创建二叉树有标注,我的是以'#'结尾的 改下就可以了
/************************************************************************/
/* coder:huifeng00
/* 时间:2010-5-16 下午5点
/* 功能:实现空格为虚节点的二叉树的建立,并且格式化打印二叉树
/************************************************************************/
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
char data;
struct node *left,*right;
}Node,*PNode;
PNode createBtree(PNode root)//创建二叉树,控制台下输入,基于先序遍历输入
{
char data;
scanf("%c",&data);
if (data==' ')
{
root=NULL;
return root;
}
root = (PNode)malloc(sizeof(Node));
root->data = data;
root->left = createBtree(root->left);
root->right = createBtree(root->right);
return root;
}
void printFormat(PNode root)//格式化打印二叉树
{
static i = 0;//这是控制格式化。
int j;
if (root==NULL)
{
return;
}
for (j=0;j<i;j++)
{
printf(" ");
}
printf("%c\n",root->data);
i++;
printFormat(root->left);
printFormat(root->right);
i--;
}
int main()
{
PNode root=NULL;
root = createBtree(root);
printFormat(root);
return 0;
}
程序如上。
虚节点用空格输入的。例如你输入
先序遍历
234空格空格5空格6空格空格7空格空格回车就可以看到结果。
另外你说的输出二叉树图形。
我是这样输出的。第1列是最高节点,就是根。
第2列是第2层节点。
格式话是通过缩进完成的。
这个图形可以参考下面的地址。
http://hi.baidu.com/huifeng00/blog/item/c1e37a4d59310b3caec3ab32.html
我空间曾经写过大量的关于二叉树和多叉树的程序,可以参考下,在数据结构类别下。
这个程序是可以运行的,运行工具是vc6.0.
语言是C.
如还有疑问,可以空间留言,或hi我。
可惜啊,我没好好学,不懂啊
呵呵 这个工程很浩大,我们有个作业和这个差不多,编了好久呢,不过是用C++编的
关于C语言二叉树?
首先二叉树的结点是由做孩子指针*lchild 右孩子指针*rchild 以及数据成员data L表示左孩子R表示右孩子T表示他们的父结点 后序遍历的访问顺序是LRT 中序遍历的访问顺序是LTR 前序遍历的访问顺序是TLR 其中说的前中后就是指访问父结点的次序;拓扑图在这里没法给出啊。。。--- 这是我用C++类写的二...
请问高手:不用指针,怎么用c语言建立二叉树?
你可以创建一个结构体数组,x号节点是父节点,那么它的左孩子就是2x号,右孩子就是2x+1号,你可以自己推演一下,不会重复的,但是这样有一点,就是说当你创建到n层的时候,就必须要申请一个2^n-1个结构体的空间,层数一多,空间严重浪费,所以才要用指针,当然如果你层数不多,比如 5层,那...
C语言统计二叉树叶子结点个数,但是运行不出来是什么原因?
可能的原因有很多,以下是一些常见的原因:1.没有初始化指针:在统计二叉树叶子结点个数时,需要使用指针指向二叉树的根节点。如果没有正确初始化指针,程序将无法访问到正确的内存地址,导致运行错误。2.没有递归遍历二叉树:统计二叉树叶子结点个数需要使用递归的方式遍历整个二叉树。如果程序没有正确地...
二叉链表表示二叉树,复制一颗二叉树,如何用C语言算法设计,希望答案正确...
生成一个二叉树的结点(其数据域为item,左指针域为lptr,右指针域为rptr)BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ){ if (!(T = (BiTNode*)malloc(sizeof(BiTNode))) exit(1); T-> data = item; T-> lchild = lptr; T-> rchild = rptr; return T;}BiTNode *...
C语言先序建立二叉树(如何结束输入)
你的算法没啥大问题,毕竟是教材上的嘛。但咱就是说,你是不是当成单链表来输入了。。。要根据二叉树的结构来啊。输入二叉树不像输入单链表那样输完加上一个终止符' '(空格)就行,而可能需要多个终止符,因为树有多个结尾处。这说得可能比较抽象,下面以你连续输入a,b,c为例。首先根据你的...
c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法_百 ...
include<malloc.h> \/\/ malloc()等 include<stdio.h> \/\/ 标准输入输出头文件,包括EOF(=^Z或F6),NULL等 include<stdlib.h> \/\/ atoi(),exit()include<math.h> \/\/ 数学函数头文件,包括floor(),ceil(),abs()等 define ClearBiTree DestroyBiTree \/\/ 清空二叉树和销毁二叉树的操作一样 ...
C语言,二叉树
是堆排序以后的二叉树?
二叉树先序非递归遍历C语言算法
else {printf("二叉树广义表字符串有错!\\n");exit(1);} } i++; }}void Preorder(struct BTreeNode * BT){ struct BTreeNode * s[10]; int top=-1; struct BTreeNode * p=BT; while(top!=-1||p!=NULL) { while(p!=NULL) { top++; s[top]=p; printf("%c",p->data); p=p->...
C语言 二叉树深度,解释一下
叶子节点就是度为0的结点,比度为2的结点多一个,即度2的没有,这样度为1的结点就是11个,故深度为12(1度就是结点连着1个子树,二叉树最多俩子树,即左右子树)
数据结构C语言 关于二叉树的基本问题
} \/\/ 如果右子树不为空,则递归右子树 if (lpNode->right) { Swap(lpNode->right); }}\/\/ 非递归的算法如下:list<Bitree *> lstNode;if (lpRoot != NULL){ lstNode.push_back(lpRoot); \/\/ 首先将二叉树的根节点放到队列中}while (!lstNode.empty()){ \/...
钊杨特尔: 创建二叉树的源程序如下: #include <cstdlib>#include <stdio.h>typedef struct node{ //树的结点int data;struct node* left;struct node* right;} Node;typedef struct{ //树根Node* root;} Tree;void insert(Tree* tree, int value)//创建树{Node* ...
嘉祥县19583418113: 有关二叉树的简单C语言程序. - ?
钊杨特尔: 先序输入 如 abc##d##e## (#表示空) 输出 cbdae#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#include "cstdlib"#include "malloc.h" typedef int Status; typedef char TElemType;#include #include ...
嘉祥县19583418113: 数据结构中用c语言建立二叉树的程序 - ?
钊杨特尔: #include "stdio.h"#include "stdlib.h"#include "malloc.h"typedef struct Bnode //二叉树节点类型{ int m; stru...
嘉祥县19583418113: 急求二叉树C语言代码 - ?
钊杨特尔: BinaryTree.h: /******************************************************************** created: 2006/07/04 filename: BinaryTree.h author: 李创 purpose: 演示二叉树的算法 *********************************************************************/ #ifndef BinaryTree_H ...
嘉祥县19583418113: 用c语言编程实现二叉树的建立和遍历二叉树? - ?
钊杨特尔: //这是我上数据结构写的 建议理解为主#include#include#define ERROR 0#define OK 1#define OVERFLOW -2#define FLASE 0#define TURE 1 typedef int Status; typedef char TElemType; typedef struct BiTNode{ TElemType data; struct BiTNode ...
嘉祥县19583418113: 用C语言实现二叉树的操作 - ?
钊杨特尔: #include#define STACK_MAX_SIZE 30 #define QUEUE_MAX_SIZE 30 #ifndef elemType typedef char elemType; #endif /************************************************************************/ /* 以下是关于二叉树操作的11个简单算法...
嘉祥县19583418113: 使用c语言写一个二叉树,具体要求如下 - ?
钊杨特尔: #include "stdio.h" #include #include #include typedef char TElemType; //--二叉树的二叉链表存储表示 typedef struct BiTNode { TElemType data; struct BiTNode * lchild, *rchild; } BiTNode, * BiTree; //算法6.4 按先序遍历的顺序建立二叉链表P...
嘉祥县19583418113: 求数据结构(C语言版)建立二叉树的代码~~急~~谢谢了 - ?
钊杨特尔: BT.H文件 #include <stdio.h> #include <malloc.h> #include <conio.h> #define TRUE 1 #define FALSE 0 #define ERROR 0 #define OK 1 #define Stack_Size 50 #define NUM 50 #define MAXSIZE 50 //队列的最大长度 //定义二叉树 typedef char ...
嘉祥县19583418113: 如何用c语言写一个二叉树的代码 - ?
钊杨特尔: 用结构体存储二叉树节点 一个数值成员, 存值 两个指针, 分别指向左右子树 然后 做二叉树相关的函数就好. struct node{int value;struct node *left, *right; };
嘉祥县19583418113: 用c语言写二叉树,源代码. - ?
钊杨特尔: 二叉树是采用递归定义的,实现起来代码简洁(也许并不简单).并且它在具体的计算机科学中有很重要的运用,是一种很重要的数据结构,二叉树有三种遍历和建立的方式.今天先学习一下它的建立和打印.以下代码在Win-Tc1.9.1下编译通...