ChenGen

一切歸零，重新開始

隨筆 - 13, 文章 - 10, 評論 - 21, 引用 - 0

數(shù)據(jù)加載中……

復習二叉排序樹

???二叉排序數(shù)是一種很重要的數(shù)據(jù)結(jié)構(gòu)，今天復習了一下如何創(chuàng)建一棵二叉排序數(shù)＆二叉排序數(shù)的兩種中序遍歷方法——遞歸中序遍歷＆非遞歸的中序遍歷。

???宏定義＆頭文件：

#include? " stdio.h "

#include? " stdlib.h " ? /* 內(nèi)存分配*/

#include? " ctype.h " ? /* 字符操作*/

#define?MAXNUM? 100 ? /* 非遞歸時的棧的大小*/

???數(shù)據(jù)結(jié)構(gòu)：

typedef?struct?node {

???? int ?data;

????struct?node? * left;

????struct?node? * right;

} ?Node;

???生成一棵二叉排序數(shù)：???

Node?*CreateTree()

{

????int?p,data;

????char?buffer[100],ch;

????Node?*head;

????head=NULL;????/*This?is?very?important!*/

????while((ch=getchar())!=EOF){

????????p=0;

????????if(isspace(ch))?/*過濾空格*/

????????????continue;

????????else?if(isdigit(ch)){

????????????buffer[p++]=ch;

????????????for(ch=getchar();isdigit(ch);ch=getchar())

????????????????buffer[p++]=ch;

????????????ungetc(ch,stdin);

????????????buffer[p]='\0';

????????????data=atoi(buffer);?/*將字符串轉(zhuǎn)化為整數(shù)*/

????????}

????????InsertNode(&head,data);/*向樹中插入一個結(jié)點*/

????}

????return?head;

}

void?InsertNode(Node?**head,int?data)

{

????if(*head==NULL){?/*如果結(jié)點為空，正是要插入的位置*/

????????*head=(Node?*)malloc(sizeof(Node));

????????(*head)->data=data;

????????(*head)->left=NULL;

????????(*head)->right=NULL;

????}

????else{

????????if(data<(*head)->data)?InsertNode(&((*head)->left),data);/*插入左子樹*/

????????else?InsertNode(&((*head)->right),data);/*插入右子樹*/

????}

}

???二叉排序數(shù)的遞歸中序遍歷：

void?MidTravel(Node?*head)

{

????if(head){

????????MidTravel(head->left);?/*遍歷左子樹*/

????????printf("%d\t",head->data);?/*輸出結(jié)點值*/

????????MidTravel(head->right);?/*遍歷又子樹*/

????}

}

???二叉排序數(shù)的非遞歸遍歷：

void?MidTravel2(Node?*p)

{

????Node?*a[MAXNUM];?/*棧*/

????int?top;?/*棧頂*/

????top=0;

????while(p?||?top){

????????while(p){

????????????if(top==MAXNUM)?{

????????????????printf("over?flow\n");

????????????????exit(-1);

????????????}

????????????a[top++]=p;?/*入棧*/

????????????p=p->left;?/*遍歷左子樹*/

????????}

????????if(top){

????????????p=a[--top];?/*出棧*/

????????????printf("%d\t",p->data);?/*輸出結(jié)點值*/

????????????p=p->right;?/*遍歷右子樹*/?

????????}

????}

}

posted on 2006-09-27 14:33 ChenGen 閱讀(1668) 評論(2) 編輯收藏所屬分類: 數(shù)據(jù)結(jié)構(gòu)復習

# re: 復習二叉排序樹回復 更多評論

又有沙發(fā)座了

2006-09-27 11:05 | 壞男孩1

# re: 復習二叉排序樹 回復 更多評論

呵呵，支持下！

2006-09-28 08:37 | 冰川

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發(fā)表評論。




網(wǎng)站導航: 博客園 IT新聞 Chat2DB C++博客博問
相關(guān)文章: 楊輝三角復習動態(tài)規(guī)劃算法——01背包問題復習回溯算法——N皇后問題復習二叉排序樹復習排序算法2 復習排序算法

# re: 復習二叉排序樹回復 更多評論

# re: 復習二叉排序樹 回復 更多評論

ChenGen

復習二叉排序樹

評論

導航

常用鏈接

留言簿(5)

隨筆分類

隨筆檔案

文章分類

文章檔案

收藏夾

Good BLogs

搜索

最新評論

閱讀排行榜

評論排行榜

ChenGen

復習二叉排序樹

評論

# re: 復習二叉排序樹 回復 更多評論

# re: 復習二叉排序樹 回復 更多評論

導航

常用鏈接

留言簿(5)

隨筆分類

隨筆檔案

文章分類

文章檔案

收藏夾

Good BLogs

搜索

最新評論

閱讀排行榜

評論排行榜

# re: 復習二叉排序樹回復更多評論

# re: 復習二叉排序樹回復更多評論