[工学]9 抽象数据类型和算法.ppt

List,Stack,Queue,Array,link * Fundamentals of Computer Science Hai Mo Page * 9.6 Stacks and Queues Queue(队列) An abstract data type in which items are entered at one end and removed from the other end FIFO, for First In First Out No standard queue terminology Enqueue, Enque, Enq, Enter, and Insert are used for the insertion operation Dequeue, Deque, Deq, Delete, and Remove are used for the deletion operation. * Fundamentals of Computer Science Hai Mo Page * 9.6 Stacks and Queues Implementation of A linked stack * Fundamentals of Computer Science Hai Mo Page * Implementation of A linked queue * Fundamentals of Computer Science Hai Mo Page * 9.7 Trees Tree －At the top of the hierarchy would be the parents, the children would be at the next level, the grandchildren at the next level, and so on. These hierarchical structures are called trees. * Fundamentals of Computer Science Hai Mo Page * 9.7 Trees Binary tree(二分树) － A container object with a unique starting node called the root, in which each node is capable of having two child nodes, and in which a unique path exists from the root to every other node Root －The top node of a tree structure; a node with no parent Leaf node －A tree node that has no children * Fundamentals of Computer Science Hai Mo Page * A Binary tree * Fundamentals of Computer Science Hai Mo Page * A Binary tree Root node Node with two children Node with right child Leaf node Node with left child * Fundamentals of Computer Science Hai Mo Page * Two variations of a binary tree * Fundamentals of Computer Science Hai Mo Page * 9.7 Trees Binary Search Tree（二分查找树） － a node in a binary search tree can have zero, one, or two children. The value in any node is greater than the value in any node in its left subtree and less than the value in any node in its right subtree. * Fundamen