根据序列构造二叉排序树_二叉树排序

2024年 8月 2日下午6:36 • 激活谷笔记

编写递归算法，从大到小输出二叉排序树中所有关键字不小于X的数据素，要求算法的时间复杂度为O(log2（m+n）)，其中n为二叉排序树中所含素的个数，m为输出素个数　　1 // IsBigThanX.cpp : 定义控制台应用程序的入口点。 2 // 编写递归算法，从大到小输出给定二叉排序树中所有关键字不小于x的数据素 3 4 #include “stdafx.h” 5 #include<iostream> 6 #include<fstream> 7 using namespace std; 8 9 typedef int KeyType; 10 struct ElemType { KeyType key; }; 11 //定义二叉树结构体 12 typedef struct BiTNode 13 { 14 ElemType data; 15 BiTNode *lchild, *rchild; 16 }*BiTree; 17 BiTree CreateNode(ElemType x)//建立新结点 18 { 19 BiTree p; 20 p = new BiTNode; 21 p->data = x; 22 p->lchild = p->rchild = NULL; 23 return p; 24 } 25 void InsertBST(BiTree &T, ElemType x)//插入结点 26 { 27 if (!T) T = CreateNode(x); 28 else if (x.key<T->data.key) InsertBST(T->lchild, x); 29 else if (x.key>T->data.key) InsertBST(T->rchild, x); 30 } 31 void CreateBST(BiTree &T, char fn[])//创建二叉排序树 32 { 33 ElemType x; ifstream f; 34 f.open(fn); T = NULL; 35 while (!f.eof()) { f >> x.key; InsertBST(T, x); } 36 f.close(); 37 } 38 //visit 函数 39 void visit(ElemType e) 40 { 41 cout << e.key; 42 } 43 //二叉树的输出函数 44 void preorderlist(BiTree T, void visit(ElemType)) 45 { 46 if (T) 47 { 48 visit(T->data); 49 if (T->lchild || T->rchild) 50 { 51 cout << “(“; preorderlist(T->lchild, visit);//输出左孩子 52 cout << “,”; preorderlist(T->rchild, visit);//输出右孩子 53 cout << “)”; 54 } 55 } 56 else cout << “#”; 57 } 58 //从大到小输出二叉排序树中不小于x的素，通过从右子树到左子树的递归实现 59 void PrintBSTLx(BiTree &T, KeyType x) 60 { 61 if (!T) return; 62 PrintBSTLx(T->rchild, x); 63 if (T->data.key<x) return; 64 cout << T->data.key << ” “; 65 PrintBSTLx(T->lchild, x); 66 } 67 //主函数 68 int main() 69 { 70 71 BiTree T; KeyType x; 72 CreateBST(T, “C:\Users\work\Desktop\1.txt”); 73 cout << “所创建的二叉树为：”;//输出创建的二叉排序树 74 preorderlist(T, visit); 75 cout << endl; 76 cout << “请输入数值x: “; 77 cin >> x; 78 PrintBSTLx(T, x); 79 cout << endl; 80 system(“pause”); 81 82 return 0; 83 }

根据序列构造二叉排序树_二叉树排序

相关推荐