二叉树 与 二叉搜索树
指针与引用：
1） int count = 18；
int* ptr = &count;
2) int count = 18;
int& pcount = count;
创建二叉树与创建二叉搜索树
前者：只是为了熟悉课本知识
后者：具有实际应用的功能
*** 比较两者之间的区别，并且考虑是否可以相互转化，为什么??
创建二叉树：
1） 创建二叉树
2） 层次遍历
3） 前序遍历
4） 中序遍历
5） 后续遍历
6） 统计叶子节点
7） 统计节点数
8） 树的深度
9） 销毁二叉树
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：还有老多不理解的地方，指针真难，后期跟进！！
二叉树与二叉搜索树指针与引用1intcount18intptrampcount2intcount18intamppcountcou…
一二叉树的性质性质1二叉树的第i层上至多有2i1i1个结点用数学归纳法证明推广k叉树或度为k的树的第i层上至多有ki1i1个结点性…
一二叉树的性质性质1二叉树的第i层上至多有2i1i1个结点用数学归纳法证明推广k叉树或度为k的树的第i层上至多有ki1i1个结点性…
includequotmallochquotdefineNULL0includequotstdiohquottypedefstructnodechar…
甘肃政法学院数据结构课程设计题目二叉树遍历计算机科学学院信息管理与信息系统专业09级信息管理与信息系统班学号20xx81020xx…
摘要二叉树是树形结构的一个重要的类型二叉树是nngt0个结点的有限集它或者是空集n0或者由个根结点及两棵互不相交的分别称作这个根的…
实验三二叉树的遍历一实验目的熟悉二叉树的结点类型和二叉树的基本操作掌握二叉树的前序中序和后序遍历的算法3加深对二叉树的理解逐步培养…
数据结构学习总结7二叉树Time20xx911ProgramNamecorrelativeoperationsofBTreeAut…
二叉树结点的数据结构typedefstructBiTNode树节点定义intvalueBiTNodelchildrchildBiT…
一二叉树的性质性质1二叉树的第i层上至多有2i1i1个结点用数学归纳法证明推广k叉树或度为k的树的第i层上至多有ki1i1个结点性…