二叉树 与 二叉搜索树
指针与引用：
int count = 18；
int* ptr = &count;
int count = 18;
int& pcount = count;
创建二叉树与创建二叉搜索树
前者：只是为了熟悉课本知识
后者：具有实际应用的功能
*** 比较两者之间的区别，并且考虑是否可以相互转化，为什么??
创建二叉树：
1.创建二叉树
2.层次遍历
3.前序遍历
4.中序遍历
5.后续遍历
6.统计叶子节点
7.统计节点数
8.销毁二叉树
BTTree.cpp
#include <iostream>
#include <string>
#include <queue>
using namespace std;
typedef struct BTNode{
char value;
struct BTNode * lchild, * rchild;
}btNode;
/**
* build tree
*/
void createTree(btNode* & nodePtr) {
char c;
cin>>c;
if(c != '0') {
nodePtr = new btNode();
nodePtr->value = c;
createTree(nodePtr->lchild);
createTree(nodePtr->rchild);
}
}
/**
* Traversal tree in levelorder
*/
void levelorder(btNode* nodePtr) {
queue<btNode*> myqueue;
myqueue.push(nodePtr);
while(nodePtr) {
cout<<nodePtr->value<<" ";
if(nodePtr->lchild) {
myqueue.push(nodePtr->lchild);
}
if(nodePtr->rchild) {
myqueue.push(nodePtr->rchild);
}
myqueue.pop();
nodePtr=myqueue.front();
}
while(!myqueue.empty()) {
cout<<myqueue.front()->value<<" ";
myqueue.pop();
}
}
/**
* Traversal tree in preorder
*/
void preorder(btNode* nodePtr) {
if(nodePtr != NULL) {
cout<<nodePtr->value<<endl;
preorder(nodePtr->lchild);
preorder(nodePtr->rchild);
}
}
/**
* Traversal tree in inorder
*/
void inorder(btNode* nodePtr, string preStr) {
if(nodePtr != NULL) {
inorder(nodePtr->lchild, preStr + " ");
cout<<(preStr + nodePtr->value)<<endl;
inorder(nodePtr->rchild, preStr + " ");
}
}
/**
* Traversal tree in postorder
*/
void postorder(btNode* nodePtr) {
if(nodePtr != NULL) {
postorder(nodePtr->lchild);
postorder(nodePtr->rchild);
cout<<nodePtr->value<<endl;
}
}
/**
* count the number of leaf
*/
void leafcount(btNode* nodePtr, int& count) {
if(nodePtr) {
if(nodePtr->lchild == NULL && nodePtr->rchild == NULL) count++;
leafcount(nodePtr->lchild, count);
leafcount(nodePtr->rchild, count);
}
}
/**
* count the number of node
*/
void nodecount(btNode* nodePtr, int& count) {
if(nodePtr) {
count++;
nodecount(nodePtr->lchild, count);
nodecount(nodePtr->rchild, count);
}
}
/**
* record the depth of tree
*/
void treedepth(btNode* nodePtr, int level, int& depth) {
if(nodePtr) {
if(nodePtr->lchild == NULL && nodePtr->rchild == NULL)
if(level > depth) depth = level;
treedepth(nodePtr->lchild, level+1, depth);
treedepth(nodePtr->rchild, level+1, depth);
}
}
/**
* destroy the tree
*/
void destroytree(btNode* nodePtr) {
if(nodePtr) {
destroytree(nodePtr->lchild);
destroytree(nodePtr->rchild);
cout<<"I am free : "<<nodePtr->value<<endl;
delete(nodePtr);
}
}
int main() {
btNode* root;
// init root and build tree
createTree(root);
//levelorder(root);
//preorder(root);
//inorder(root,"");
//postorder(root);
//int count=0; // the number of leaf
//leafcount(root, count);
//cout<<"The number of leaf is : "<<count<<endl;
//int count=0;
//nodecount(root, count);
//cout<<"The number of node is : "<<count<<endl;
//int depth=0;
//treedepth(root, 0, depth);
//cout<<"The depth of tree is : "<<depth<<endl;
destroytree(root);
return 0;
}
创建二叉搜索树
1.添加节点
2.显示树
3.删除节点
4.各种工具函数
BSTTree.cpp
#include <iostream>
using namespace std;
enum ORDER_MODE
{
ORDER_MODE_PREV = 0,
ORDER_MODE_MID,
ORDER_MODE_POST
};
template <class T>
struct BinaryNode
{
T element;
BinaryNode *left;
BinaryNode *right;
BinaryNode(const T& theElement,
BinaryNode *lt,
BinaryNode *rt):
element(theElement),
left(lt),
right(rt)
{
}
};
template <class T>
class BinarySearchTree
{
private:
BinaryNode<T> *m_root;
public:
BinarySearchTree();
BinarySearchTree(const BinarySearchTree& rhs);
~BinarySearchTree();
const T& findMin() const;
const T& findMax() const;
bool contains(const T& x) const;
void printTree(ORDER_MODE eOrderMode = ORDER_MODE_PREV) const;
void makeEmpty();
void insert(const T& x);
void remove(const T& x);
private:
//因为树的方法用到了很多递归， 所以这里我们需要申明如下的私有成员函数
void insert(const T& x, BinaryNode<T>* &t) ;
void remove(const T& x, BinaryNode<T>* &t) ;
BinaryNode<T>* findMin( BinaryNode<T>* t) const;
BinaryNode<T>* findMax( BinaryNode<T>* t) const;
bool contains(const T& x, const BinaryNode<T>* t) const;
void makeEmpty(BinaryNode<T>* &t);
void printTreeInPrev(BinaryNode<T>* t) const;
void printTreeInMid(BinaryNode<T>* t)const;
void printTreeInPost(BinaryNode<T>* t)const;
};
template <class T>
BinarySearchTree<T>::BinarySearchTree()
{
m_root = NULL;
}
template <class T>
BinarySearchTree<T>:: BinarySearchTree(const BinarySearchTree& rhs)
{
m_root = rhs.m_root;
}
template <class T>
BinarySearchTree<T>:: ~BinarySearchTree()
{
makeEmpty();
}
// return true if the x is found in the tree
template <class T>
bool BinarySearchTree<T>::contains(const T& x) const
{
return contains(x, m_root);
}
template <class T>
bool BinarySearchTree<T>::contains(const T& x, const BinaryNode<T>* t) const
{
if (!t)
return false;
else if (x < t->element)
return contains(x, t->left);
else if (x > t->element)
return contains(x, t->right);
else
return true;
}
// find the min value in the tree
template <class T>
const T& BinarySearchTree<T>::findMin() const
{
return findMin(m_root)->element;
}
template <class T>
BinaryNode<T>* BinarySearchTree<T>::findMin( BinaryNode<T>* t) const
{
//二叉树的一个特点就是左子叶的值比根节点小， 右子叶的比根节点的大
if (!t)
return NULL;
if (t->left == NULL)
return t;
else
return findMin(t->left);
}
// find the max value in the tree
template <class T>
const T& BinarySearchTree<T>::findMax() const
{
return findMax(m_root)->element;
}
template <class T>
BinaryNode<T>* BinarySearchTree<T>::findMax( BinaryNode<T>* t) const
{
//二叉树的一个特点就是左子叶的值比根节点小， 右子叶的比根节点的大
if (t != NULL)
while (t->right != NULL)
t = t->right;
return t;
}
//insert an element into tree
template <class T>
void BinarySearchTree<T>:: insert(const T& x)
{
insert(x, m_root);
}
template <class T>
void BinarySearchTree<T>::insert(const T& x, BinaryNode<T>* &t)
{
if (t == NULL)
t = new BinaryNode<T>(x, NULL, NULL);//注意这个指针参数是引用
else if (x < t->element)
insert(x, t->left);
else if (x > t->element)
insert(x, t->right);
else
;//do nothing
}
//remove a element int a tree
template <class T>
void BinarySearchTree<T>::remove(const T& x)
{
return remove(x, m_root);
}
template <class T>
void BinarySearchTree<T>::remove(const T& x, BinaryNode<T>* &t)
{
if (t == NULL)
return;
if (x < t->element)
remove(x, t->left);
else if (x > t->element)
remove (x, t->right);
else // now ==
{
if (t->left != NULL &&
t->right != NULL)//two child
{
t->element = findMin(t->right)->element;
remove(t->element, t->right);
}
else
{
BinaryNode<T> *oldNode = t;
t = (t->left != NULL) ? t->left : t->right;
delete oldNode;
}
}
}
template <class T>
void BinarySearchTree<T>::makeEmpty()
{
makeEmpty(m_root);
}
template <class T>
void BinarySearchTree<T>::makeEmpty(BinaryNode<T>* &t)
{
if (t)
{
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
t = NULL;
}
//Print tree
template <class T>
void BinarySearchTree<T>::printTree(ORDER_MODE eOrderMode /*= ORDER_MODE_PREV*/) const
{
if (ORDER_MODE_PREV == eOrderMode)
printTreeInPrev(m_root);
else if (ORDER_MODE_MID == eOrderMode)
printTreeInMid(m_root);
else if (ORDER_MODE_POST == eOrderMode)
printTreeInPost(m_root);
else
;//do nothing
}
template <class T>
void BinarySearchTree<T>::printTreeInPrev(BinaryNode<T>* t) const
{
if (t)
{
cout << t->element;
printTreeInPrev(t->left);
printTreeInPrev(t->right);
}
}
template <class T>
void BinarySearchTree<T>::printTreeInMid(BinaryNode<T>* t) const
{
if (t)
{
printTreeInPrev(t->left);
cout << t->element;
printTreeInPrev(t->right);
}
}
template <class T>
void BinarySearchTree<T>::printTreeInPost(BinaryNode<T>* t) const
{
if (t)
{
printTreeInPost(t->left);
printTreeInPost(t->right);
cout << t->element;
}
}
int main() {
BinarySearchTree<int> bst;
bst.insert(5);
bst.insert(6);
bst.insert(7);
bst.insert(9);
bst.insert(4);
bst.printTree();
bst.remove(7);
bst.printTree();
return 0;
}
二叉搜索树总结：
1.这里x最好声明为const T& x,涉及到递归，值传递浪费空间，引用同时声明为常量
2.修改树的结构时一般都是引用，是不是在递归一般都这样呢？？
3. remove 的辅助函数findMin 这里可以不用通过递归，所以可以不需要在public弄一个接口但是这里还是需要将其放到private中去，findMin目前不会单独作为一个功能提供给开发者，只是一个工具函数，放到private中去更合理
Ps：还有老多不理解的地方，指针真难，后期跟进！！
发表评论
相关推荐
二叉搜索树（Binary Search Tree，BST）是一种特殊类型的二叉树，它的每个节点都具有以下特性： 1. **左子树性质**：左子树上所有节点的值都小于当前节点的值。 2. **右子树性质**：右子树上所有节点的值都大于当前...
在算法面试中，树、二叉树以及二叉搜索树是非常关键的数据结构，它们在解决各种问题时展现出高效和灵活性。下面将详细讲解这些概念及其重要性质。 **1. 树 (Tree)** 树是一种非线性的数据结构，由一个或多个节点...
二叉搜索树是一种二叉树，其中每个节点包含一个键（key）、一个关联值、一个指向左子树的引用和一个指向右子树的引用。二叉搜索树的性质规定，对于任意节点，其左子树中的所有节点的键都小于该节点的键，而右子树中...
大连理工大学数据结构上机 二叉树三种遍历，先序和中序建立二叉树，后序和中序建立二叉树，二叉搜索树查找，删除，插入
【二叉树与二叉搜索树】 在计算机科学中，二叉树是一种特殊的树结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树经常被用于实现各种算法，如搜索、排序等。二叉搜索树（Binary Search Tree...
二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树结构，它的每个节点都具有以下特性：左子树上所有节点的值均小于当前节点的值，右子树上所有节点的值均大于当前节点的值。这种特性使得二叉搜索树在查找、...
二叉搜索树（Binary Search Tree，BST）是二叉树的一种特殊形式，它满足以下性质： 1. 对于任意节点，其左子树中的所有节点的值都小于该节点的值。 2. 对于任意节点，其右子树中的所有节点的值都大于该节点的值。 3...
在IT领域，二叉搜索树（Binary Search Tree, BST）是一种常见的数据结构，它具有左子树上所有节点的值小于根节点的值，右子树上所有节点的值大于根节点的值的特性。这样的特性使得二叉搜索树非常适合进行查找、插入...
题 目 二叉排序树与平衡二叉树的实现 1、课程设计的目的 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。 使学生掌握软件设计的基本内容...
二叉搜索树（Binary Search Tree，BST）是一种特殊类型的二叉树，它的每个节点都包含一个键（key）、一个关联的值、一个指向左子树的指针和一个指向右子树的指针。在二叉搜索树中，对于任何一个节点，其左子树中的...
最优二叉搜索树，也称为最优化二叉查找树或者动态二叉搜索树，是计算机科学中的一个重要概念，尤其在算法设计与分析领域占据一席之地。这种数据结构主要用于提高查询效率，在某些特定操作序列下，它能比普通二叉搜索...
"第六章.ppt" 文件可能包含了关于二叉树的深入理论、示例和练习，可能涵盖了二叉树的性质、查找算法、排序算法（如二叉搜索树）以及与二叉链表相关的复杂操作。例如，可能讲解了如何判断一棵二叉树是否平衡，或者...
对于二叉查找树，插入操作需要遵循上述的排序规则，搜索操作则可以通过比较目标值与当前节点值进行递归查找。删除操作相对复杂，可能需要调整节点的连接关系以保持二叉查找树的性质。 在VC++6.0环境中，你可以编译...
二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，其中每个节点的左子树只包含比它小的节点，右子树只包含比它大的节点。这种特性使得搜索、插入和删除操作的时间复杂度可以达到O(log n)。二叉搜索树的...
二叉搜索树定义： （1）若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值。 （2）若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值。 （3）它的左、右子树也分别为二叉搜索树。 ...
1.二叉搜索树的建立 2.二叉搜索树节点的查找 3.二叉搜索树节点的删除 4.二叉搜索树的中序、后序递归遍历 5.二叉搜索树的中序、后序非递归遍历 6.二叉搜索树查找某个节点的前驱（下一个值比当前节点x大的节点）
根据给定的文件信息，我们将深入探讨如何通过不同的方法来判断一棵二叉树是否为二叉排序树（Binary Search Tree, BST）。二叉排序树是一种特殊的二叉树，它满足以下条件： 1. 若左子树不为空，则左子树上所有节点的...
1.实现二叉搜索树的基本操作 2.包括建立，查找，删除，显示 3.得到最长路径和最短路径，并能分别计算长度
本实验——“数据结构二叉树实验——构造二叉搜索树”，旨在深入理解并实践二叉搜索树的构建过程和特性。 二叉搜索树是一种特殊的二叉树，每个节点都满足以下性质：左子树上的所有节点的键值小于父节点的键值；右子...
二叉搜索树（Binary Search Tree，BST），是数据结构领域中的一个重要概念，它是一种特殊的二叉树，每个节点的左子树只包含比其小的元素，而右子树则包含大于它的元素。这种特性使得二叉搜索树在查找、插入和删除...