1 #include <stdio.h> 2 #include<stdlib.h> 3 #include <conio.h> 4 #define ARRAYLEN 11 5 int source [] = {55,94,6,65,11,38,40,39,91,67,66}; 6 typedef struct bst { 7 int data; 8 struct bst *left; 9 struct bst *right; 10 }ercha; 11 12 /* 13 将单个节点插入到二叉树的相应位置 14 */ 15 void Inserter (ercha *t ,int key){ 16 ercha *p, *parent, *head; 17 if(!(p=(ercha *)malloc(sizeof(ercha)))){ //申请一个新节点 18 printf("申请的内存出错！"); 19 exit(0); 20 } 21 p->data=key; 22 p->left=p->right=NULL; 23 head = t; 24 while(head){ 25 parent=head; 26 if(key<head->data) //如果插入值小于当前节点值，则向左遍历 ，否则，向右遍历 27 head=head->left; 28 else 29 head =head->right; 30 } 31 if(key<parent->data) //找到key值的合适位置后，与其父节点比较，插入适当的位置 32 parent->left=p; 33 else 34 parent->right=p; 35 } 36 37 /* 38 构造二叉树 39 */ 40 void Createer(ercha *t,int data[],int n){ 41 int i; 42 t->data = data[0]; 43 t->left=t->right=NULL; 44 for(i=1;i<n;i++){ 45 Inserter(t,data[i]); 46 } 47 } 48 49 /* 50 中序遍历二叉树 51 */ 52 void BST_LDR(ercha *t){ 53 if(t){ 54 BST_LDR(t->left); 55 printf("%d ",t->data); 56 BST_LDR(t->right); 57 } 58 return ; 59 } 60 61 /* 62 删除二叉树中的节点，分三种大情况： 63 64 1、 被删除节点没有孩子节点 即删除节点为叶子节点，则直接删除（本文算法加入了一个父节点，有点不一样） 65 66 2、被删除节点只有左子树，或只有右子树，则可以直接将被删的节点的左子树或右子树直接改写为双亲节点的左子树或者右子树 67 68 （1） 被删节点是父节点的左孩子 ，如果被删节点有左子树或者右子树， 则被删节点的左子树，或者右子树作为父节点的左子树 ； 69 70 （2） 被删节点是符节点的右孩子， 如果被删节点有左子树或者右子树， 则被删节点的左子树，或者右子树作为父节点的左子树 ； 71 72 3、被删除节点既有左子树，也有右子树时有两种方法： 73 74 （1） 首先找到被删节点左子树上最右下角的节点 S（中序序列中被删节点的直接前驱），然后将被删节点的左子树改为其父节点的左子树 75 被删节点的右子树改为 S 的右子树。或者首先找到被删除节点在左子树上最右下角的节点S，然后用S的值代替被删除节点的值，
原S节点的左子树改为S的双亲节点的右子树。 76
77 （2） 从删除节点的右子树开始，在删除节点的右子树上找到最左下角 的节点（即中序序列中被删节点的直接后继节点，然后将最左下角 78 的值取代被删节点，最左下角节点的右子树作为最左下角节点父节点的左子树。 79 80 */ 81 82 void Deleteer(ercha *t,int key){ 83 ercha *p, *parent , *l,*l1; 84 bool flag =false; 85 int child =0; 86 if(!t) 87 return ; 88 p=t; 89 parent=p; 90 while(p){ 91 if(p->data==key){ 92 if(!p->left&&!p->right){ 93 if(p==t){ 94 free(p); 95 }else if(child==0){ 96 parent->left = NULL; 97 free(p); 98 }else{ 99 parent->right=NULL; 100 free(p); 101 } 102 }else if(!p->left){ 103 if(child==0){ 104 parent->left = p->right; 105 }else{ 106 // parent->left=p->left; 107 parent->right=p->right; 108 } 109 110 free(p); 111 112 }else if(!p->right){ 113 if(child==0){ 114 parent->left=p->left; 115 // parent->right=p->right; 116 }else{ 117 parent->right=p->left; 118 } 119 free(p); 120 }else{ 121 l1=p; 122 l=p->right; 123 while(l->left){ 124 l1=l; 125 l=l->left; 126 flag=true; 127 } 128 p->data=l->data; 129 if(flag){ 130 if(l->right) 131 l1->left=l->right; 132 else 133 l1->left=NULL; 134 }else{ 135 p->right=NULL; 136 } 137 break; 138 } 139 p=NULL; 140 }else if(key<p->data){ 141 child =0; 142 parent = p; 143 p=p->left; 144 }else{ 145 child = 1; 146 parent =p; 147 p=p->right; 148 } 149 } 150 } 151 152 int main(){ 153 int i,key; 154 ercha bst, *pos; 155 printf("data source:"); 156 for(i=0;i<ARRAYLEN;i++){ 157 printf("%d ",source[i]); 158 } 159 printf(" "); 160 Createer(&bst,source,ARRAYLEN); 161 printf("遍历二叉排序树"); 162 BST_LDR(&bst); 163 Deleteer(&bst,66); 164 printf(" 删除节点后的节点："); 165 BST_LDR(&bst); 166 getch(); 167 return 0; 168 }
二叉排序树python实现
1 class TreeNode(object): 2 def __init__(self, data, left=None, right=None): 3 self.data = data 4 self.left = left 5 self.right = right 6 self.traversed_right = 0 7 8 class BinaryTree(object): 9 def __init__(self): 10 self.root = None 11 12 def searchNode(self, key): 13 ''' 14 search node 15 ''' 16 node = self.root 17 while node: 18 if key < node.data : 19 node = node.left 20 elif key > node.data: 21 node = node.right 22 else: 23 print("%d is found" % key) 24 return key 25 print(" %d is not found" % key) 26 27 def insertNode(self, key): 28 ''' 29 insert node 30 ''' 31 if self.root is None: 32 self.root = TreeNode(key) 33 return 34 node = self.root 35 while(node is not None): 36 if key > node.data: 37 if node.right is None: 38 node.right = TreeNode(key) 39 return 40 else: 41 node = node.right 42 elif key < node.data: 43 if node.left is None: 44 node.left = TreeNode(key) 45 return 46 else: 47 node=node.left 48 else: 49 print("%d is in BinaryTree" % key) 50 return 51 52 def calculate_depth(self, node): 53 ''' 54 计算节点的高度 55 ''' 56 if (node.left is None) and (node.right is None): 57 return 0 58 elif node.left is None: 59 height = self.calculate_depth(node.right) + 1 60 print("height right is %d"%height) 61 elif node.right is None: 62 height = self.calculate_depth(node.left) + 1 63 print("height left is %d"%height) 64 else: 65 height = max(self.calculate_depth(node.left) , self.calculate_depth(node.right)) + 1 66 print("height is %d"%height) 67 68 return height 69 70 def deleteNode(self, key): 71 ''' 删除分三种情况 72 1)根节点是没有父节点的，故只要找到根节点的右子树的最左孩子的值作为根节点的值，然后将最左孩子置空，这里不能直接将temp置空，temp相当一个引用指向node 73 2)要删除的节点只有左子树或者右子树 74 3)要删除的节点有左右子树，找到删除节点的右子树的最左孩子的值作为删除节点的值 75 ''' 76 parent = None 77 node = self.root 78 while node : 79 if key < node.data: 80 parent = node 81 node = node.left 82 elif key > node.data: 83 parent = node 84 node = node.right 85 else: 86 if parent: 87 print("%d is found. Parent is %d" % (key, parent.data)) 88 else: 89 print("root is found") 90 break 91 if parent is None: 92 temp = node.right 93 temp_parent= node 94 while(temp.left): 95 temp_parent = temp 96 temp = temp.left 97 node.data = temp.data 98 temp_parent.left = None 99 # 判断删除节点是在parent的左边还是右边 100 elif parent.data > key : 101 if node.left is None : 102 parent.left = node.right 103 elif node.right is None: 104 parent.left = node.left 105 else: 106 temp = node.right 107 temp_parent= node 108 while(temp.left): 109 temp_parent = temp 110 temp = temp.left 111 node.data = temp.data 112 temp_parent.left = None 113 elif parent.data < key: 114 if node.left is None: 115 parent.right = node.right 116 elif node.right is None: 117 parent.right = node.left 118 else: 119 temp = node.right 120 temp_parent= node 121 while(temp.left): 122 temp_parent = temp 123 temp = temp.left 124 node.data = temp.data 125 temp_parent.left = None 126 127 def beforeIterator(self): 128 ''' before traversing 129 ''' 130 node = self.root 131 stack = [] 132 while(node or stack): 133 while node: 134 yield node.data 135 stack.append(node) 136 node = node.left 137 node = stack.pop() 138 node = node.right 139 140 def __iter__(self): 141 ''' inorder traversing 142 ''' 143 node = self.root 144 stack = [] 145 while (node or stack): 146 while node : 147 stack.append(node) 148 node = node.left 149 node = stack.pop() 150 yield node.data 151 node = node.right 152 153 154 155 def postIterator(self): 156 ''' postorder traversing 157 ''' 158 node = self.root 159 stack = [] 160 while node or stack: 161 while node and node.traversed_right == 0 : 162 node.traversed_right = 1 # 表示已经入list，list中的节点不能再向左访问 163 stack.append(node) 164 node = node.left 165 166 node = stack.pop() 167 if node.right and node.traversed_right != 2: 168 node.traversed_right = 2 169 stack.append(node) 170 node = node.right 171 else: 172 yield node.data 173 if len(stack) == 0: 174 break 175 176 177 if __name__ == '__main__': 178 lis = [62, 58, 88, 48, 73, 99, 35, 51, 93, 29, 37, 49, 56, 36, 50] 179 bs_tree = BinaryTree() 180 for i in range(len(lis)): 181 bs_tree.insertNode(lis[i]) 182 # bs_tree.insert(100) 183 # bs_tree.delete(58) 184 print("inorder traversing") 185 for i in bs_tree: 186 print(i, end=" ") 187 188 print(" before traversing") 189 for i in bs_tree.beforeIterator(): 190 print(i, end=" ") 191 192 print(" poster traversing") 193 for i in bs_tree.postIterator(): 194 print(i, end=" ") 195 bs_tree.searchNode(4) 196 bs_tree.searchNode(58) 197 # bs_tree.deleteNode(62) 198 print("inorder traversing") 199 for i in bs_tree: 200 print(i, end=" ") 201 print("root data", bs_tree.root.data) 202 print("max depth is %d" % bs_tree.calculate_depth(bs_tree.root) )