二叉树总结

二叉树 与 二叉搜索树 指针与引用： 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 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 myqueue; myqueue.push(nodePtr); while(nodePtr) { coutlchild) { myqueue.push(nodePtr->lchild); } if(nodePtr->rchild) { myqueue.push(nodePtr->rchild); } myqueue.pop(); nodePtr=myqueue.front(); }

while(!myqueue.empty()) { cout

/** * Traversal tree in preorder */ void preorder(btNode* nodePtr) { if(nodePtr != NULL) { coutlchild); preorder(nodePtr->rchild); } } /** * Traversal tree in inorder */ void inorder(btNode* nodePtr, string preStr) { if(nodePtr != NULL) { inorder(nodePtr->lchild, preStr + " "); cout<<(preStr + nodePtr->value)rchild, preStr + " "); } }

/** * Traversal tree in postorder */ void postorder(btNode* nodePtr) { if(nodePtr != NULL) { postorder(nodePtr->lchild); postorder(nodePtr->rchild); cout

/** * 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 : "

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 : "

//int depth=0; //treedepth(root, 0, depth); //cout<<"The depth of tree is : "<

destroytree(root); return 0; }

创建二叉搜索树 1） 添加节点 2） 显示树 3） 删除节点 4） 各种工具函数

BSTTree.cpp #include using namespace std;

enum ORDER_MODE { ORDER_MODE_PREV = 0, ORDER_MODE_MID, ORDER_MODE_POST };

template struct BinaryNode { T element; BinaryNode *left; BinaryNode *right;

BinaryNode(const T& theElement, BinaryNode *lt, BinaryNode *rt): element(theElement), left(lt), right(rt) {

} };

template class BinarySearchTree { private:

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() {