首页 > 代码库 > 数据结构-二叉查找树
数据结构-二叉查找树
前序遍历：
后序遍历：
二叉查找树按照二叉树进行组织。二叉查找树关键字的存储方式总是瞒住二叉查找树性质：
设x为二查查找树种一个节点。如果y是x的左子树中的一个节点，那么key[x] >= key[y]。如果y是x的右子树的一个节点，那么key[x] <= key[y]。
这样对二叉查找树进行中序遍历就可得到书中所有元素的一个非降序排列。
查找某一个存在节点的前驱和后继。某一个节点x的后继就是大于key[x]的关键字中最小的那个节点，前驱就是小于key[x]的关键字中最大的那个节点。查找二叉前驱和后继节点的算法如下所示：
1 typedef struct _node { 2 struct _node *left_child; 3 struct _node *right_child; 4 struct _node * parent; 5 ctype data; 6 }node; //树节点数据结构定义 7 8 typedef node* Tree; 9 10 //查找二叉查找树中关键字最小的节点，返回指向该节点的指针11 Tree tree_minimum(Tree root)12 {13 Tree p = root;14 while (p->left_child != null)15 p = p->left_child;16 return p;17 }18 19 //查找二叉查找树中关键字最大的节点，返回指向该节点的指针20 Tree tree_maxmum(Tree root)21 {22 Tree p = root;23 24 while (p->right_child != null)25 {26 p = p->right_child;27 }28 return p;29 }30 31 //查找二叉查找树中节点x的后继节点，返回指向该节点的指针32 //在查找过程中，如果节点x右子树不为空，那么返回右子树的最小节点即可33 //如果节点x的右子树为空，那么后继节点为x的某一个祖先节点的父节点，而且该祖先节点是作为其父节点的左儿子34 Tree tree_successor(Tree x)35 {36 if (x->right_child != null)37 return tree_minimum(x->right_child);38 39 //x用来保存待确定的节点40 //y为x的父节点41 Tree y = x->parent;42 43 while (y != NULL && x == y->right_child)44 {45 x = y;46 y = y->parent;47 }48 return y;49 }50 51 52 //查找二叉查找树中节点x的前驱节点，返回指向该节点的指针53 //在查找过程中，如果节点x左子树不为空，那么返回左子树的最大节点即可54 //如果节点x的左子树为空，那么前驱节点为x的某一个祖先节点的父节点，而且该祖先节点是作为其父节点的右儿子55 Tree tree_predecessor(Tree x)56 {57 if (x->left_child != null)58 return tree_maxmum(x->left_child);59 60 Tree y = x->parent;61 while (y != NULL && x == y->left_child)62 {63 x = y;64 y = y->parent;65 }66 return y;67 }
数据结构-二叉查找树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。