二叉树的前序遍历c语言,二叉树前序遍历c语言代码

本文目录一览：

• 1、C语言二叉树遍历程序
• 2、二叉树先序非递归遍历C语言算法
• 3、用c语言描述二叉树先序遍历的算法
• 4、C语言二叉树的遍历。
• 5、二叉树先序遍历算法流程图怎么画，学的是数据结构c语言。

C语言二叉树遍历程序

先看下creat这个函数:

status creat(bitnode *t)/*先序建立二叉树*/

{

char ch;

ch=getch();putch(ch);

if(ch==’0′) t=NULL;

else

{

t=(bitnode *)malloc(sizeof(bitnode));

if(!t)

exit(OVERFLOW);

t-data=ch;

creat(t-lchild);

creat(t-rchild);

}

return OK;

}

其中有句代码是t=(bitnode *)malloc(sizeof(bitnode));

这是给t赋值，由于t是参数，这样做是不能返回的。

我知道你的意思是想通过指针返回，但是那样的用法应该是对t所指向的变量赋值，也就是对*t赋值。

如果你还没理解的话看下函数里的递归调用：creat(t-lchild);调用函数后，本意是要给t-lchild赋值的，但是是做不到的，因为要改变一个变量的值的话，应该传的是它的地址。

可能你觉得有点乱了，我举个函数中用指针做参数来返回的例子：

假如要用指针返回一个整型的变量，那么指针应该是指向整型变量的，即int*

这里应该是要返回一个struct bitnode *类型的，也就是返回的值就是个指针，那么参数就应该是一个指向这种指针的指针，即struct bitnode **

可以这么修改：

status creat(bitnode **t) //多了个*

{

char ch;

ch=getch();putch(ch);

if(ch==’0′) *t=NULL; //多了个*

else

{

*t=(bitnode *)malloc(sizeof(bitnode)); //多了个*

if(!*t) //多了个*

exit(OVERFLOW);

(*t)-data=ch;

creat((*t)-lchild); //注意不同

creat((*t)-rchild);

}

return OK;

}

主函数这么改

status main()

{

bitnode* t1; //多了个*

creat(t1);

pre(t1,print); //少了个

getch();

return 0;

}

另外一个编译错误就是

int pre(bitnode *t,status (*visit)())

指针函数后面应该带参数，改为

int pre(bitnode *t,status (*visit)(bitnode *))

二叉树先序非递归遍历C语言算法

#include “stdio.h”

#include “stdlib.h”

#define STACK_INIT_SIZE 10 //栈的初始长度

#define STACKINCREMENT 5 //栈的追加长度

typedef struct bitree{

char data;

struct bitree *lchild,*rchild;

}bitree; //二叉树结点定义

typedef struct {

bitree **base;

bitree **top;

int stacksize;

}sqstack; // 链栈结点定义top栈顶 base栈底 且栈元素是指向二叉树结点的二级指针

//建立一个空栈

int initstack(sqstack *s)

{s-base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree)); //栈底指向开辟空间

if(!s-base) exit(1); //抛出异常

s-top=s-base; //栈顶=栈尾 表示栈空

s-stacksize=STACK_INIT_SIZE; //栈长度为开辟空间大小

return 1;

}

//进栈

int push(sqstack *s,bitree *e)

{if(s-top-s-base=s-stacksize) //如果栈满 追加开辟空间

{s-base=(bitree *)realloc (s-base,(s-stacksize+STACKINCREMENT)* sizeof(bitree));

if(!s-base) exit(1); //抛出异常

s-top=s-base+s-stacksize; //感觉这一句没用

s-stacksize+=STACKINCREMENT;}

*(s-top)=e;s-top++; //进栈 栈顶后移

return 1;

}

//出栈

int pop(sqstack *s,bitree **e)

{if(s-top==s-base) return 0; //栈空 返回0

–s-top;*e=*(s-top); //栈顶前移 取出栈顶元素给e

return 1;}

//取栈顶

int gettop(sqstack *s,bitree **e) //去栈顶元素 注意top指向的是栈顶的后一个

{if(s-top==s-base) return 0; //所以 s-top-1

*e=*(s-top-1);

return 1;

}

/*————————非递归—–先序建立二叉树———————————-*/

bitree *createprebitree()

