第14週実践項目2-ツリー・ソート・ツリーで検索されたパス
3138 ワード
<pre name="code" class="cpp">/*
Copyright (c)2015,
All rights reserved.
: 2.cbp
:
:2015 11 30
:v1.0
: , 。
:
:
*/
:
#include <stdio.h> #include <malloc.h> #define MaxSize 100 typedef int KeyType; // typedef char InfoType; typedef struct node // { KeyType key; // InfoType data; // struct node *lchild,*rchild; // } BSTNode; int path[MaxSize]; // , void DispBST(BSTNode *b); // int InsertBST(BSTNode *&p,KeyType k) // *p BST k { if (p==NULL) // , { p=(BSTNode *)malloc(sizeof(BSTNode)); p->key=k; p->lchild=p->rchild=NULL; return 1; } else if (k==p->key) return 0; else if (k<p->key) return InsertBST(p->lchild,k); // *p else return InsertBST(p->rchild,k); // *p } BSTNode *CreatBST(KeyType A[],int n) // A { BSTNode *bt=NULL; // bt int i=0; while (i<n) InsertBST(bt,A[i++]); // A[i] T return bt; // } // , path , path int SearchBST(BSTNode *bt,KeyType k,KeyType path[],int i) { if (bt==NULL) return i; else if (k==bt->key) // { path[i+1]=bt->key; // return i+1; } else { path[i+1]=bt->key; if (k<bt->key) SearchBST(bt->lchild,k,path,i+1); // else SearchBST(bt->rchild,k,path,i+1); // } } // void SearchResult(BSTNode *bt, int k1) { int r, j; r = SearchBST(bt,k1,path,-1); for (j=0; j<=r; j++) printf("%3d",path[j]); printf("
"); } void DispBST(BSTNode *bt) // bt { if (bt!=NULL) { printf("%d",bt->key); if (bt->lchild!=NULL || bt->rchild!=NULL) { printf("("); DispBST(bt->lchild); if (bt->rchild!=NULL) printf(","); DispBST(bt->rchild); printf(")"); } } } int main() { BSTNode *bt; KeyType k1=65, k2=32; int a[]= {43,91,10,18,82,65,33,59,27,73},n=10; printf(" BST :"); bt=CreatBST(a,n); DispBST(bt); printf("
"); printf(" %d :",k1); SearchResult(bt,k1); printf(" %d :",k2); SearchResult(bt,k2); return 0; }:
<img src="http://img.blog.csdn.net/20151130191011067" alt="" />