当前位置：文档库 › 二叉搜索树

二叉搜索树

概念

二叉搜索树（Binary Search Tree），又称二叉排序树，它或者是一颗空树，或者具有如下性质的树：

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

基本操作

插入

向二叉搜索树中插入新元素时，必须先检测这个元素是否在树中已经存在。如果已经存在，则不进行插入，如果元素不存在则将新元素插入到搜索停止的时候，也就是每次插入都是一个叶子节点。

查找

在一棵不为空的二叉搜索树中查找元素时，如果要查找的元素与根节点的值相等，则返回true 或根节点，如果小于根节点的值，则在左子树查找，如果大于根节点的值，在其右子树中查找。否则，返回false或者NULL。

删除

相对查找和插入操作来说，删除算是二叉搜索树中最复杂的一个操作。我们需要分情况讨论。

首先判断是否是一颗空树，是空树则直接返回false，表示删除失败，否则进行下一步

判断当前树是否只有一个结点，且比较要删除的值与根节点的值是否相同，相同则删除成功，不相同，表示删除失败

以上条件都不满足，可分以下三步

找到要删除的结点

分情况讨论节点的情况，根据所在位置的不同，进行值变换，和指针调整（下面有具体描述）

删除该节点

注意：这里我们将叶子结点进行了归并，总共分为下面三种情况：

要删除的结点分别对应三种情况：

一. 只有左孩子

1). pcur 为根节点更新pRoot的指向为当前结点的左孩子

2). pcur 不为根节点更改要删除结点的父节点的指向

1>. 如果要删除结点是父节点的左孩子parent->left = pcur->left

2>. 如果要删除结点是父节点的右孩子parent->right = pcur->left

二. 只有右孩子

1). pcur 为根节点更新pRoot的指向为当前结点的右孩子

2). pcur 不为根节点

三. 左右孩子都有

1). 第一步找到要删除结点右子树中最小的结点并替换，转换为删除右子树中最小的结点

2). 删除右子树中最小的结点分两种情况

1>. 找到的结点为pCur的右孩子此时将pCur->right = pDelete->right

2>. 找到的结点不是pCur的右孩子需要更新pDelete结点的父节点指向parent->left = pDelete->right

上述文字对应情况的图解

一、只有左孩子

1）、pCur为根节点的情况：

2）、pCur不为根节点的情况

二、只有右孩子

1）、pCur为根节点的情况：

2）、pCur不为根节点的情况

三、左右孩子都有

有两种实现方式，第一种是在当前结点的左子树中找到最大的节点，第二种是在当前结点的右子树中找到最小的结点（这里是用了第二种）

找到右子树中最小的结点后有如下两种情况

1.d 找到的结点为pCur的右孩子

d 找到的结点不是pCur的右孩子

实现代码

BinarySearchTree.hpp

#ifndef _BINARYSEARCHTREE_H_

#define _BINARYSEARCHTREE_H_

#include

using namespace std;

template

class BSTree

