二叉树怎么输入,C语言 二叉树建立与指针
二叉树的创建
如输入ABCD#
是不能建立一个完整的二叉树的,
代码中以字符'#'判断是否是空结点,有N个结点就会有N+1个空结点。
从代码中可以看出是先序历遍(根-左-右),进行输入的。
如果想得到二叉树:
A
/ \
B C
/ \
D E
就要输入:ABD##E##C##
就是:
A
/ \
B C
/ \ / \
D E # #
/ \ / \
# # # #
C语言 二叉树建立与指针
2. &和scanf里面的&一样是为了取地址。
1. 传入二级指针是为了修改左右孩子。
createbintree(&(*t)->lchild);和createbintree(&(*t)->rchild)这里如果不用二级指针,那就只能传入左右孩子的值,无法无法修改它们的值。
一般情况下(不用引用的情况下),函数传变量的值的时候就是使用变量的值,也就是变量的一个临时拷贝;而传它的地址的时候一般是为了修改此变量(在函数内可以通过地址找到变量位置,进而修改它)。
想想交换变量值的函数为什么要写成 void switch(int *a,int* b)这种形式,就能够明白了。
3. 第一个问题说这么多,第三个就可以简单地说了。
void initstack(Stack st) 这种写法,是把一个外部的Stack类的变量拷贝给了st,而那个变量的确是没有初始化的,所以编译错误(应该是警告吧)。
而void initstack(Stack *st)这种方式就是传进了那个变量的地址,这样就能在函数内部修改它从而对其初始化了,当然也不会提示错误了。
说这么多,不知说的是否清晰,有什么问题可以继续问
数据结构二叉树的建立
/* 非递归法遍历二叉树
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("\n");
}
}
void main()
{
PBinTree T;
T=CreatBinTNode();
printf("二叉树的先序遍历为 :\n");
nPreOrder(T);
printf("\n");
printf("二叉树的中序遍历为 :\n");
nInOrder(T);
printf("\n");
printf("二叉树的后序遍历为 :\n");
nPostOrder(T);
printf("\n");
}