{char ch;bitree *ht,*p,*q;

sqstack *s;

s=malloc(sizeof(bitree)); //加上这一句为s 初始化开辟空间

ch=getchar();

if(ch!=’#’ch!=’\n’) /* 输入二叉树先序顺序 是以完全二叉树的先序顺序

不是完全二叉树的把没有的结点以#表示 */

{ht=(bitree *)malloc(sizeof(bitree));

ht-data=ch;

ht-lchild=ht-rchild=NULL;

p=ht;

initstack(s);

push(s,ht); //根节点进栈

while((ch=getchar())!=’\n’) // 算

{if(ch!=’#’) {q=(bitree *)malloc(sizeof(bitree)); // 法

q-data=ch; //

if(p==*(s-top-1)) p-lchild=q; // 核

else p-rchild=q; //

push(s,q);p=q; // 心

} //

else {if(p==*(s-top-1)) p-lchild=NULL; // 的

else p-rchild=NULL; //

pop(s,p);} // 步

//

} // 骤

return ht;

}

else return NULL;

}

/*————————–递归———先序建立二叉树——————————-*/

void CreateBiTree(bitree **T) {

//按先序次序输入二叉树中的结点的值（一个字符），空格字符表示空树，

//构造二叉链表表示二叉树

char ch;

scanf(“%c”,ch);

if(ch==’#’) *T=NULL;

else{

*T=(bitree * )malloc(sizeof(bitree));

if(!*T) exit(1);

(*T)-data=ch; //生成根结点

CreateBiTree((*T)-lchild); //构造左子树

CreateBiTree((*T)-rchild); //构造右子树

}

}

/*————————–非递归——-中序建立二叉树——————————-*/

/*————————–递归———中序建立二叉树——————————-*/

/*————————–非递归——-后序建立二叉树——————————-*/

/*————————–递归———后序建立二叉树——————————-*/

/*———————–非递归——先序输出二叉树——————————*/

void preordertraverse(bitree *h)

{sqstack m;

initstack(m);

while(h||m.base!=m.top)

{if(h) {push(m,h);printf(“%c”,h-data);h=h-lchild;}

else{pop(m,h);

h=h-rchild;}

}

}

/*————————非递归—–中序输出二叉树—————————-*/

void inordertraverse(bitree *h)

{sqstack m;

initstack(m);

while(h||m.base!=m.top)

{if(h) {push(m,h);h=h-lchild;}

else {

pop(m,h);

printf(“%c”,h-data);

h=h-rchild;

}

}

}

/*———————非递归—-后序遍历二叉树———————————-*/

void postordertraverse(bitree *h)

{

sqstack m;

initstack(m);

while(h||m.base!=m.top)

{if(h) {

push(m,h);

h=h-lchild;}

else {

bitree *r; //使用r结点表示访问了右子树 代替标志域

gettop(m,h);

if(h-rchildh-rchild!=r)

{h=h-rchild;

push(m,h);

h=h-lchild;}

else{pop(m,h);

printf(“%c”,h-data);

r=h;h=NULL;}

}

}

}

//层次遍历二叉树 用队列 哈哈以后做

/*——————————-主过程——————————-*/

int main()

{bitree *ht;

printf(“先序非递归建立一个二叉树:”);

if((ht=createprebitree())!=NULL) //非递归建立

//CreateBiTree(ht);

//if(ht!=NULL) //递归建立

{

printf(“先序遍历输出二叉树:”);

preordertraverse(ht);

putchar(‘\n’);

printf(“中序遍历输出二叉树:”);

inordertraverse(ht);

putchar(‘\n’);

printf(“后序遍历输出二叉树:”);

postordertraverse(ht);

putchar(‘\n’);

}

else printf(“空二叉树\n”);

}

用c语言描述二叉树先序遍历的算法

参考：

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

 

/* Helper function that allocates a new node with the given data and

   NULL left and right  pointers.*/

struct node* newNode(int data)

{

    struct node* node = new struct node;

    node-data = data;

    node-left = NULL;

    node-right = NULL;

    return(node);

}

void iterativePreorder(node *root)

{

    // Base Case

    if (root == NULL)

       return;

 

    // Create an empty stack and push root to it

    stacknode * nodeStack;

    nodeStack.push(root);

 

    /* Pop all items one by one. Do following for every popped item

       a) print it

       b) push its right child

       c) push its left child

    Note that right child is pushed first so that left is processed first */

    while (nodeStack.empty() == false)

    {

        // Pop the top item from stack and print it

        struct node *node = nodeStack.top();

        printf (“%d “, node-data);

        nodeStack.pop();

 

        // Push right and left children of the popped node to stack

        if (node-right)

            nodeStack.push(node-right);

        if (node-left)

            nodeStack.push(node-left);

    }

}

C语言二叉树的遍历。

二叉树的前中后遍历（递归与非递归）

#includestdio.h

#includestdlib.h

typedef struct NODE

{

char value;

struct NODE *LChild;

struct NODE *RChild;

}BiTNode,*BiTree; //二叉树数据结构

BiTree root;

typedef struct node

{

BiTNode *pointer;

struct node *link;

}LinkStackNode,*LinkStack; //链栈数据结构

LinkStack S;

int count = 0;

//BiTNode * InitTree(BiTree Tree);

BiTNode *CreateTree(BiTree Tree); //创建二叉树

void PreOrder(BiTree Tree); //递归前序遍历二叉树

void MidOrder(BiTree Tree); //递归中序遍历二叉树

void PostOrder(BiTree Tree); //递归后序遍历二叉树

void NPreOrder(BiTree Tree); //非递归前序遍历二叉树

void NMidOrder(BiTree Tree); //非递归中序遍历二叉树

void NPostOrder(BiTree Tree); //非递归后序遍历二叉树

//—————————————————

LinkStackNode *InitLinkStack(LinkStack top); //初始化链栈

void Push(LinkStack top,BiTNode *p); //进栈操作

BiTNode * Pop(LinkStack top); //出栈操作

//int IsEmpty(LinkStack S); //判断栈是否为空

void main()

{

//BiTree tree;

//root = InitTree(tree);

root = CreateTree(root);

PreOrder(root);

printf(“\n”);

MidOrder(root);

printf(“\n”);

PostOrder(root);

printf(“\n”);

NPreOrder(root);

printf(“\n”);

NMidOrder(root);

printf(“\n”);

NPostOrder(root);

printf(“\n”);

}

/*BiTNode * InitTree(BiTree Tree)

{

//BiTNode *root;

//root = Tree;

Tree = (BiTNode *)malloc(sizeof(BiTNode));

Tree = NULL;

//Tree-LChild = NULL;

//Tree-RChild = NULL;

return Tree;

}*/

//二叉树的扩展先序遍历的创建

BiTNode * CreateTree(BiTree Tree)

{

char ch;

ch = getchar();

if(ch == ‘.’)

Tree = NULL;

else

{

Tree = (BiTNode *)malloc(sizeof(BiTNode));

if(Tree)

{

Tree-value = ch;

Tree-LChild = CreateTree(Tree-LChild);

Tree-RChild = CreateTree(Tree-RChild);

}

}

return Tree;

}

//递归前序遍历二叉树

void PreOrder(BiTree Tree)

{

if(Tree)

{

printf(“%c”,Tree-value);

PreOrder(Tree-LChild);

PreOrder(Tree-RChild);

}

}

//递归中序遍历二叉树

void MidOrder(BiTree Tree)

{

if(Tree)

{

MidOrder(Tree-LChild);

printf(“%c”,Tree-value);

MidOrder(Tree-RChild);

}

}

//递归后序遍历二叉树

void PostOrder(BiTree Tree)

{

if(Tree)

{

PostOrder(Tree-LChild);

PostOrder(Tree-RChild);

printf(“%c”,Tree-value);

}

}

//非递归前序遍历二叉树

void NPreOrder(BiTree Tree)

{

BiTNode *p;

S = InitLinkStack(S);

p = Tree;

while(p || count != 0)

{

if(p)

{

if(p-RChild)

Push(S,p-RChild);

printf(“%c”,p-value);

p = p-LChild;

}

else

p = Pop(S);

}

}

//非递归中序遍历二叉树

void NMidOrder(BiTree Tree)

{

//char ch;

BiTNode *p;

S = InitLinkStack(S);

p = Tree;

while(p || count != 0)

{

if(p)

{

Push(S,p);

p = p-LChild;

}

else

{

p = Pop(S);

printf(“%c”,p-value);

p = p-RChild;

}

}

}

//非递归后序遍历二叉树

void NPostOrder(BiTree Tree)

{

BiTNode *p,*q = NULL;

S = InitLinkStack(S);

p = Tree;

while(p || count != 0)

{

if(p)

{

Push(S,p);

p = p-LChild;

}

else

{

p = S-link-pointer;

if(p-RChild == NULL || p-RChild == q)

{

p = Pop(S);

printf(“%c”,p-value);

q = p;

p = NULL;

}

else

{

//p = Pop(S);

p = p-RChild;

}

}

}

}

//初始化链栈

LinkStackNode *InitLinkStack(LinkStack top)

{

top = (LinkStackNode *)malloc(sizeof(LinkStackNode));

return top;

}

//进栈操作

void Push(LinkStack top,BiTNode *p)

{

LinkStackNode *temp;

temp = (LinkStackNode *)malloc(sizeof(LinkStackNode));

if(temp)

{

temp-pointer = p;

temp-link = top-link;

top-link = temp;

count++;

}

}

//出栈操作

BiTNode * Pop(LinkStack top)

{

//char ch;

BiTNode *p;

LinkStackNode *temp;

p = (BiTNode *)malloc(sizeof(BiTNode));

temp = top-link;

if(temp)

{

top-link = temp-link;

p = temp-pointer;

free(temp);

count–;

}

return p;

}

二叉树先序遍历算法流程图怎么画，学的是数据结构c语言。

在计算机软件专业中，数据结构、以及 C 语言这两门课程是非常重要的两门课程。最为重要的是：如果将来想做计算机软件开发工作的话，那么对 C 语言中的指针编程、以及递归的概念是必须要熟练精通掌握的，因为它和数据结构课程中的链表、二叉树等内容的关系实在是太紧密了。但是这个编程技能必须要依靠自己多上机实践才能够真正彻底掌握的。

首先要搞明白二叉树的几种遍历方法：（1）、先序遍历法：根左右；（2）、中序遍历法：左根右；（3）、后序遍历法：左右根。其中根：表示根节点；左：表示左子树；右：表示右子树。

至于谈到如何画先序遍历的流程图，可以这样考虑：按照递归的算法进行遍历一棵二叉树。

程序首先访问根节点，如果根节点的值为空（NULL），则停止访问；如果根节点的值非空，则递归访问二叉树的左子树（left），然后是依然判断二叉树下面的左子树下面的根节点是否为空（NULL），如果根节点的值为空（NULL），则返回上一层，再访问二叉树的右子树（right）。依此类推。