Implementation of tree data structure in Python
Environment:
- Language used: python
- Version: 3.3.2
- OS: Fedora 20
- Data Structure used: Python lists
Algorithm:
- Enter the height of the tree
- Type “Add” to add a node to the tree:
- First node should be root
- For any other value:
- Ask the user if its a left or a right node
- Find the possible parents (Note: For example if the height of the tree is 2 with elements 1,2,3. Where 1 is the root node and 2 is left node and 3 is the right node. For node 2 the possible parent is 1 which is at index 1. )
- List the possible parent and allow the user to select the parent
- Add the value to the node
- Enter ‘N’ to go to next level or ‘S’ to stay at the same level. (Note: If we take the same example as explained above then the first level is consist of 1 node i.e. root and the 2nd level is consist of child node 2 and 3 and so on)
- Type “Show” to view the current tree structure
- Type “exit” to exit the program
Code Snippet:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 |
class buildTree (): """Please run the code with Python 3""" def __init__(self): """Class to build your own tree data structure""" self.root_status=False self.data_list=[] self.current_level=1 def possible_parents(self): result=[] for i in range(self.current_level,self.current_level*2): if self.data_list[i]!=-999: result.append(i) return result def addNode(self,node): """The following function will add the node on the left side of the parent""" val=self.possible_parents() if len(val)==0: print ("Error: No parent available. Cannot add any value as a left node") return else: print ("\n") print ("---List of possible parents:") print ("---Index: " + str([data for data in val])) print ("---Value: " + str([self.data_list[data] for data in val])) print ("---Note: The above list shows the indexes and the values of the possible parents. Select the index for which you want to assign the current node as parent") while True: input_user=int(input(">>")) if input_user not in val: print ("Error: Incorrect input. Try Again") else: break input_value=int(input("---Enter the value for {} node with parent {} >> ".format(node,self.data_list[input_user]))) try: if node=="Left": self.data_list[input_user*2]=input_value elif node=="Right": self.data_list[input_user*2+1]= input_value return except: print ("Error: No more space left. Please try again with a higher level/height value") return def changeLevel(self): #Asking the user if they want to continue on the same level or move to another level print ("---If you want to move to the next level type N or S to stay on the same level") print ("---Note: Current level is {}".format(self.current_level-1)) while True: try: input_user = input(">> ") if input_user.lower()=="n": self.current_level=self.current_level*2 break elif input_user.lower()=="s": break except: print ("Error: Exception raised. Incorrect format") print ("Error: Incorrect input. Try Again") return def addRoot(self): """The following function will add the data at root node""" self.root_status=True input_user=input(">>Enter the value for root node >> ") self.data_list[1]=input_user print ("---Value added at root node\n") return def message(self): """The following function will handle the menu portion and after gathering the input from the user it will perform the corrospondng operations """ print ("Type \"Add\" to add a node") print ("Type \"Show\" to view the current tree structure") print ("Type \"Exit\" to \"exit\" the program\n\n") try: input_user=input(">>") #Requesting the user for input except: print ("Error: Incorrect input") if input_user=="add": #1 if if self.root_status==False: #2 if print ("---The first node should be root") return self.addRoot() else: try: input_user=input("---Type Left to enter a left node or Right to enter a right node >> ") except: print ("Error: Incorrect input") if input_user.lower()=="left": self.addNode("Left") #3 if elif input_user.lower()=="right": self.addNode("Right") #3 ends self.changeLevel() #-------------2 if ends #---------------1 if ends elif input_user.lower()=="exit": return -1 elif input_user.lower()=="show": self.printTree(self.data_list) def printTree(self,arr): import sys i,k,j=1,1,1 space=int((len(arr))/2) while i<len(arr): sys.stdout.write (space*" ") while k<=i: if arr[j]==-999: sys.stdout.write ("N") else: sys.stdout.write (str(arr[j])) sys.stdout.write (" ") j+=1 k=k+1 space-=1 k=1 i=i*2 print ("\n") def main(self): while True: try: user_input= int(input("Enter the height of your tree (Note: Level starts at 1) >> ")) self.data_list=[-999 for i in range(0,2**user_input)] #Initializing the array based on the height of the tree break except: print ("Error: Incorrect Format. Try again") var_a=0 while var_a!=-1: var_a=self.message() x=buildTree() x.main() ########################################################## #################------Output-------###################### Type "Add" to add a node Type "Show" to view the current tree structure Type "Exit" to "exit" the program >>add ---The first node should be root >>Enter the value for root node >> 6 ---Value added at root node Type "Add" to add a node Type "Show" to view the current tree structure Type "Exit" to "exit" the program >>show 6 N N N N N N Type "Add" to add a node Type "Show" to view the current tree structure Type "Exit" to "exit" the program >>add ---Type Left to enter a left node or Right to enter a right node >> left ---List of possible parents: ---Index: [1] ---Value: ['6'] ---Note: The above list shows the indexes and the values of the possible parents. Select the index for which you want to assign the current node as parent >>1 ---Enter the value for Left node with parent 6 >> 3 ---If you want to move to the next level type N or S to stay on the same level ---Note: Current level is 0 >> S Type "Add" to add a node Type "Show" to view the current tree structure Type "Exit" to "exit" the program >>show 6 3 N N N N N |