二叉树
代码如下:
1 #include <iostream> 2 #include <stdlib.h> 3 #include <vector> 4 using namespace std; 5 6 7 struct BiTreeNode 8 { 9 int data; 10 struct BiTreeNode* left; 11 struct BiTreeNode* right; 12 }; 13 typedef BiTreeNode* Bitree; 14 typedef BiTreeNode* position; 15 int sum_of_Node(Bitree T); 16 void create_Bitree(Bitree &T)//先创建结点,然后创建左树,后右树 17 { 18 int c; 19 cin >> c; 20 if (c == 0) 21 T = NULL; 22 else 23 { 24 T = (Bitree)malloc(sizeof(BiTreeNode)); 25 T->data = c; 26 create_Bitree(T->left); 27 create_Bitree(T->right); 28 } 29 } 30 //先序遍历 31 void pre_order_traverse(Bitree T) 32 { 33 if (T != NULL) 34 { 35 cout << T->data<<" "; 36 pre_order_traverse(T->left); 37 pre_order_traverse(T->right); 38 } 39 } 40 //中序遍历 41 void mid_order_traverse(Bitree T) 42 { 43 if (T != NULL) 44 { 45 mid_order_traverse(T->left); 46 cout << T->data << " "; 47 mid_order_traverse(T->right); 48 } 49 } 50 //后序遍历 51 void post_order_traverse(Bitree T) 52 { 53 if (T != NULL) 54 { 55 post_order_traverse(T->left); 56 post_order_traverse(T->right); 57 cout << T->data << " "; 58 } 59 } 60 //层序遍历 61 void level_traverse(Bitree T) 62 { 63 int n = sum_of_Node(T); 64 if (T == NULL) 65 return; 66 vector<Bitree>p(n); 67 p[0] = T; int i = 1,k=0; 68 while (i < n) 69 { 70 Bitree q = p[k++]; 71 if (q->left != NULL) 72 p[i++] = q->left; 73 if (q->right != NULL) 74 p[i++] = q->right; 75 } 76 for (int j = 0; j < n; j++) 77 cout << p[j]->data << " "; 78 } 79 //二叉树的深度 80 int depth_of_tree(Bitree T) 81 { 82 if (T == NULL) 83 return 0; 84 else 85 { 86 int m = depth_of_tree(T->left) + 1; 87 int n = depth_of_tree(T->right) + 1; 88 if (m > n) 89 return m; 90 else 91 return n; 92 } 93 } 94 //树叶的数目 95 int sum_of_leaf(Bitree T) 96 { 97 if (T == NULL) 98 return 0; 99 if (T->left == NULL && T->right == NULL) 100 return 1; 101 else 102 return sum_of_leaf(T->left) + sum_of_leaf(T->right); 103 } 104 //求结点个数 105 int sum_of_Node(Bitree T) 106 { 107 if (T == NULL) 108 return 0; 109 else 110 return sum_of_Node(T->left) + sum_of_Node(T->right) + 1; 111 } 112 int main() 113 { 114 Bitree T=NULL; 115 create_Bitree(T); 116 pre_order_traverse(T);cout << endl;//先序遍历 117 mid_order_traverse(T);cout<<endl;//中序遍历 118 post_order_traverse(T);cout << endl;//后序遍历 119 level_traverse(T);cout << endl;//层序遍历 120 cout << depth_of_tree(T) << endl; 121 cout << sum_of_leaf(T) << endl; 122 cout << sum_of_Node(T) << endl; 123 system("pause"); 124 return 0; 125 }
输入4 2 0 3 0 0 5 0 6 0 0(ctrl+z+回车)
创建如下的树:
运行结果(第一行为输入的数据):
二叉查找树
代码如下:
1 #include <iostream> 2 #include <stdlib.h> 3 using namespace std; 4 5 struct TreeNode 6 { 7 int data; 8 struct TreeNode* left; 9 struct TreeNode* right; 10 }; 11 typedef struct TreeNode* tree; 12 typedef struct TreeNode* position; 13 14 //查找 15 position find(tree T, int data) 16 { 17 if (T == NULL) 18 return NULL; 19 if (data < T->data) 20 find(T->left, data); 21 else if (data > T->data) 22 find(T->right, data); 23 else 24 return T; 25 } 26 //找最小值——递归实现 27 position find_min(tree T) 28 { 29 if (T == NULL) 30 return NULL; 31 else if (T->left!=NULL) 32 return find_min(T->left); 33 else 34 return T; 35 } 36 //找最大值——递归实现 37 position find_max(tree T) 38 { 39 if (T == NULL) 40 return NULL; 41 else if (T->right != NULL) 42 return find_max(T->right); 43 else 44 return T; 45 } 46 //插入 47 void insert(tree &T, int data) 48 { 49 if (T == NULL) 50 { 51 T = (tree)malloc(sizeof(TreeNode)); 52 T->data = data; 53 T->left = T->right = NULL; 54 } 55 else if (data < T->data) 56 insert(T->left, data); 57 else if (data > T->data) 58 insert(T->right, data); 59 else 60 return; 61 } 62 //创建一个二叉查找树 63 tree create_Bitree(int data[],int n) 64 { 65 tree T = NULL; 66 for (int i = 0; i < n; i++) 67 insert(T, data[i]); 68 return T; 69 } 70 //先序遍历 71 void pre_order_traverse(tree T) 72 { 73 if (T != NULL) 74 { 75 cout << T->data << " "; 76 pre_order_traverse(T->left); 77 pre_order_traverse(T->right); 78 } 79 80 } 81 //中序遍历 82 void mid_order_traverse(tree T) 83 { 84 if (T == NULL) 85 return; 86 mid_order_traverse(T->left); 87 cout << T->data << " "; 88 mid_order_traverse(T->right); 89 } 90 //后序遍历 91 void post_order_traverse(tree T) 92 { 93 if (T == NULL) 94 return; 95 post_order_traverse(T->left); 96 post_order_traverse(T->right); 97 cout << T->data << " "; 98 } 99 //找父结点 100 position find_precursor(tree T, int data) 101 { 102 if (T == NULL) 103 return NULL; 104 if (T->data == data)//第一个根结点没有父结点 105 return NULL; 106 else 107 { 108 while ((data != T->left->data) && (data != T->right->data)) 109 { 110 if (data < T->data) 111 { 112 T = T->left; 113 } 114 else if (data > T->data) 115 { 116 T = T->right; 117 } 118 } 119 return T; 120 } 121 } 122 //删除结点 123 void delete_Node(tree T, int data,position pre)//同时传入要删除数据的父结点pre 124 { 125 position tmpcell=NULL,p; 126 if (T == NULL) 127 return; 128 if (data < T->data) 129 delete_Node(T->left, data,pre); 130 else if(data > T->data) 131 delete_Node(T->right, data,pre); 132 else 133 { 134 if (T->left!=NULL&&T->right!=NULL)//两个儿子 135 { 136 tmpcell = find_min(T->right); 137 T->data = tmpcell->data; 138 p = find_precursor(T->right, T->data); 139 delete_Node(T->right, T->data,p); 140 } 141 else if (T->left == NULL && T->right == NULL)//零个儿子 142 { 143 if (data < pre->data) 144 pre->left = NULL; 145 else if (data > pre->data) 146 pre->right = NULL; 147 free(T); 148 } 149 else//一个儿子 150 { 151 if (T->left == NULL) 152 tmpcell = T->right; 153 else if (T->right == NULL) 154 tmpcell = T->left; 155 free(T); 156 T = NULL; 157 if (data<pre->data) 158 pre->left = tmpcell; 159 else if (data>pre->data) 160 pre->right = tmpcell; 161 } 162 } 163 164 } 165 //使树变为空 166 void make_empty(tree T) 167 { 168 if (T == NULL) 169 return; 170 make_empty(T->left); 171 make_empty(T->right); 172 free(T); 173 } 174 int main() 175 { 176 int data[] = { 5,3,7,6 }; 177 tree T=create_Bitree(data, 4); 178 cout << "先序遍历:"; pre_order_traverse(T); cout << endl;//先序遍历 179 cout << "中序遍历:"; mid_order_traverse(T); cout << endl;//中序遍历 180 cout << "后序遍历:"; post_order_traverse(T); cout << endl;//后序遍历 181 cout << "3的父结点是:"; 182 position p = find_precursor(T, 3); 183 cout << p->data << endl; 184 cout << "最小值:"; 185 cout << find_min(T)->data << endl; 186 cout << "最大值:"; 187 cout << find_max(T)->data << endl; 188 cout << "插入8后的后序排序:"; 189 insert(T, 8); 190 post_order_traverse(T); cout << endl; 191 cout << "删掉5后的先序排序:"; 192 delete_Node(T, 5,find_precursor(T,5)); 193 pre_order_traverse(T); 194 system("pause"); 195 return 0; 196 }
运行结果:
AVL树
代码如下:
1 #include <iostream> 2 #include <stdlib.h> 3 using namespace std; 4 5 struct avlNode 6 { 7 int data; 8 struct avlNode* left; 9 struct avlNode* right; 10 int height; 11 }; 12 typedef struct avlNode* avltree; 13 typedef struct avlNode* position; 14 15 position single_rotate_left(position K2); 16 position single_rotate_right(position K2); 17 position double_rotate_left(position K3); 18 position double_rotate_right(position K3); 19 //查找结点 20 position find(avltree T, int data) 21 { 22 if (T == NULL) 23 return NULL; 24 else if (data < T->data) 25 find(T->left, data); 26 else if (data > T->data) 27 find(T->right, data); 28 else 29 return T; 30 } 31 //找最大值 32 position find_max(avltree T) 33 { 34 if (T == NULL) 35 return NULL; 36 if (T->right != NULL) 37 return find_max(T->right); 38 else 39 return T; 40 } 41 //找最小值 42 position find_min(avltree T) 43 { 44 if (T == NULL) 45 return NULL; 46 if (T->left != NULL) 47 return find_min(T->left); 48 else 49 return T; 50 } 51 //使树为空 52 avltree make_empty(avltree T) 53 { 54 if (T != NULL) 55 { 56 make_empty(T->left); 57 make_empty(T->right); 58 free(T); 59 } 60 return T; 61 } 62 //结点高度 63 int get_height(position p) 64 { 65 int lh, rh; 66 if (p != NULL) 67 { 68 lh = get_height(p->left); 69 rh = get_height(p->right); 70 return ((lh > rh) ? lh : rh) + 1; 71 } 72 else 73 return -1; 74 } 75 //插入结点 76 position insert(avltree &T, int data) 77 { 78 if (T == NULL) 79 { 80 T = (position)malloc(sizeof(avlNode)); 81 T->data = data; 82 T->height = 0; 83 T->left = T->right = NULL; 84 } 85 else if (data < T->data) 86 { 87 T->left=insert(T->left, data); 88 if (get_height(T->left) - get_height(T->right) == 2)//插入结点使高度差为2,需进行旋转 89 if (data < T->left->data) 90 T = single_rotate_left(T);//左-左单旋转 91 else 92 T = double_rotate_left(T);//左-右双旋转 93 } 94 else if (data > T->data) 95 { 96 T->right = insert(T->right, data); 97 if (get_height(T->right) - get_height(T->left) == 2)//插入结点后使高度差为2,需进行旋转 98 if (data > T->right->data) 99 T = single_rotate_right(T);//右-左双旋转 100 else 101 T = double_rotate_right(T);//右-右单旋转 102 } 103 T->height = get_height(T); 104 return T;//返回指向插入结点的指针 105 } 106 //左-左单旋转,更新高度,返回新根 107 position single_rotate_left(position K2) 108 { 109 position K1= K2->left; 110 K2->left = K1->right; 111 K1->right = K2; 112 K2->height = get_height(K2); 113 K1->height = get_height(K1); 114 return K1; 115 } 116 //右-右单旋转, 更新高度,返回新根 117 position single_rotate_right(position K2) 118 { 119 position K1 = K2->right; 120 K2->right = K1->left; 121 K1->left = K2; 122 K2->height = get_height(K2); 123 K1->height = get_height(K1); 124 return K1; 125 } 126 //左-右双旋转,返回新根 127 position double_rotate_left(position K3)//分为两次单旋转,K3->left右单旋,K3左旋 128 { 129 K3->left = single_rotate_right(K3->left); 130 return single_rotate_left(K3); 131 } 132 //右-左双旋转,返回新根 133 position double_rotate_right(position K3) 134 { 135 K3->right = single_rotate_left(K3->right); 136 return single_rotate_right(K3); 137 } 138 139 //创建val树 140 avltree create_valtree(int data[], int n) 141 { 142 avltree T = NULL; position p; 143 for (int i = 0; i < n; i++) 144 { 145 p=insert(T, data[i]); 146 //cout << p->data << " "; 147 } 148 return T; 149 } 150 //先序遍历 151 void pre_order(avltree T) 152 { 153 if (T != NULL) 154 { 155 cout << T->data << " "; 156 pre_order(T->left); 157 pre_order(T->right); 158 } 159 } 160 //中序遍历 161 void mid_order(avltree T) 162 { 163 if (T != NULL) 164 { 165 mid_order(T->left); 166 cout << T->data << " "; 167 mid_order(T->right); 168 } 169 } 170 //后序遍历 171 void post_order(avltree T) 172 { 173 if (T != NULL) 174 { 175 post_order(T->left); 176 post_order(T->right); 177 cout << T->data << " "; 178 } 179 } 180 181 int main() 182 { 183 int data[] = { 3,2,1,4,5,6,7,16,15,14}; 184 avltree T; 185 T = create_valtree(data, 10); 186 position p = find(T, 7); 187 cout<<"查找:";cout << p->data << endl; 188 cout << "最大值:"; p = find_max(T); cout << p->data << endl; 189 cout << "最小值:"; p = find_min(T); cout << p->data << endl; 190 cout << "先序遍历;"; pre_order(T); cout << endl; 191 cout << "中序遍历:"; mid_order(T); cout << endl; 192 cout << "后序遍历:"; post_order(T); cout << endl; 193 system("pause"); 194 return 0; 195 }
运行结果: