Definition for trees is simple, here we discuss the difference between Binary trees and Binary Search Trees. Binary Trees : Binary tree is a set of nodes that is either empty or consists of a root and two disjoint binary trees called left and right subtrees. Binary Search Tree :It is a binary tree,it may be empty ,if it's not empty, then it satisfies the following properties: 1.Every element has a key and no two elements have the same key. 2.All keys in the left subtree(if any) are smaller than the key in the root. 3.All keys in the right subtree(if any) are greater than the key in the root. 4.The left and right subtrees are also binary search trees. Binary Heap: A binary heap is a complete binary tree and satisfies two constraints 1. All levels of the tree, except possibly the last one(deepest) are fully filled, and , if the last level of the tree is not complete, the nodes of that level are filled from left to right. 2. Each node is greater than or equal to each of its children(max heap). Algorithm1: Recursive search of a binary search tree Since the definition of binary search tree is recursive, it is easiest to describe a recursive search method. Algorithm search(t,x) { if(t=0) then return 0; else if(x=t-data) then return x; else if(xt-data) then return search(t-lchild,x); else return search(t-rchild,x); } Algorithm2: Insertion into a binary search tree Algorithm Insert(x) { found=false; p=tree; while((p!=0) and not found) do { q=p; //Save p. if(x=(p-data)) then found=true; else if(x(p-data)) then p=(p-lchild); else p=(p-rchild); } if(not found) then { p=new TreeNode; p-lchild=0; p-rchild=0; p-data=x; if(tree!=0)then { if(x(q-data)) then (q-lchild)=p; else (q-rchild)=p; }else tree=p; } }
标签: Trees经管大学堂：名校名师名课
京公网安备 11010802022788号
论坛法律顾问：王进律师
知识产权保护声明
免责及隐私声明
