二叉树-构造体
二叉树--结构体
二叉树--结构体
//========================================// //程序名称:利用结构体建立二叉树 // //Written By HEWEI // //2011 05 30 // //========================================// #include<iostream> using namespace std; #define MAX 20 //定义存储二叉树节点的结构体 struct tree { int left; int Data; int right; }; //自定义结构体类型 //typedef tree treenode; //treenode b_tree[MAX]; tree b_tree[MAX]; //公共数组 int nodelist[MAX]; //--------------------------------------// //---------建立二叉树-------------------// //--------------------------------------// void Create_Tree(int nIndex) { int i; int level; //树的阶层数 int Position;//左树为-1,右树为1 b_tree[1].Data = nodelist[0]; for(i = 1; i< nIndex; i++) { //以i为索引,将nodelist[i]中的数据存入二叉树,并找到它的上一级元素,将此索引存入上一级元素的left or right b_tree[i +1].Data = nodelist[i]; level = 1; Position = 0; while(Position == 0) { //nodelist[i]应该在那个索引 if(nodelist[i] >= b_tree[level].Data) //右树 { //判断是否有子节点 if(b_tree[level].right != -1) //有子节点 level = 2*level +1; else Position = 1; } else //左树 { //判断是否有子节点 if(b_tree[level].left != -1) //有左节点 level = 2* level; else Position = -1; } } if(Position == -1) //左树 b_tree[level].left = i; else b_tree[level].right = i; } } //---------------------------------------// //-------------存储输入元素--------------// //---------------------------------------// void Store_Data(int nIndex) { int temp; int i; for(i=0; i <nIndex;i++) { cout << "Please Input the Data => "; cin >> temp; nodelist[i] = temp; } } int main(void) { int capacity ; //输入数据的容量 //初始化struct为0 for(int i = 0; i < MAX; i++) { b_tree[i].left = -1; b_tree[i].Data = 0; b_tree[i].right = -1; } //存储输入的数据 cout <<"Please Input the capacity : "; cin >> capacity; cout << endl; Store_Data(capacity); //建立二叉树 Create_Tree(capacity); //输出数组和二叉树的元素 cout <<"Output the content Data of NodeList : " << endl; for(int i= 0; i <capacity; i++) { cout << nodelist[i] << " "; } cout << endl; cout <<"Output the content Data of b_tree : " << endl; cout <<"==============================\n"; for(int i = 1; i<= MAX; i++) { cout << (i-1) << ": [" << b_tree[i].left<<"]"; cout <<" [" << b_tree[i].Data <<"]"; cout << " [" << b_tree[i].right <<"]"; cout << endl; } return 0; }