二叉树总结.doc

二叉树 与 二叉搜索树指针与引用：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 #include #include using namespace std;typedef struct BTNodechar value;struct BTNode * lchild, * rchild;btNode;/* build tree */void createTree(btNode* & nodePtr) char c;cinc;if(c != 0) nodePtr = new btNode();nodePtr-value = c;createTree(nodePtr-lchild);createTree(nodePtr-rchild);/* Traversal tree in levelorder*/void levelorder(btNode* nodePtr) queue myqueue;myqueue.push(nodePtr);while(nodePtr) coutvaluelchild) myqueue.push(nodePtr-lchild);if(nodePtr-rchild) myqueue.push(nodePtr-rchild);myqueue.pop();nodePtr=myqueue.front();while(!myqueue.empty() coutvalue ;myqueue.pop();/* Traversal tree in preorder*/void preorder(btNode* nodePtr) if(nodePtr != NULL) coutvaluelchild);preorder(nodePtr-rchild);/* Traversal tree in inorder*/void inorder(btNode* nodePtr, string preStr) if(nodePtr != NULL) inorder(nodePtr-lchild, preStr + );coutvalue)rchild, preStr + );/* Traversal tree in postorder*/void postorder(btNode* nodePtr) if(nodePtr != NULL) postorder(nodePtr-lchild);postorder(nodePtr-rchild);coutvaluelchild = 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);coutI am free : valueendl;delete(nodePtr);int main() btNode* root;/ init root and build treecreateTree(root);/levelorder(root);/preorder(root);/inorder(root,);/postorder(root);/int count=0; / the number of leaf/leafcount(root, count);/coutThe number of leaf is : countendl;/int count=0;/nodecount(root, count);/coutThe number of node is : countendl;/int depth=0;/treedepth(root, 0, depth);/coutThe depth of tree is : depthendl;destroytree(root);return 0;创建二叉搜索树1） 添加节点2） 显示树3） 删除节点4） 各种工具函数BSTTree.cpp#include using namespace std;enum ORDER_MODEORDER_MODE_PREV = 0,ORDER_MODE_MID,ORDER_MODE_POST;template struct BinaryNodeTelement;BinaryNode*left;BinaryNode*right;BinaryNode(const T& theElement,BinaryNode *lt,BinaryNode *rt):element(theElement),left(lt),right(rt);template class BinarySearchTreeprivate:BinaryNode*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) ;void remove(const T& x, BinaryNode* &t) ;BinaryNode* findMin( BinaryNode* t) const;BinaryNode* findMax( BinaryNode* t) const;bool contains(const T& x, const BinaryNode* t) const;void makeEmpty(BinaryNode* &t);void printTreeInPrev(BinaryNode* t) const;void printTreeInMid(BinaryNode* t)const;void printTreeInPost(BinaryNode* t)const;template BinarySearchTree:BinarySearchTree()m_root = NULL;template BinarySearchTree: BinarySearchTree(const BinarySearchTree& rhs)m_root = rhs.m_root;template BinarySearchTree: BinarySearchTree()makeEmpty();/ return true if the x is found in the treetemplate bool BinarySearchTree:contains(const T& x) constreturn contains(x, m_root);template bool BinarySearchTree:contains(const T& x, const BinaryNode* t) constif (!t)return false;else if (x element)return contains(x, t-left);else if (x t-element)return contains(x, t-right);elsereturn true;/ find the min value in the treetemplate const T& BinarySearchTree:findMin() constreturn findMin(m_root)-element;template BinaryNode* BinarySearchTree:findMin( BinaryNode* t) const/二叉树的一个特点就是左子叶的值比根节点小， 右子叶的比根节点的大if (!t)return NULL;if (t-left = NULL)return t;elsereturn findMin(t-left);/ find the max value in the treetemplate const T& BinarySearchTree:findMax() constreturn findMax(m_root)-element;template BinaryNode* BinarySearchTree:findMax( BinaryNode* t) const/二叉树的一个特点就是左子叶的值比根节点小， 右子叶的比根节点的大if (t != NULL)while (t-right != NULL)t = t-right;return t;/insert an element into treetemplate void BinarySearchTree: insert(const T& x)insert(x, m_root);template void BinarySearchTree:insert(const T& x, BinaryNode* &t) if (t = NULL)t = new BinaryNode(x, NULL, NULL);/注意这个指针参数是引用else if (x element)insert(x, t-left);else if (x t-element)insert(x, t-right);else;/do nothing/remove a element int a treetemplate void BinarySearchTree:remove(const T& x)return remove(x, m_root);template void BinarySearchTree:remove(const T& x, BinaryNode* &t) if (t = NULL)return;if (x element)remove(x, t-left);else if (x t-element)remove (x, t-right);else / now =if (t-left != NULL &t-right != NULL)/two childt-element = findMin(t-right)-element;remove(t-element, t-right);elseBinaryNode *oldNode = t;t = (t-left != NULL) ? t-left : t-right;delete oldNode;template void BinarySearchTree:makeEmpty()makeEmpty(m_root);template void BinarySearchTree:makeEmpty(BinaryNode* &t)if (t)makeEmpty(t-left);makeEmpty(t-right);delete t;t = NULL;/Print treetemplate void BinarySearchTree:printTree(ORDER_MODE eOrderMode /*= ORDER_MODE_PREV*/) constif (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 nothingtemplate void BinarySearchTree:printTreeInPrev(BinaryNode* t) constif (t)cout element;printTreeInPrev(t-left);printTreeInPrev(t-rig