二叉查找树

二叉查找树，也称二叉排序树，二叉搜索树。
它或者是一棵空树；或者是具有下列性质的二叉树：

若左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若右子树不空，则右子树上所有结点的值均大于它的根结点的值； 左、右子树也分别为二叉排序树

步骤：

若根结点的关键字值等于查找的关键字，成功。 否则，若小于根结点的关键字值，递归查左子树；若大于根结点的关键字值，递归查右子树。 若子树为空，查找不成功。

步骤：

首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。 若二叉树为空，则首先单独生成根结点。
注意：新插入的结点总是叶子结点。

假设被删结点是*p，其双亲是*f，不失一般性，设*p是*f的左孩子，下面分三种情况讨论：

若结点*p是叶子结点，则只需修改其双亲结点*f的指针即可。 若结点*p只有左子树PL或者只有右子树PR，则只要使PL或PR 成为其双亲结点的左子树即可。 若结点*p的左、右子树均非空，先找到*p的中序前趋结点*s（注意*s是*p的左子树中的最右下的结点，它的右链域为空），然后有两种做法：
令*p的左子树直接链到*p的双亲结点*f的左链上,而*p的右子树链到*p的中序前趋结点*s的右链上。 以*p的中序前趋结点*s代替*p（即把*s的数据复制到*p中），将*s的左子树链到*s的双亲结点*q的左（或右）链上。
cout "先序遍历：";preTraverse(root);cout " END" endl; cout "中序遍历：";inTraverse(root);cout " END" endl; cout "后序遍历：";postTraverse(root);cout " END" endl; for (int i = 0; i 20; i++) deleteNode(root, i); cout "先序遍历：";preTraverse(root);cout " END" endl; TreeNode *temp = minNode(root); temp != NULL ? cout temp- val endl : cout "null" endl; temp = maxNode(root); temp != NULL ? cout temp- val endl : cout "null" endl; return 0; }

Java实现代码：

package test;

class TreeNode{

 int val;

 TreeNode left;

 TreeNode right;

 TreeNode parent;

