数据结构-二叉树的创建?
/* 非递归法遍历二叉树
C语言 */
#include "stdio.h"
#include "stdlib.h"
typedef char Datatype;
typedef struct{
int flag;
PBinTree p;
}
typedef struct BinTNode{
Datatype data;
struct BinTNode *lchild, *rchild;
}BinTree,*PBinTree;
typedef struct stnode{ //栈的结构
Datatype data;//数据域
struct stnode *next;//指针域
}LinkStack;
void InitStack(LinkStack *top){ //初始化栈
top->next=NULL;
}
void Push(LinkStack *top, Datatype x){ //进栈
LinkStack *p;
p=(LinkStack *)malloc(sizeof(LinkStack ));
p->data=x;
p->next=top->next;
top->next=p;
}
int Pop(LinkStack *top,Datatype *e){ //出栈
LinkStack *p;
if(top->next==NULL)
return 0;
else
{
p=top->next;
*e=p->data;
top->next=p->next;
free(p);
return 1;
}
}
int StackEmpty(LinkStack *top){ //判断栈是否为空
if(top->next==NULL)
return 1;
else
return 0;
}
PBinTree CreatBinTNode(){/* 建立二叉树 */
PBinTree T;
Datatype ch;
scanf("%c",&ch);
if(ch=='@'){T=NULL;return T;}
else
{
T=(PBinTree)malloc(sizeof(BinTree) );
T->data=ch;
T->lchild=CreatBinTNode();
T->rchild=CreatBinTNode();
}
return T;
}
void nPreOrder(PBinTree root){ //先序遍历
LinkStack s;
PBinTree p;
InitStack(&s);
if(root==NULL) return;
p=root;
while( p||StackEmpty(s)!=0)
{
while(p)
{
printf("%c",p->data);
Push(s,p->data);
p=p->lchild;
}
}
if(StackEmpty(s)) return ;
else
{
Pop(s,p->data);
p=p->rchild;
}
}
void nInOrder(PBinTree root){ //中序遍历
PBinTree p;
InitStack(&s);
if(root==NULL) return;
p=root;
while(p||StackEmpty(s))
{
while(p)
{
Push(s,p);
p=p->lchild;
}
if(StackEmpty(s)) return;
else {
Pop(s,p->data);
printf("%c ",p->data);
}
printf("
");
}
}
void main()
{
PBinTree T;
T=CreatBinTNode();
printf("二叉树的先序遍历为 :
");
nPreOrder(T);
printf("
");
printf("二叉树的中序遍历为 :
");
nInOrder(T);
printf("
");
printf("二叉树的后序遍历为 :
");
nPostOrder(T);
printf("
");
}
你不是已经画出来了吗,你到底是什么问题?
如果要在内存中建立一个如下左图这样的树,wield能让每个结点确认是否有左右孩子,我们对它进行扩展,变成如下右图的样子,也就是将二叉树中的每个结点的空指针引出一个虚结点,其值为一个特定值,比如”#”,称之为扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一棵二叉树了。如前序遍历序列为AB#D##C##。
有了这样的准备,就可以看看如何生成一棵二叉树了。假设二叉树的结点均为一个字符,把刚才前序遍历序列AB#D##C##用键盘挨个输入,实现的算法如下所示。
二叉树建立实现代码一,如下所示。
//创建树
//按先后次序输入二叉树中结点的值(一个字符),#表示空树
//构造二叉链表表示的二叉树
BiTree CreateTree(BiTree t)
{
char ch;
scanf("%c", &ch);
if(ch == '#')
{
t = NULL;
}
else
{
t = (BitNode *)malloc(sizeof(BitNode));
if(t == NULL)
{
fprintf(stderr, "malloc() error in CreateTree.
");
return;
}
t->data = ch; //生成根结点
t->lchild = CreateTree(t->lchild); //构造左子树
t->rchild = CreateTree(t->rchild); //构造右子树
}
return t;
}
二叉树建立实现代码二,如下所示。
//创建树方法二
int CreateTree2(BiTree *t)
{
char ch;
scanf("%c", &ch);
if(ch == '#')
{
(*t) = NULL;
}
else
{
(*t) = (BiTree)malloc(sizeof(BitNode));
if((*t) == NULL)
{
fprintf(stderr, "malloc() error in CreateTree2.
");
return ERROR;
}
(*t)->data = ch;
CreateTree2(&((*t)->lchild));
CreateTree2(&((*t)->rchild));
}
return OK;
}
其实建立二叉树,也是利用了递归的原理。只不过在原来应该打印结点的地方,改成生成结点、给结点赋值的操作而已。因此,完全可以用中序或后序遍历的方式实现二叉树的建立,只不过代码里生成结点和构造左右子树的代码顺序交互一下即可。
#include <stdio.h>
#define ElemType char
//节点声明,数据域、左孩子指针、右孩子指针
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//先序建立二叉树
BiTree CreateBiTree(){
char ch;
BiTree T;
scanf('%c',&ch);
if(ch=='#')T=NULL;
else{
T = (BiTree)malloc(sizeof(BiTNode));
T->data = ch;
T->lchild = CreateBiTree();
T->rchild = CreateBiTree();
}
return T;//返回根节点
}
//先序遍历二叉树
void PreOrderTraverse(BiTree T){
if(T){
printf('%c',T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
//中序遍历
void InOrderTraverse(BiTree T){
if(T){
PreOrderTraverse(T->lchild);
printf('%c',T->data);
PreOrderTraverse(T->rchild);
}
}
//后序遍历
void PostOrderTraverse(BiTree T){
if(T){
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
printf('%c',T->data);
}
}
void main(){
BiTree T;
T = CreateBiTree();//建立
PreOrderTraverse(T);//输出
getch();
}
用清华大学数据结构书上代码创建二叉树怎么创建
1、要明确的一点是只有中序是无法创建二叉树的,要结合先序,两者相联系才可以。二、根据二叉树的图,得出先序的顺序是ABDECFG,而与此同时的中序DBEAFCG,根据这个建立。三、然后就是要根据二叉树的原则编写代码。
数据结构-树
(10)树的高度(最大层数)(11)森林:多颗子树构成森林 二叉树是一种特殊的树,每个节点最多只能有两个子节点。其子节点分为左节点和右节点。若该二叉树的所有叶子节点都在最后一层,且节点总数为2^n-1,则称为满二叉树;若叶子节点在最后一层或倒数第二层,且最后一层叶子节点连续,倒数第...
数据结构·二叉树问题·
struct BitNode *lchild, *rchild; \/\/左右孩子指针 } BitNode, *BiTree;Status InitBitree(BiTree &T);\/\/初始化一棵二叉树 Status CreateBiTree(BiTree &T);\/\/二叉树的创建(二叉链表)Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType e)) ;\/\/先序遍历 Status InOrderTraverse(B...
数据结构--二叉排序树
二叉排序树,也被称为二叉查找树,是一种特殊的二叉树结构。它具有以下特性:空树或非空树,且满足以下规则:左子树中的所有节点关键字值小于根节点。右子树中的所有节点关键字值大于根节点。左、右子树本身也是二叉排序树。在二叉排序树中进行中序遍历,会得到一个递增的有序序列。查找过程从根节点开始...
【数据结构】课程设计:二叉树的设计与遍历
根据输入的任意数列创建二叉树。(2)遍历。实现二叉树的先序、中序和后序遍历。希望给出的C++程序能够完整无错,如果满意,还有加分。能把程序... 要求:(1)初始化(Initialization)。根据输入的任意数列创建二叉树。(2)遍历。实现二叉树的先序、中序和后序遍历。希望给出的C++程序能够完整无错,如果满意,还有加分。
二叉树是如何实现数据结构的?
我觉得应该是如下的解答:首先画出该树 :如下图左边所示。然后根据树的二叉链表表示法表示存储结构如图右边所示:注意这里的指针域为左边表示第一个孩子*firstchild,右边表示兄弟*nextsibling 紧接着就涉及到了树与二叉树的转换:核心思想:左子树放孩子,右子树放兄弟,则有如图所示的二叉树:
[数据结构]二叉树的分支数为5,度为2的结点2,该数中共有多少个节点_百度...
比如下图中的二叉树就有5个分支。定理1、二叉树的分支数等于二叉树中所有节点的度的总和。比如上图中各个节点的度分别为:A=2,B=2,C=1,D=0,E=0,F=0 2+2+1+0+0+0=5 定理2、在任意一棵二叉树中,度数为0的结点(即叶子结点)总比度为2的结点多一个。题目中说,该二叉树分支数...
树|(2) 二叉树
在操作二叉树时,我们常需要对它进行遍历,以理解其结构和内容。这里有几种常见的遍历方式:先序遍历(DLR):这种顺序是先访问根节点,接着遍历左子树,最后遍历右子树。对应的函数是 void preorder(Btree T)。中序遍历(LDR):遵循的顺序是左子树、根节点、右子树,函数为 void inorder(Btree T)...
二叉树及其拓展可以解决什么问题?
二叉树的拓展应用广泛,例如红黑树(Linux中ext3文件系统管理)和AVL树(Windows对进程地址空间的管理),它们是基于二叉树的优化结构,解决了在实际应用中对性能要求更高的问题。在算法竞赛中,ACM选手熟悉这些高级数据结构,对他们来说,二叉树的深入理解无疑是一大优势。对于非竞赛背景的学习者,算法的...
二叉树的构造过程可以分为哪几个过程?
首先,根据给定的中序遍历序列和后序遍历序列,我们可以推断出这棵二叉树的结构。中序遍历序列是AEHCFBIGD,后序遍历序列是HEFCIGDBA。在后序遍历序列中,最后一个节点A是根节点,它的左子树包含在后序遍历序列的第一个元素H和最后一个元素D之间,右子树包含在后序遍历序列的第二个元素F和倒数第二...
褒毕三维: /* 非递归法遍历二叉树C语言 */ #include "stdio.h" #include "stdlib.h"typedef char Datatype; typedef struct{int flag;PBinTree p; } typedef struct BinTNode{Datatype data;struct BinTNode *lchild, *rchild; }BinTree,*PBinTree;typedef struct ...
望江县13549868717: c语言数据结构:怎么建立一个二叉树? - ?
褒毕三维: 只要将一个二叉树用“括号表示法”表示出来,然后,用链式存储结构将其各个结点存储就可以了,也就是输入一个二叉树.最后,用中序遍历输出! typedef struct node{ ElemType data;struct node *lchild,*rchild;} BTNode; //创建一个二叉树...
望江县13549868717: 数据结构二叉树的创建(c语言版) - ?
褒毕三维: //输入的格式为:abd##e##c###include "stdlib.h"typedef int Element;struct Tree {Element data;struct Tree *left;struct Tree *right; };void CreateBinSortTree(struct Tree **t); void InsertNode2Tree(struct Tree **root, Element num);void ...
望江县13549868717: 二叉树(C语言)怎么创建? - ?
褒毕三维: C语言中二叉树的创建需要用到结构体来定义一个树的数据类型.树这个数据结构有一些数据域,和多个指针域.当然,对于二叉树而言,一般可以定义两个指针域,分别指向root节点的左右子节点.数据结构定义:struct tree{ int data; //这里数据域以此为例 tree*right,*left;}; 真正构建二叉树可以使用动态内存申请,这是一种比较常见的方法(如果不会动态内存申请,可以先看看),但是这样做在子树很多时会耗费较多时间.因此可以事先开辟好一段内存空间用于存储树.比如 tree T[2000];如果需要建立新的子树,那么只需将数组中某个左右子节点赋值即可.如有疑问,欢迎继续追问.
望江县13549868717: 数据结构二叉树的书的创建 - ?
褒毕三维: 用二叉链表存储结构存储二叉树:typedef struct BiTNode{ TElemType data struct BiTree *lchild,*rchild; }BiTNode,*BiTree; 创建:Status CreateBiTree(){ scanf(&ch);//输入节点数据;if(ch=='') T=Null; else{ if(!(T=(BiTNode *)malloc(sizeof(...
望江县13549868717: 数据结构 创建二叉树 - ?
褒毕三维: void GenTree :: ConstructTree ( istream& in, char& value ) {//从输入流对象in接受用广义表表示的非空树,建立广义表的存储表示t. Stack <GenTreeNode* > st (maxSubTreeNum); //用于建表时记忆回退地址 GenTreeNode * p, q, r; Type ch;cin >...
望江县13549868717: 二叉树如何建立 - ?
褒毕三维: 先序递归创建二叉树,并对其进行 先序、中序、后序遍历 #include<malloc.h> // malloc()等 #include<stdio.h> // 标准输入输出头文件,包括EOF(=^Z或F6),NULL等 #include<stdlib.h> // atoi(),exit() #include<math.h> // 数学函数头文件,包括floor()...
望江县13549868717: 请问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* ...
望江县13549868717: 求数据结构(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 ...
望江县13549868717: 怎么样创建二叉树呢? - ?
褒毕三维: 下面给出结构体和建立二叉树的算法,你自己写个主函数加进去就行了,哦!对了,这些问题在一些关于数据结构的书上都有写的 typedef struct BNode //二叉树结点结构体 { ElemType data; struct BNode *lch,*rch; }BNode; BNode *creat_bt0() ...