二叉樹的前序遍歷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）。依此類推。