关于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).
