关于C语言二叉树?
完全二叉树除了第一层和最后一层外,其余各层的结点数都是2的幂,所以都是偶数,因此,当最后一层的结点数为偶数时,树的总结点数才可能是奇数.
而完全二叉树只有最后一层的结点数为奇数时,树中才可能存在唯一的度为1的结点,即最后一个结点的父结点.但现在最后一层结点数为偶数,所以树中不存在度为1的结点,即n1=0.
所以n=n0+n2=2n0-1=699,n0=350
dev c++
#include
#include
#include
#include
typedef struct node
{
int data;//节点信息
struct node *lchild;//左孩子
struct node *rchild;//右孩子
}BTnode;
void Init(BTnode *&b)//初始化
{b=NULL;}
int Insert(BTnode *&b,int m)//插入操作
{
BTnode *p;
if(b==NULL)
{b=(BTnode*)malloc(sizeof(BTnode));
b->data=m;
b->lchild=b->rchild=NULL;
}
else
{if(mdata)
{
if(b->lchild!=NULL&&m>b->lchild->data)
{p=(BTnode*)malloc(sizeof(BTnode));
p->data=m;
p->rchild=NULL;
p->lchild=b->lchild;
b->lchild=p;
}
else return Insert(b->lchild,m);
}
else if(m>b->data)
{if(b->rchild!=NULL&&mrchild->data)
{p=(BTnode*)malloc(sizeof(BTnode));
p->data=m;
p->lchild=NULL;
p->rchild=b->rchild;
b->rchild=p;
}
else return Insert(b->rchild,m);
}
else printf("插入重复节点,插入覆盖!");
}
}
static char s[1024][1024],a[1024];
static int n;
int output(BTnode *&b,int i)//层次输出
{
if(n<i)n=i;
BTnode *p=b;
if(p!=NULL)
{
itoa(p->data,a,10);
strcpy(s[i],a);
output(p->lchild,2*i+1);
output(p->rchild,2*(i+1));
}
else strcpy(s[i],"N");
}
void xianxu(BTnode*&b)//先序
{
BTnode *p=b;
if(p!=NULL)
{
printf("%d ",p->data);
xianxu(p->lchild);
xianxu(p->rchild);
}
}
void zhongxu(BTnode *&b)//中序
{
BTnode *p=b;
if(p!=NULL)
{
zhongxu(p->lchild);
printf("%d ",p->data);
zhongxu(p->rchild);
}
}
void houxu(BTnode *&b)//后序
{
BTnode *p=b;
if(p!=NULL)
{
houxu(p->lchild);
houxu(p->rchild);
printf("%d ",p->data);
}
}
void menu()
{
BTnode *b;
Init(b);
int i,j,k,y,m;
while(1)
{
printf("*****************************************
");
printf("*************二叉数功能菜单**************
");
printf("*************1.插入整数 ************
");
printf("*************2.层次输出二叉树************
");
printf("*************3.先序遍历 ************
");
printf("*************4.中序遍历 ************
");
printf("*************5.后序遍历 ************
");
printf("*************6.退出 ************
");
printf("*****************************************
");
printf("请选择:");
scanf("%d",&y);
switch(y)
{
case 1:printf("
请输入整数:");scanf("%d",&m);Insert(b,m);break;
case 2:i=0;output(b,i);printf("N代表空节点
");
for(int j=0;j<=n;j++)
{
printf("%s ",s[j]);
for(k=1;(int)pow(2,k)-2<j;k++);
if((int)pow(2,k)-2==j)printf("
");
}
break;
case 3:xianxu(b);break;
case 4:zhongxu(b);break;
case 5:houxu(b);break;
case 6:exit(0);break;
default:printf("
输入错误!");break;
}
printf("
");
}
}
int main()
{
menu();
system("pause");
}
L表示左孩子R表示右孩子T表示他们的父结点
后序遍历的访问顺序是LRT
中序遍历的访问顺序是LTR
前序遍历的访问顺序是TLR
其中说的前中后就是指访问父结点的次序;
拓扑图在这里没法给出啊。。。
--------------------------------------------
这是我用C++类写的二叉树的头文件,里面有几个函数你可能用不到,你主要看看那几个遍历函数
#include<iostream>
using namespace std;
typedef char elemType;
struct bnode
{
bnode *lchild,*rchild;
elemType data;
};
class BinaryTree
{
public:
BinaryTree();
void create(bnode* &tempR);
void visite(bnode *T);
void preorder(bnode *T);
void inorder(bnode *T);
void postorder(bnode *T);
int high(bnode *T);
void convert(bnode* &tempR,string &a,int i);
void copy(bnode *T,bnode *&T1);
void level(bnode *T,int i);
void swap(bnode *T);
bnode *root;
private:
int count;
};
BinaryTree::BinaryTree()
{
root = NULL;
count = 0;
}
void BinaryTree::create(bnode* &tempR)
{
elemType x;
cin>>x;
if(x == '.')
{
tempR = NULL;
}
else
{
tempR = new bnode;
count++;
tempR->data = x;
create(tempR->lchild);
create(tempR->rchild);
}
}
void BinaryTree::visite(bnode *T)
{
if(T!=NULL)
cout<<T->data<<' ';
}
void BinaryTree::preorder(bnode *T)
{
if(T!=NULL)
{
visite(T);
preorder(T->lchild);
preorder(T->rchild);
}
}
void BinaryTree::inorder(bnode *T)
{
if(T!=NULL)
{
inorder(T->lchild);
visite(T);
inorder(T->rchild);
}
}
void BinaryTree::postorder(bnode *T)
{
if(T!=NULL)
{
postorder(T->lchild);
postorder(T->rchild);
visite(T);
}
}
int BinaryTree::high(bnode *T)
{
if(T==NULL)
return 0;
else if(high(T->lchild)>high(T->rchild))
return high(T->lchild)+1;
else
return high(T->rchild)+1;
}
void BinaryTree::level(bnode *T,int i)
{
if(T!=NULL)
{
level(T->lchild,i+1);
visite(T);
cout<<i<<' ';
level(T->rchild,i+1);
}
}
void BinaryTree::convert(bnode *&T,string &a,int i)
{
elemType x;
if(i<=a.length())
{
x = a[i-1];
T = new bnode;
count++;
T->data = x;
convert(T->lchild,a,2*i);
convert(T->rchild,a,2*i+1);
}
else
{
T=NULL;
}
}
void BinaryTree::copy(bnode *T,bnode *&T1)
{
elemType x;
if(T!=NULL)
{
x=T->data;
if(x == '.')
{
T1 = NULL;
}
else
{
T1 = new bnode;
T1->data = x;
T1->lchild = NULL;
T1->rchild = NULL;
copy(T->lchild,T1->lchild);
copy(T->rchild,T1->rchild);
}
}
}
void BinaryTree::swap(bnode *T)
{
if(T!=NULL)
{
bnode *temp;
temp=T->lchild;
T->lchild=T->rchild;
T->rchild=temp;
swap(T->lchild);
swap(T->rchild);
}
}
#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语言二叉树中“度”为0,1,2各是什么意思啊?
只有一个根,没有孩子的二叉树度为0,所有节点只有一个孩子的二叉树的度为1,节点中有两个孩子的二叉树的度为2。树所包含的节点中,拥有最大的分支的数目为该树的度。二叉树的度小于等于2,因为二叉树的定义要求二叉树中任意结点的度数(结点的分支数)小于等于2 ,并且两个子树有左右之分,顺序...
请问高手:不用指针,怎么用c语言建立二叉树?
你可以创建一个结构体数组,x号节点是父节点,那么它的左孩子就是2x号,右孩子就是2x+1号,你可以自己推演一下,不会重复的,但是这样有一点,就是说当你创建到n层的时候,就必须要申请一个2^n-1个结构体的空间,层数一多,空间严重浪费,所以才要用指针,当然如果你层数不多,比如 5层,那...
请问C语言如何创建二叉树???
创建二叉树的源程序如下: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* node=(Node*)malloc(sizeof(...
c语言二叉树选择菜单怎么制作
c语言二叉树选择菜单怎么制作?选择一个菜单项,选择文件,按alt键复制或选择菜单单位,在菜单的中心点打开,选择菜单命令,输入0数字等等,单击下方的复制按钮,选择选中后位置默认,单击ok即可使用,如下图。将复制好的选择按钮右击,选择选择命令,打开回到文件,在弹出的界面,找到复制内容的选择框(点击...
C语言二叉树
我试着来解答一下。这是一个递归函数。首先要理解T、L、R的含义。假如L[i]=x1,R[i]=x2,那么节点i的左右孩子分别就是x1,x2.那么T[x1]=i,T[x2]=i,就是指x1,x2的双亲节点就是i。Status Dencend(Array1D L, Array1D R, int n, int u, int v, Array1D T)\/***\/ { int i...
在二级c语言考试题中看到好几道树,二叉树之类的题,在教材里没有任何一...
树与二叉树 树是一种非线性结构,在这种结构中,所有数据元素之间的关系具有明显的层次特性。而二叉树也是一种非线性结构,它与树结构相似,并且树结构的所有术语都可以用到二叉树这种数据结构上。二叉树具有以下两个特点:① 非空二叉树只有一个根结点。② 每一个结点最多有两棵子树,且分别称为该...
c语言如何实现一棵二叉树的遍历
今天我也遇到这道题了,经过我的研究,我觉得应该是如下的解答:首先画出该树 :如下图左边所示。然后根据树的二叉链表表示法表示存储结构如图右边所示:注意这里的指针域为左边表示第一个孩子*firstchild,右边表示兄弟*nextsibling 紧接着就涉及到了树与二叉树的转换:核心思想:左子树放孩子,右子树放...
使用c语言写一个二叉树,具体要求如下
语句较多,但比较简单,所以不一一介绍了,难理解的i主要编程思想,你可以输入abc**e*hj***cf**g** 然后回车 试试 看看结果。
c语言,二叉树求解~
先考虑度为2的结点,第一层1个,第二层2个,第三层4个,第四层8个,第五层8个,共23个。然后第5层还有8个空位,先假设为叶子节点,即度为0。第五层满,目前总共31个结点。然后第五层的8个度为2的结点可以引申出16个叶子结点,总共47个,以满足题意,假设成立。故6层。当然比较简单的题...
C语言二叉树的深度指什么?怎么求?
3.比较左右子树深度值,返回较大的那一个 4.通过递归调用 include<iostream>#include<stdlib.h>using namespace std;struct BinaryTreeNode{ int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight;};\/\/创建二叉树结点BinaryTreeNode* CreateBinaryTreeNode(int value){ B...
圭路羚羊: 在计算机科学中,二叉树是每个结点最多有两个子树的有序树.通常子树的根被称作“左子树”(left subtree)和“右子树”(right subtree).二叉树常被用作二叉查找树和二叉堆或是二叉排序树. 二叉树的每个结点至多只有二棵子树(不存在度大...
肃宁县13961159868: 二叉树(C语言)怎么创建? - ?
圭路羚羊: C语言中二叉树的创建需要用到结构体来定义一个树的数据类型.树这个数据结构有一些数据域,和多个指针域.当然,对于二叉树而言,一般可以定义两个指针域,分别指向root节点的左右子节点.数据结构定义:struct tree{ int data; //这里数据域以此为例 tree*right,*left;}; 真正构建二叉树可以使用动态内存申请,这是一种比较常见的方法(如果不会动态内存申请,可以先看看),但是这样做在子树很多时会耗费较多时间.因此可以事先开辟好一段内存空间用于存储树.比如 tree T[2000];如果需要建立新的子树,那么只需将数组中某个左右子节点赋值即可.如有疑问,欢迎继续追问.
肃宁县13961159868: 请问C语言如何创建二叉树???? - ?
圭路羚羊: 创建二叉树的源程序如下: #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* ...
肃宁县13961159868: C语言建立二叉树 - ?
圭路羚羊: 根据二叉树的父节点和子节点的关系来创建 比如,父节点的编号是1,那么左子节点的编号就是2,右子节点的编号就是3 关系父节点编号为i,则左子节点编号为2*i,右子节点编号为2*i+1 然后按照从小到大的顺序赋值就行了 比如操作 先i=1;...
肃宁县13961159868: c语言数据结构:怎么建立一个二叉树? - ?
圭路羚羊: 只要将一个二叉树用“括号表示法”表示出来,然后,用链式存储结构将其各个结点存储就可以了,也就是输入一个二叉树.最后,用中序遍历输出! typedef struct node{ ElemType data;struct node *lchild,*rchild;} BTNode; //创建一个二叉树...
肃宁县13961159868: C语言,二叉树的问题 - ?
圭路羚羊: 1.219 二叉树的几点只有 0 1 2 三种度数2度节点 数等于0度节点(即叶子节点)减1n=n0+n1+n2=70+80+69=219 2.250 满二叉树下 节点数(n)与深度(m)的关系是 n=1+2+4+……+2^(m-1)=(2^m)-1因为完全二叉树 的节点数n 2^(m-1)-1<n<=2^m-1 所以 m=9 深度为9 满二叉树的叶子是 256 节点一共是511 完全二叉树节点少了11 256-11 =245 因为两个叶子 有一个父亲 11/2 =5 本来的父亲没了孩子 成为叶子 245+5=250
肃宁县13961159868: 求代码——二叉树——要C语言的 - ?
圭路羚羊: #include <stdio.h>#include <stdlib.h>#define STACK_MAX_SIZE 30#define QUEUE_MAX_SIZE 30#ifndef elemType typedef char elemType;#endif/************************************************************************//* 以下是关于二叉树操作的11个简...
肃宁县13961159868: 急急急:关于二叉树的算法 遍历 左右子树交换 用类C语言 要详细代码 - ?
圭路羚羊: (1)编写建立二叉树的算法. (2)验证二叉树的先序、中序、后序遍历算法 (3)编写二叉树的左右子树交换算法 上面这些都比较简单,程序如下:#include <stdio.h> #include <malloc.h>typedef struct tree {char data;struct tree *l;/*左儿子*/...
肃宁县13961159868: 求数据结构(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 ...
肃宁县13961159868: 在C语言中,什么是二叉树啊??
圭路羚羊: 叉树是每个结点最多有两个子树的有序树.通常子树的根被称作“左子树”(left subtree)和“右子树”(right subtree).