二叉搜索树笔记 CC++

1.概念

1.1 性质：一颗二叉树，可以为空；如果不为空，满足以下性质：

非空左子树的所有键值小于根结点的键值非空右子树的所有键值大于根节点的键值左右子树都是二叉搜索树

1.2 举例说明：

2.二叉搜索树的查找

2.1 思路：

查找从根节点开始，如果树为空，则返回NULL若搜索树非空，则根节点关键字和X进行比较，并进行以下处理：             1.若X小于根键值，则只需在左子树中继续搜索            2.若X大于根键值，则在右子树继续搜索            3.如果相等，则搜索完成，返回该节点的指针

2.2 代码实例：

typedef struct TNode *Position; typedef Position BinTree; /* 二叉树类型 */ struct TNode{ /* 树结点定义 */ int Data; /* 结点数据 */ BinTree Left; /* 指向左子树 */ BinTree Right; /* 指向右子树 */ }; Position IterFind( int X, BinTree BST ) { while( BST ) { if( X > BST->Data ) BST = BST->Right; /*向右子树中移动，继续查找*/ else if( X < BST->Data ) BST = BST->Left; /*向左子树中移动，继续查找*/ else /* X == BST->Data */ return BST; /*查找成功，返回结点的找到结点的地址*/ } return NULL; /*查找失败*/ }

2.3 注：

由于非递归函数的执行效率高，可将“尾递归”函数改为迭代函数。查找效率决定于树的高度

2.4 查找最大最小元素：

二叉树的最小元素一定在最左分支的端结点上二叉树最大元素一定在最右分支端结点上

3.二叉搜索树的插入

3.1 思路：关键是要找到插入的位置，可以采用和Find（）类似的方法。要注意插入的地方一定是叶结点，即插入处该子树的根节点为空。

3.2 代码实例：

typedef struct TNode *Position; typedef Position BinTree; /* 二叉树类型 */ struct TNode{ /* 树结点定义 */ int Data; /* 结点数据 */ BinTree Left; /* 指向左子树 */ BinTree Right; /* 指向右子树 */ }; BinTree Insert( BinTree BST, int X ) { if( !BST ){ /* 若原树为空，生成并返回一个结点的二叉搜索树 */ BST = (BinTree)malloc(sizeof(struct TNode)); BST->Data = X; BST->Left = BST->Right = NULL; } else { /* 开始找要插入元素的位置 */ if( X < BST->Data ) BST->Left = Insert( BST->Left, X ); /*递归插入左子树*/ else if( X > BST->Data ) BST->Right = Insert( BST->Right, X ); /*递归插入右子树*/ /* else X已经存在，什么都不做 */ } return BST; }

4.二叉搜索树的删除

4.1 思路：二叉树的删除分三种情况：

删除的是叶结点：直接删除，并修改其父节点指针（置为NULL）要删除的结点只有一个孩子结点：将其父节点的指针指向要删的除结点的子节点（见：例 删除33）要删除的结点有左右两棵子树：用右子树的最小元素，或左子树的最大元素代替被删除的点（见：例 删除41）

4.2 代码实例：

typedef struct TNode *Position; typedef Position BinTree; /* 二叉树类型 */ struct TNode{ /* 树结点定义 */ int Data; /* 结点数据 */ BinTree Left; /* 指向左子树 */ BinTree Right; /* 指向右子树 */ }; Position FindMin( BinTree BST ) { if( !BST ) return NULL; /*空的二叉搜索树，返回NULL*/ else if( !BST->Left ) return BST; /*找到最左叶结点并返回*/ else return FindMin( BST->Left ); /*沿左分支继续查找*/ } BinTree Delete( BinTree BST, int X ) { Position Tmp; if( !BST ) printf("要删除的元素未找到"); else { if( X < BST->Data ) BST->Left = Delete( BST->Left, X ); /* 从左子树递归删除 */ else if( X > BST->Data ) BST->Right = Delete( BST->Right, X ); /* 从右子树递归删除 */ else { /* BST就是要删除的结点 */ /* 如果被删除结点有左右两个子结点 */ if( BST->Left && BST->Right ) { /* 从右子树中找最小的元素填充删除结点 */ Tmp = FindMin( BST->Right ); BST->Data = Tmp->Data; /* 从右子树中删除最小元素 */ BST->Right = Delete( BST->Right, BST->Data ); } else { /* 被删除结点有一个或无子结点 */ Tmp = BST; if( !BST->Left ) /* 只有右孩子或无子结点 */ BST = BST->Right; else /* 只有左孩子 */ BST = BST->Left; free( Tmp ); } } } return BST; }