樹結(jié)構(gòu)練習(xí)——排序二叉樹的中序遍歷

Time Limit:?1000MS?Memory Limit:?65536KB Submit?Statistic?Discuss

Problem Description

在樹結(jié)構(gòu)中，有一種特殊的二叉樹叫做排序二叉樹，直觀的理解就是——(1).每個(gè)節(jié)點(diǎn)中包含有一個(gè)關(guān)鍵值 (2).任意一個(gè)節(jié)點(diǎn)的左子樹（如果存在的話）的關(guān)鍵值小于該節(jié)點(diǎn)的關(guān)鍵值 (3).任意一個(gè)節(jié)點(diǎn)的右子樹（如果存在的話）的關(guān)鍵值大于該節(jié)點(diǎn)的關(guān)鍵值。現(xiàn)給定一組數(shù)據(jù)，請(qǐng)你對(duì)這組數(shù)據(jù)按給定順序建立一棵排序二叉樹，并輸出其中序遍歷的結(jié)果。

Input

輸入包含多組數(shù)據(jù)，每組數(shù)據(jù)格式如下。 第一行包含一個(gè)整數(shù)n，為關(guān)鍵值的個(gè)數(shù)，關(guān)鍵值用整數(shù)表示。(n<=1000) 第二行包含n個(gè)整數(shù)，保證每個(gè)整數(shù)在int范圍之內(nèi)。

Output

為給定的數(shù)據(jù)建立排序二叉樹，并輸出其中序遍歷結(jié)果，每個(gè)輸出占一行。

Example Input

1 2 2 1 20

Example Output

2 1 20

#include<iostream> using namespace std; int tag; typedef struct btree {int data;struct btree *lchild,*rchild; }btree; void createbtree(btree *&T,int key) {if(T==NULL){T=new btree;T->lchild=T->rchild=NULL;T->data=key;return ;}if(key<T->data)createbtree(T->lchild,key);elsecreatebtree(T->rchild,key); } void InOrder(btree *b) {if(b){InOrder(b->lchild);if(!tag){cout<<b->data;tag=1;}elsecout<<' '<<b->data;InOrder(b->rchild);} } int main() {int m,n;btree *T;while(cin>>m){tag=0;T=NULL;for(int i=0;i<m;i++){cin>>n;createbtree(T,n);}InOrder(T);cout<<endl;}return 0; }對(duì)于排序二叉樹的講解：

http://blog.csdn.net/stpeace/article/details/9067029

http://blog.csdn.net/hackbuteer1/article/details/7275396

下面的代碼等我回來(lái)：

#include <iostream> #include <malloc.h> using namespace std; typedef struct btree {int date;btree *lchild,*rchild; }btree; btree *root; btree *createbtree(btree *&root,int a) {btree *b=root;//這時(shí)候就不對(duì)b分配指針空間就不對(duì)if(b==NULL){b=(btree *)malloc(sizeof(btree));b->date=a;b->lchild=b->rchild=NULL;return b;}if(a<b->date)createbtree(b->lchild,a);elsecreatebtree(b->rchild,a); } void inorder(btree *b) {if(b!=NULL){inorder(b->lchild);cout<<b->date;inorder(b->rchild);} } int main() {int n;while(cin>>n){int a;root=(btree*)malloc(sizeof(btree));root=NULL;for(int i=0;i<n;++i){cin>>a;root=createbtree(root,a);}inorder(root);cout<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的sdut 2128 树结构练习——排序二叉树(BST)的中序遍历的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。