数据结构-二叉树的创建？

数据结构二叉树的建立~

/* 非递归法遍历二叉树
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();
}

---

望江县13549868717： 数据结构二叉树的建立 - ？
褒毕三维： /* 非递归法遍历二叉树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() ...