{

// 二叉搜索树结点类型

template

struct BSTNode

{

BSTNode(const K& _key, const V& _val)

: key(_key)

, val(_val)

, left(NULL)

, right(NULL)

{}

K key; // 结点的键

V val; // 结点对应的值

BSTNode * left; // 指向左孩子

BSTNode * right; // 指向右孩子};

public:

// 构造函数

BSTree()

: pRoot(NULL)

{}

// 拷贝构造

BSTree(const BSTree& bst)

:pRoot(NULL)

{

pRoot = _Copy(bst.GetRoot());

}

// 赋值运算符重载

BSTree& operator=(const BSTree& bst) {

if (this != &bst)

{

_Clear(pRoot);

pRoot = _Copy(bst.GetRoot());

}

return *this;

}

// 虚构函数

~BSTree()

{

_Clear(pRoot);

}

// 插入结点递归写法

void Insert(const K& key, const V& val)

{

_Insert(pRoot, key, val);

}

// 插入结点非递归

void InsertNor(const K& key, const V& val)

{

_InsertNor(pRoot, key, val);

}

// 查找结点递归写法

bool Find(const K& _key)

{

return _Find(pRoot, _key);

}

// 查找结点非递归写法

bool FindNor(const K& _key)

{

return _FindNor(pRoot, _key);

}

// 删除指定key结点

bool Remove(const K& key)

{

if (NULL == pRoot)

return false;

else

return _Remove(pRoot, key);

}

// 判空

bool Empty()const

{

return pRoot == NULL;

}

// 获取根节点

const BSTNode* GetRoot()const

{

return pRoot;

}

private:

// 拷贝构造和赋值运算符重载调用

BSTNode* _Copy(const BSTNode* pRoot)

{

BSTNode* temp = NULL;

if (pRoot != NULL)

{

temp = new BSTNode(pRoot->key, pRoot->val);

temp->left = _Copy(pRoot->left);

temp->right = _Copy(pRoot->right);

}

return temp;

}

// 删除

bool _Remove(BSTNode*& _pRoot, const K& _key)

{

// 特殊处理要删除的结点是根节点，且只有一个结点

if (_pRoot->left == NULL && _pRoot->right == NULL && _pRoot->key == _key)

{

delete _pRoot;

_pRoot = NULL;

return true;

}

// 第一步找到要删除的结点

BSTNode* pCur = _pRoot;

BSTNode* pParent = NULL;

while (pCur != NULL)

{

if (_key < pCur->key)

{

pParent = pCur;

pCur = pCur->left;

}

else if (pCur->key < _key)

{

pParent = pCur;

pCur = pCur->right;

}

else

break;

}

// 第二步分情况讨论结点情况

* 要删除的结点分别对应三种情况：

* 1. 只有左孩子

* (1). pcur 为根节点更新pRoot的指向为当前结点的左孩子

* (2). pcur 不为根节点更改要删除结点的父节点的指向

* 1>. 如果要删除结点是父节点的左孩子parent->left = pcur->left

* 2>. 如果要删除结点是父节点的右孩子parent->right = pcur->left

* 2. 只有右孩子

* (1). pcur 为根节点更新pRoot的指向为当前结点的右孩子

* (2). pcur 不为根节点

* 1>.

* 3. 左右孩子都有

* (1). 第一步找到要删除结点右子树中最小的结点并替换，转换为删除右子树中最小的结点

* (2). 删除右子树中最小的结点分两种情况

* 1>. 找到的结点为pCur的右孩子此时将pCur->right = pDelete->right

* 2>. 找到的结点不是pCur的右孩子需要更新pDelete结点的父节点指向parent->left = pDelete->right

/* 找到要删除的结点*/

if (NULL == pCur) // 需要删除的结点不存在

return false;

if (pCur->right == NULL) // 当前结点无右孩子

{

if (pCur == pRoot) // 删除的结点是根节点时

{

pRoot = pRoot->left;

}

else // 删除的结点非根节点

{

if (pParent->left == pCur) // 要删除的结点是父节点的左孩子

pParent->left = pCur->left;

else // 要删除的结点是父节点的右孩子

pParent->right = pCur->left;

}

else if (pCur->left == NULL) // 当前结点无左孩子

{

if (pCur == pRoot)

{

pRoot = pRoot->right;

}

else

{

if (pParent->left == pCur)

pParent->left = pCur->right;

else

pParent->right = pCur->right;

}

else // 左右孩子都有

{

BSTNode* pDelete = pCur->right; // 在右子树中找到最小的结点

pParent = pCur;

while ( pDelete->left )

{

pParent = pDelete;

pDelete = pDelete->left;

}

pCur->key = pDelete->key; // 将右子树中最小的结点赋给pCur

pCur->val = pDelete->val;

if (pCur->right == pDelete) // 如果右子树中最小的结点就是pCur 的右孩子

pCur->right = pDelete->right;

else

pParent->left = pDelete->right;

pCur = pDelete; // 将最终要delete的结点赋给pCur为了在if else 外部统一delete pCur

}

/* 第三步已经结点找到删除即可*/

delete pCur;

pCur = NULL;

return true;

}

// 清空

void _Clear(BSTNode*& pRoot)

{

if (pRoot != NULL)

{

_Clear(pRoot->left);

_Clear(pRoot->right);

delete pRoot;

pRoot = NULL;

}

// 非递归实现查找

bool _FindNor(const BSTNode* pRoot, const K& _key)

{

while (pRoot != NULL)

{

if (pRoot->key == _key)

return true;

else if (pRoot->key > _key)

pRoot = pRoot->left;

else

pRoot = pRoot->right;

}

return false;

}

// 递归实现查找

bool _Find(const BSTNode* pRoot, const K& _key)

{

if (pRoot == NULL)

return false;

if (pRoot->key == _key)

return true;

else if (pRoot->key > _key)

return _Find(pRoot->left, _key);

else

return _Find(pRoot->right, _key);

}

// 递归实现插入

void _Insert(BSTNode*& pRoot, const K& _key, const V& _val) {

if (pRoot == NULL)

{

pRoot = new BSTNode(_key, _val);

}

else

{

if (_key > pRoot->key)

_Insert(pRoot->right, _key, _val);

else if (_key < pRoot->key)

_Insert(pRoot->left, _key, _val);

else

return;

}

// 非递归实现插入

void _InsertNor(BSTNode*& pRoot, const K& _key, const V& _val) {

if (pRoot == NULL)

{

pRoot = new BSTNode(_key, _val);

return;

}

BSTNode* pCur = pRoot;

BSTNode* pPre = pRoot;

while (pCur != NULL)

{

pPre = pCur;

if (_key < pCur->key)

{

pCur = pCur->left;

}

else if (_key > pCur->key)

{

pCur = pCur->right;

}

else

return;

}

if (_key < pPre->key)

pPre->left = new BSTNode(_key, _val);

else

pPre->right = new BSTNode(_key, _val);

}

private:

BSTNode* pRoot; // 维护一个根节点

};

#endif //_BINARYSEARCHTREE_H_

test.cpp

#include "BinarySearchTree.hpp"

void Test_BST()

{

BSTree bst;

bst.Insert(20, "根节点");

bst.Insert(1, "根节点");

bst.Insert(10, "左子树");

bst.Insert(30, "右子树");

bst.Insert(9, "嘿嘿");

cout << boolalpha << bst.FindNor(20)<< endl;

cout << boolalpha << bst.FindNor(10)<< endl;

cout << boolalpha << bst.FindNor(30)<< endl;

cout << boolalpha << bst.FindNor(9) << endl;

cout << boolalpha << bst.FindNor(0) << endl;

bst.~BSTree();

bst.Find(1);

}

void Test_BST_Remove()

{

BSTree bt;

bt.InsertNor(5, 5);

bt.InsertNor(3, 3);

bt.InsertNor(4, 4);

bt.InsertNor(1, 1);

bt.InsertNor(7, 7);

bt.InsertNor(8, 8);

bt.InsertNor(2, 2);

bt.InsertNor(6, 6);

bt.InsertNor(0, 0);

bt.InsertNor(9, 9);

bt.Remove(5);

bt.Remove(6);

bt.Remove(1);

bt.Remove(3);

bt.Remove(7);

BSTree bt1(bt);

BSTree bt2;

bt1 = bt2 = bt;

}

int main()

{

//Test_BST();

Test_BST_Remove();

return 0;

}

数据结构课程设计报告二叉排序树的实现

课程设计课程名称数据结构课程设计题目名称二叉排序树的实现学院应用数学学院专业班级学号学生指导教师 2013 年 12 月 26 日

1.设计任务 1）实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、、成绩3项),对比查找效率，并说明为什么二叉排序树效率高（或者低）。 2. 函数模块： 2.1.主函数main模块功能 1.通过bstree CreatTree()操作建立二叉排序树。 2.在二叉排序树t过操作bstree InsertBST(bstree t,int key,nametype name,double grade)插入一个节点。 3. 从二叉排序树t过操作void Delete(bstree &p)删除任意节点。 4. 在二叉排序树t过操作bstnode *SearchBST(bstree t,keytype key)查找节点。 5. 在二叉排序树t过操作p=SearchBST(t,key)查询，并修改节点信息 6. 非递归遍历二叉排序树。 7. 定义函数void compare()对数组和二叉排序树的查找效率进行比较比较。 2.2创建二叉排序树CreatTree模块从键盘中输入关键字及记录，并同时调用插入函数并不断进行插入。最后，返回根节点T。 2.3删除模块：二叉排序树上删除一个阶段相当于删去有序系列中的一个记录，只要在删除某个节点之后依旧保持二叉排序树的性质即可。假设二叉排序树上删除节点为*p（指向节点的指针为p），其双亲节点为*f（节点指针为f）。若*p节点为叶子节点，则即左右均为空树，由于删去叶子节点不破坏整棵树的结构，则只需修改其双亲节点的指针即可；若*p节点只有左子树或只有右子树，此时只要令左子树或右子树直接成为其双亲节点*f的左子树即可；若*p节点的左子树和右子树均不为空，其一可以令*p的左子树为*f的左子树，而*p的右子树为*s的右子树，其二可以令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的直接前驱（或直接后继）。在二叉排序树中删除一个节点的算法为 void DeleteData(bstree &t,keytype key) 若二叉排序树t中存在关键字等于key的数据元素，则删除该数据元素节点，并返回TRUE，否则返回FALSE。 2.4插入模块二叉排序树是一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找的过程中，当树中不存在关键字等于给定值得节点时在进行插入。

数据结构二叉树习题含答案

2.1 创建一颗二叉树创建一颗二叉树，可以创建先序二叉树，中序二叉树，后序二叉树。我们在创建的时候为了方便，不妨用‘#’表示空节点，这时如果先序序列是：6 4 2 3 # # # # 5 1 # # 7 # #，那么创建的二叉树如下：下面是创建二叉树的完整代码：穿件一颗二叉树，返回二叉树的根 2.2 二叉树的遍历二叉树的遍历分为：先序遍历，中序遍历和后序遍历，这三种遍历的写法是很相似的，利用递归程序完成也是灰常简单的： 2.3 层次遍历层次遍历也是二叉树遍历的一种方式，二叉树的层次遍历更像是一种广度优先搜索（BFS）。因此二叉树的层次遍历利用队列来完成是最好不过啦，当然不是说利用别的数据结构不能完成。 2.4 求二叉树中叶子节点的个数树中的叶子节点的个数= 左子树中叶子节点的个数+ 右子树中叶子节点的个数。利用递归代码也是相当的简单， 2.5 求二叉树的高度求二叉树的高度也是非常简单，不用多说：树的高度= max(左子树的高度，右子树的高度) + 1 2.6 交换二叉树的左右儿子交换二叉树的左右儿子，可以先交换根节点的左右儿子节点，然后递归以左右儿子节点为根节点继续进行交换。树中的操作有先天的递归性。。 2.7 判断一个节点是否在一颗子树中可以和当前根节点相等，也可以在左子树或者右子树中。 2.8 求两个节点的最近公共祖先求两个节点的公共祖先可以用到上面的：判断一个节点是否在一颗子树中。（1）如果两个节点同时在根节点的右子树中，则最近公共祖先一定在根节点的右子树中。（2）如果两个节点同时在根节点的左子树中，则最近公共祖先一定在根节点的左子树中。（3）如果两个节点一个在根节点的右子树中，一个在根节点的

数据结构：二叉树子系统

/* *题目：按屏幕提示用前序方法建立一棵二叉树，并能按凹入法显示二叉树结构。 * 编写前序遍历、中序遍历、后序遍历、层次遍历程序。 * 编写求二叉树的叶结点数、总结点数和深度的程序。 * 设计一个选择式菜单，以菜单方式选择下列操作。 * 二叉树子系统 * *************************** **** * * 1 -- 建二叉树* * * 2 -- 凹入显示* * * 3 -- 先序遍历* * * 4 -- 中序遍历* * * 5 -- 后序遍历* * * 6 -- 层次遍历* * *7 -- 求叶子数* * *8 -- 求结点数* * *9 -- 求树深度* * *0 -- 返回* * *************************** **** * 请选择菜单号（0--9） */ #include #include typedef struct bTree // 二叉树结点{ char data; // 值域 struct bTree *lchild; // 左孩子 struct bTree *rchild; // 右孩子 }BT; BT *createTree(); void showTree(BT *t); void preOrder(BT *t); void postOrder(BT *t); void inOrder(BT *t); void levelOrder(BT *t); int leafNum(BT *t); int nodeNum(BT *t); int treeDepth(BT *t); /************************************************* Function: main() Description: 主调函数 Calls: createTree() showTree() preOrder() postOrder() in Order() leafNum() levelOrder() no deNum() treeDepth() In put: NULL

二叉搜索树C语言探讨与实现

二叉搜索树的详解所谓二叉搜索树，就是指对包括树本身的任何一棵子树，左子树的值要小于根节点，右子树的值要大于根节点。以便在搜索的时候能够从根节点开始一直往下检索。在搜索树构造合理的情况下复杂度是。这里主要介绍二叉搜索树的创建和查询以及增加节点和删除节点。先定义节点的结构体：为了索引更加方便，定义了父节点。二叉搜索树的创建二叉搜索树的显示二叉搜索树的插入二叉搜索树的删除完整代码：链接：密码：

二叉搜索树的创建二叉搜索树的创建分为直接创建和随机创建。所谓直接创建，就是拿到一系列树以后，根据原有数据的顺序依次以增加节点的方式扩展原二叉搜索树。而随机创建就是指创建二叉树的过程随机的从给定树种随机选取一个点加入二叉搜索树。先来介绍直接创建的办法：先创建根节点判空寻找下一个节点插入的位置这里有两点要注意的：是用来表示往下后的父节点。新节点要插入的位置的父节点，它一定不会是有两个孩子的节点。如果比插入点的值要大，则父节点一定没有左孩子；如果比插入点的值要小，则没有右孩子。插入节点

直接创建的整个函数为：

二叉树的查找这里要注意的是，我们认为在二叉查找数中的关键字是没有重复，如果有重复的只会查找到其中一个，而无法保证返回所有的值。用递归的方法是最简单的方法：如果为空，或者找到关键词搜索左子树

搜索右子树二叉树的显示（层次遍历）二叉树的层次遍历现在主要事采用队列的方法来处理：队列的原理性的内容随便百度都有，这里直接上源码值得注意的是，虽然我们定义的节点是带有父节点的内容，但是实际上我们的遍历算法并没有用到父节点，具有一般适应性。记录层数初始化遍历过程判断是否还有节点

二叉排序树运算-数据结构与算法课程设计报告_l

合肥学院计算机科学与技术系课程设计报告 2009 ～2010 学年第二学期课程数据结构与算法课程设计名称二叉排序树运算学生姓名顾成方学号0704011033 专业班级08计科(2) 指导教师王昆仑张贯虹 2010 年 5 月

题目：（二叉排序树运算问题）设计程序完成如下要求：对一组数据构造二叉排序树，并在二叉排序树中实现多种方式的查找。基本任务：⑴选择合适的储存结构构造二叉排序树；⑵对二叉排序树T作中序遍历，输出结果；⑶在二叉排序树中实现多种方式的查找，并给出二叉排序树中插入和删除的操作。 ⑷尽量给出“顺序和链式”两种不同结构下的操作，并比较。一、问题分析和任务定义本次程序需要完成如下要求：首先输入任一组数据，使之构造成二叉排序树，并对其作中序遍历，然后输出遍历后的数据序列；其次，该二叉排序树能实现对数据（即二叉排序树的结点）的查找、插入和删除等基本操作。实现本程序需要解决以下几个问题： 1、如何构造二叉排序树。 2、如何通过中序遍历输出二叉排序树。 3、如何实现多种查找。 4、如何实现插入删除等操作。二叉排序树的定义：

⑴其左子树非空，则左子树上所有结点的值均小于根结点的值。 ⑵若其右子树非空，则右子树上所有结点的值大于根结点的值。 ⑶其左右子树也分别为二叉排序树。本问题的关键在于对于二叉排序树的构造。根据上述二叉排序树二叉排序树的生成需要通过插入算法来实现：输入（插入）的第一个数据即为根结点；继续插入，当插入的新结点的关键值小于根结点的值时就作为左孩子，当插入的新结点的关键值大于根结点的值时就作为右孩子；在左右子树中插入方法与整个二叉排序树相同。当二叉排序树建立完成后，要插入新的数据时，要先判断已建立的二叉排序树序列中是否已有当前插入数据。因此，插入算法还要包括对数据的查找判断过程。本问题的难点在于二叉排序树的删除算法的实现。删除前，首先要进行查找，判断给出的结点是否已存在于二叉排序树之中；在删除时，为了保证删除结点后的二叉树仍为二叉排序树，要考虑各种情况，选择正确

基于matlab构造最优二叉树

摘要 Matlab是一种用于算法开发,数据可视化，数据分析以及数值计算的高级技术计算语言和交互式环境。MATLAB是当今最优秀的科技应用软件之一，利用MATLAB 对层次分析法的判断、分析和计算过程进行处理后，为决策者提供方便友好的对话界面。只要决策者在MATLAB软件中输入自己的层次结构方案和两两对比的判断矩阵后能迅速得出相应的结果，为解决实际问题提供一个快捷的方法。从而提高人们的决策效率，同时也为科技工作者使用层次分析法提供一种新思路。本文是利用matlab的强大功能来构造最优二叉树。二叉树是一种非常重要以及常见的数据结构，不仅在计算机系统中运用广泛，而且在日常生活中也有一定的应用。本文概述了二叉树的数据结构以及使用matlab来模拟出二叉树的数据结构，从而来实现二叉树的插入，删除，查询等常用功能。关键词：Matlab；二叉树；数据结构；

ABSTRACT Matlab is used for algorithm development, data visualization, data analysis and numerical calculation of the senior technical computing language and interactive environment. Matlab is the most outstanding application of science and technology, using MATLAB to determine the right level of analysis, analysis and computation processing, in order to provide decision makers with convenient user-friendly dialog interface. When the decision-makers in MATLAB software, enter their own hierarchy of the program and judgment matrix to determine quickly after the corresponding results obtained, in order to solve practical problems to provide a quick method. Thereby enhancing the efficiency of people's decision-making, but also for the scientific and technological workers to use AHP to provide a new idea.This article is using matlab to construct optimal binary tree. Binary Tree is a very important and common data structures, it is widely used in the computer system. This article outlines the binary tree data structure and the use of matlab to simulate a binary tree data structure, in order to achieve the binary tree insertion, deletion, query and other commonly used functions. Key words：Matlab；binary tree；data struction；

数据结构二叉树练习题答案

数据结构第6章树和二叉树一、下面是有关二叉树的叙述，请判断正误（√）1.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n-1个非空指针域。 n个结点的二叉树有n-1条分支（×）2.二叉树中每个结点的两棵子树的高度差等于1。（√）3.二叉树中每个结点的两棵子树是有序的。（×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。（×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（应当是二叉排序树的特点）（×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2k-1）（×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i -1个结点。

（应2i-1）（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，即有后继链接的指针仅n-1个，还有n+1个空指针。）采用二叉链表存储有2n个链域，空链域为：2n-（n-1）=n+1 （√）10.具有12个结点的完全二叉树有5个度为2的结点。最快方法：用叶子数＝[ n/2] ＝6，再求n2=n0-1=5 [n/2] 除的结果四舍五入二、填空 1．由３个结点所构成的二叉树有5种形态。 2. 一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 (或：总结点数为n=2k-1=26-1=63，叶子数为n0= [ n/2] =32，满二叉数没有度为1的结点，由n0=n2+1得n2=n0-1=32-1=31)

实验5 二叉搜索树的基本操作(大作业)

浙江大学城市学院实验报告课程名称数据结构与算法实验项目名称实验五二叉搜索树的基本操作学生姓名蓝礼巍专业班级学号实验成绩指导老师（签名）日期一.实验目的和要求 1．掌握二叉搜索树的基本概念。 2．掌握二叉搜索树基本操作的实现。二. 实验内容 1. 设在一棵二叉搜索树的每个结点的data域中，含有关键字key域和统计相同关键字元素个数的count域。当向该树插入一个元素时，若树中已有相同关键字值的结点，则使该结点的count域值增1，否则由该元素值生成一个新结点插入到该树中，并使其count域值为1。当向该树删除一个元素时，若树中该元素结点的count域值大于1，则使该结点的count域值减1，否则（count 域值等于1）删除该结点。编写头文件bstree.h，实现上述二叉搜索树的存储结构定义与基本操作实现函数；编写主函数文件test8_1.cpp，验证头文件中各个操作。基本操作包括： ①void InitBSTree(BTreeNode *&bst); //初始化该二叉搜索树 ②void PrintBSTree(BTreeNode *bst); //以广义表形式输出该二叉搜索树（输出内容包括关键字值与相同元素个数值） ③void Insert (BTreeNode *&bst, ElemType item); //插入一个元素到该二叉搜索树（用非递归算法实现） ④int Delete (BTreeNode *&bst , ElemType item); //从二叉搜索树中删除某个元素（用非递归算法实现） ⑤ElemType MaxBSTree(BTreeNode *bst); //求该二叉搜索树的最大关键字值（用非递归算法实现） 2.选做：编写下列操作的实现函数，添加到头文件bstree.h中，并在主函数文件test8_1.cpp中添加相应语句进行测试。 ①void PrintNode1(BTreeNode *bst); //按递减序打印二叉搜索树中所有左子树为空，右子树非空的结点数据域的值 ②void PrintNode2(BTreeNode *bst, int x );

树与二叉树习题解析(答)

习题五树与二叉树一、选择题 1、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足。 A、所有的结点均无左孩子 B、所有的结点均无右孩子 C、只有一个叶子结点 D、是任意一棵二叉树 2、一棵完全二叉树上有1001个结点，其中叶子结点的个数是。 A、250 B、500 C、254 D、505 E、以上答案都不对 3、以下说法正确的是。 A、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点 B、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点 C、在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点 D、在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点 4、以下说法错误的是。 A、哈夫曼树是带权路径长度最短得数，路径上权值较大的结点离根较近 B、若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍历序列中的第一个结点 C、已知二叉树的前序遍历和后序遍历并不能唯一地确定这棵树,因为不知道树的根结点是哪一个 D、在前序遍历二叉树的序列中,任何结点其子树的所有结点都是直接跟在该结点之后的 5、一棵有124个叶结点的完全二叉树，最多有个结点。

A、247 B、248 C、249 D、250 E、251 6、任何一棵二叉树的叶结点在前（先）序、中序和后序遍历序列中的相对次序。 A、不发生变化 B、发生变化 C、不能确定 7、设a、b为一棵二叉树上的两个结点。在中序遍历时，a在b前面的条件是。 A、a在b的右方 B、a在b的左方 C、a是b的祖先 D、a是b的子孙 8、设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含的结点总数为。 A、不确定 B、2k C、2k-1 D、2k+1 9、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有个结点。 A、13 B、12 C、26 D、25 10、下面几个符号串编码集合中，不是前缀编码的是。 A、{0，10，110，1111} B、{11，10，001，101，0001} C、{00，010，0110，1000} D、{b,c,aa,ac,aba,abb,abc} 11、欲实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳的方案是二叉树采用存储结构。 A、三叉链表 B、广义表 C、二叉链表 D、顺序表 12、以下说法错误的是。 A、存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同 B、二叉树是树的特殊情形 C、由树转换成二叉树，其根结点的右子树总是空的 D、在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树 13、树的基本遍历策略可分为先根遍历和后根遍历，二叉树的基本遍历策略可分为先序、中序和后序三种遍历。我们把由树转化得到的二叉树称该树对应的二叉树，则下面是正确的。 A、树的先根遍历序列与其对应的二叉树先序遍历序列相同

最优二叉查找树

二叉查找树（BST，Binary Search Tree），又名二叉搜索树或二叉检索树，是一颗满足如下条件的树： 1、每个节点包含一个键值 2、每个节点有最多两个孩子 3、对于任意两个节点x和y，它们满足下述搜索性质: a、如果y在x的左子树里，则key[y] <= key[x] b、如果y在x的右子树里，则key[y] >= key[x] 最优二叉查找树（Optimal BST，Optimal Binary Search Tree）最优二叉查找树是使查找各节点平均代价最低的二叉查找树。具体来说就是：给定键值序列K = ，k1 < k2 <.. < kn，其中键值ki,被查找的概率为pi，要求以这些键值构建一颗二叉查找树T，使得查找的期望代价最低（查找代价为检查的节点数）。下面是对于查找期望代价的解释：对于键值ki, 如果其在构造的二叉查找树里的深度（离开树根的分支数）为depthT(ki)，则搜索该键值的代价= depthT(ki) +1（需要加上深度为0的树根节点）。由于每个键值被查找的概率分别为pi，i=1,2,3…,n。所以查找期望代价为： E[T的查找代价] = ∑i=1~n(depthT(ki) +1)*pi 时间复杂度 1、穷举穷举构造最优二叉查找树，其实就是这样的一个问题：给一个拥有n个数的已排序的节点，可以将其构造成多少种不同的BST（用来找到一个最优的二叉查找树）？设可以构造成T(n)个，那么枚举每一个元素作为根节点的情况，当第一个元素作为根节点时，其余n-1个构成右子树，无左子树，是n-1情况时的子问题，共T(n-1)种；当第二个元素作为根节点时，左子树有1个元素，右子树有n-2个元素，根据乘法原理共有T(1)T(n-2)种情况……依此类推得到：T(n)= (0)T(n-1)+T(1)T(n-2)+T(2)T(n-3)+ ......+T(n-2)T(1)+T(n-1)T(0)；此外，有T(0)=T(1)=1。下面来求解T(n)：定义函数f(x) = T(0) + T(1)*x + T(2)*x2 + ...... 那么有： f(x)2 = (T(0)2) + (T(0)T(1) + T(1)T(0)) · x + (T(0)T(2) + T(1)T(1) + T(2)T(0)) · x2 + ......

二叉搜索树

二叉搜索树锁定本词条由“科普中国”百科科学词条编写与应用工作项目审核。

在二叉排序树b中查找x的过程为：若b是空树，则搜索失败，否则：若x等于b的根结点的数据域之值，则查找成功；否则：若x小于b的根结点的数据域之值，则搜索左子树；否则：查找右子树。 Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &*p){ //在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找成功，//则指针p指向该数据元素结点，并返回TRUE，否则指针指向查找路径上访问的最后//一个结点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL if(!T){ p=f; return FALSE;} //查找不成功 else if EQ(key, T->data.key) {P=T; return TRUE;} //查找成功 else if LT(key,T->data.key) return SearchBST(T->lchild, key, T, p); //在左子树中继续查找 else return SearchBST(T->rchild, key, T, p); //在右子树中继续查找 pascal语言实现 type Link = ^tree; Tree = record D :longint; Left :link; Right :link; End; function search(n :longint;t :link):boolean; Begin If t^.d < n then begin If t^.right = nil then exit(false) else exit(search(n,t^.right)); End; If t^.d > n then begin If t^.left = nil then exit(false) else exit(search(n,t^.left)); End; Exit(true); End; 插入算法向一个二叉排序树b中插入一个结点s的算法，过程为：若b是空树，则将s所指结点作为根结点插入，否则：若s->data等于b的根结点的数据域之值，则返回，否则：若s->data小于b的根结点的数据域之值，则把s所指结点插入到左子树中，否则：把s所指结点插入到右子树中。

数据结构课程设计排序二叉树

学号数据结构课程设计设计说明书排序二叉树的遍历起止日期：2011 年12月12日至2011 年12月16日学生姓名班级成绩指导教师(签字) 电子与信息工程系 2011年12月16日

天津城市建设学院课程设计任务书 2011 —2012 学年第二学期电子与信息工程系软件工程专业班级课程设计名称：数据结构课程设计设计题目：排序二叉树的遍历完成期限：自2011 年12月12 日至2011 年12月16 日共 1 周设计依据、要求及主要内容（可另加附页）：一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计要求（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；（4）认真编写课程设计报告。三、设计内容排序二叉树的遍历（用递归或非递归的方法都可以） 1)问题描述输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。 2)基本要求 (1)用菜单实现

(2)能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列和叶子结点的数目。四、参考文献 1．王红梅．数据结构．清华大学出版社 2．王红梅．数据结构学习辅导与实验指导．清华大学出版社 3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社指导教师（签字）：教研室主任（签字）：批准日期： 2011 年 12 月 17 日主要内容：一、需求分析：输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。我自己的思想：首先设想把源程序分成头文件，调用和主函数三部分。在头文件中申明类和定义结构体，把先序，中序，后序，层次和叶子节点数的函数定义在类中。然后在调用文件中，把几个函数的实现定义写在里面。最后在主函数中把输出结果以菜单的样式输出来的方式写完主函数程序。实现的过程是先想好自己要输入的是什么，然后通过输入节点制，判断其是否是满足前序遍历，满足则可以实现下后面的功能。二、问题求解：现实中的问题：给同学排队问题。层次是从头开始每一层一层的排，然后分别记号码。前序是先从最上面的那一个开始往左手边开始排，排之前先计算好人数，然后开始排，排玩左边排右边。中序是先从最左边开始，然后左斜上角，然后右下角，再左斜上角，直到最上层为止，然后安这个顺序继续排右边的。后序是先从最左边开始的，左边的一次排过来，然后直接排右边的，也是安依次的顺序，最后才是最上层的。