 TreeNode(int x){

 this.val = x;

public class BinarySearchTree {

 TreeNode root;

 TreeNode maxElem(TreeNode node){

 while (node != null node.right != null){

 node = node.right;

 return node;

 TreeNode minElem(TreeNode node){

 while (node != null node.left != null){

 node = node.left;

 return node;

 TreeNode search(int key){

 TreeNode temp = root;

 while (temp != null temp.val != key){

 if (temp.val key){

 temp = temp.left;

 }else{

 temp = temp.right;

 return temp;

 boolean insert(int key){

 if (search(key) != null){

 return false;

 TreeNode newnode = new TreeNode(key);

 TreeNode temp = root;

 if (temp == null){

 this.root = newnode;

 return true;

 TreeNode parentNode = null;

 while (temp != null){

 parentNode = temp;

 if (temp.val key){

 temp = temp.left;

 }else{

 temp = temp.right;

 if (parentNode.val key){

 parentNode.left = newnode;

 }else{

 parentNode.right = newnode;

 newnode.parent = parentNode;

 return true;

 boolean delete(int key){

 TreeNode cur = search(key);

 if (cur == null){

 return false;

 TreeNode temp = null;

 if (cur.left != null cur.right != null){

 TreeNode leftMax = maxElem(cur.left);

 cur.val = leftMax.val;

 delete(leftMax.val);

 }else if (cur.left == null cur.right == null){

 temp = null;

 }else if (cur.left != null cur.right == null){

 temp = cur.left;

 }else if (cur.left == null cur.right != null){

 temp = cur.right;

 if (cur.parent == null){

 this.root = temp;

 if (temp != null){

 temp.parent = null;

 else{

 if (cur.parent.left == cur){

 cur.parent.left = temp;

 }else{

 cur.parent.right = temp;

 if (temp != null){

 temp.parent = cur.parent;

 return true;

 void preTraverse(TreeNode node){

 if (node != null){

 System.out.print(node.val + " ");

 preTraverse(node.left);

 preTraverse(node.right);

 void inTraverse(TreeNode node){

 if (node != null){

 inTraverse(node.left);

 System.out.print(node.val + " ");

 inTraverse(node.right);

 void postTraverse(TreeNode node){

 if (node != null){

 postTraverse(node.left);

 postTraverse(node.right);

 System.out.print(node.val + " ");

 public static void main(String[] args){

 BinarySearchTree bst = new BinarySearchTree();

 for (int i = 0; i 20; i++){

 bst.insert((int)(Math.random() * 100));

 //bst.insert(i);

 System.out.print("前序遍历："); bst.preTraverse(bst.root); System.out.println();

 System.out.print("中序遍历："); bst.inTraverse(bst.root); System.out.println();

 System.out.print("后序遍历："); bst.postTraverse(bst.root); System.out.println();

 for (int i = 0; i 20; i++){

 bst.delete(i);

 System.out.print("前序遍历："); bst.preTraverse(bst.root); System.out.println();

 System.out.println("Max:" + bst.maxElem(bst.root).val);

 System.out.println("Min:" + bst.minElem(bst.root).val);

}

Python实现代码：

from random import random

class TreeNode:

 def __init__(self, x):

 self.val = x

 self.left = None

 self.right = None

 self.parent = None

class BinarySearchTree: 

 def __init__(self, root = None):

 self.root = root

 def minElem(self, node):

 temp = node

 while temp and temp.left:

 temp = temp.left

 return temp;

 def maxElem(self, node):

 temp = node

 while temp and temp.right:

 temp = temp.right

 return temp;

 def search(self, node, key):

 if not node:

 return None

 if node.val == key:

 return node

 elif node.val key:

 return self.search(node.left, key)

 else:

 return self.search(node.right, key)

 def insert(self, key):

 if self.search(self.root, key):

 return

 newnode = TreeNode(key)

 if not self.root:

 self.root = newnode

 return

 parentNode = None

 temp = self.root

 while temp:

 parentNode = temp

 if temp.val key:

 temp = temp.left

 else:

 temp = temp.right

 if parentNode.val key:

 parentNode.left = newnode

 else:

 parentNode.right = newnode

 newnode.parent = parentNode

 def delete(self, key):

 cur = self.search(self.root, key)

 if not cur:

 return

 if cur.left and cur.right:

 leftMax = self.maxElem(cur.left)

 n = leftMax.val

 self.delete(leftMax)

 cur.val = n

 else:

 temp = None

 if cur.left:

 temp = cur.left

 elif cur.left:

 temp = cur.right

 if not cur.parent:

 self.root = temp

 temp.parent = None

 else:

 if cur.parent.left == cur:

 cur.parent.left = temp

 else:

 cur.parent.right = temp

 if temp:

 temp.parent = cur.parent

 def preorderTraverse(self, node):

 if node:

 print(node.val,end =  )

 self.preorderTraverse(node.left)

 self.preorderTraverse(node.right)

bst = BinarySearchTree();

for i in range(0, 20):

 bst.insert(int(random()*100))

bst.preorderTraverse(bst.root) 

print()

for i in range(0, 20):

 bst.delete(i);

bst.preorderTraverse(bst.root) 

print(\nThe smallest element is %d. % bst.minElem(bst.root).val)

print(The largest element is %d. % bst.maxElem(bst.root).val)

没有父亲指针的C++实现代码：

#include iostream 

#include algorithm 

using namespace std;

struct TreeNode

 int val;

 TreeNode *left;

 TreeNode *right;

 TreeNode(int x) : val(x), left(NULL), right(NULL) {}

TreeNode* search(TreeNode *root, int key)

 while (root != NULL)

 if (root- val key)

 root = root- left;

 else if (root- val key)

 root = root- right;

 else

 break;

 return root;

void insertNode(TreeNode* root, int key)

 TreeNode *p = root;

 TreeNode *q;

 while (p != NULL)

 if (p- val key)

 q = p;

 p = p- left;

 else if (p- val key)

 q = p;

 p = p- right;

 else

 break;

 if (p != NULL)

 return;

 TreeNode *newnode = new TreeNode(key);

 if (root == NULL)

 root = newnode;

 return;

 if (q- val key)

 q- left = newnode;

 else

 q- right = newnode;

void deleteNode(TreeNode* root, int key)

 TreeNode *p = root;

 TreeNode *q;

 while (p != NULL)

 if (p- val key)

 q = p;

 p = p- left;

 else if (p- val key)

 q = p;

 p = p- right;

 else

 break;

 if (p == NULL)

 return;

 if (p- left != NULL p- right != NULL)

 TreeNode *s = p- left;

 TreeNode *t = p;

 while (s- right != NULL)

 t = s;

 s = s- right;

 p- val = s- val;

 if (t == p)

 p- left = s- left;

 else

 t- right = s- left;

 delete s;

 else

 TreeNode *temp;

 if (p- left == NULL p- right == NULL)

 temp = NULL;

 else if (p- left == NULL)

 temp = p- right;

 else

 temp = p- left;

 if (p == root)

 root = temp;

 else

 if (q- left == p)

 q- left = temp;

 else

 q- right = temp;

 delete p;

void preorderTraverse(TreeNode *root)

 if (root != NULL)

 cout root- val " ";

 preorderTraverse(root- left);

 preorderTraverse(root- right);

int main()

 TreeNode *root = NULL;

 for (int i = 0; i 20; i++)

 insertNode(root, rand() % 50);

 preorderTraverse(root); cout endl;

 for (int i = 0; i 20; i++)

 deleteNode(root, i);

 preorderTraverse(root); cout endl;

}

转载：http://blog.csdn.net/foreverling/article/details/46661937

二叉查找树 Java实现 二叉查找树 Java实现定义：一棵二叉查找树是一棵二叉树，每个节点都含有一个Comparable的键（以及对应的值）。每个节点的键都大于左子树中任意节点的键而小于右子树中任意节点的键。 image 树的术语： Name Function路径 顺着连接点的边从一个节点走向另一个节点，所经过的节点的顺序排列就称为路径。