tree.h
#ifndef TREE_H #define TREE_H #include <assert.h> typedef int element; /*定义二叉树*/ typedef struct Node{ element data; Node* leftChild; Node* rightChild; }TreeNode; void PreOrder(TreeNode *root);//递归前序遍历 void InOrder(TreeNode *root);//递归中序遍历 void PostOrder(TreeNode *root);//递归后序遍历 void IterationPreOrder(TreeNode *root);//迭代前序遍历 void IterationInOrder(TreeNode *root);//迭代中序遍历 void IterationPostOrder(TreeNode *root);//迭代后序遍历(方法一):具体思路见cpp中解释 void IterationPostOrder2(TreeNode *root);//迭代后序遍历(方法二) void IterationPostOrder3(TreeNode *root);//迭代后序遍历(方法三,设置标志位) void LevelOrder(TreeNode *root);//层序遍历 int PrintTreeAtLevel(TreeNode *root,int level);//打印树的第level(根节点为第0层)层所有结点,成功返回1 int TreeDepth(TreeNode *root);//返回二叉树的深度,空树深度为0; void ReleaseTree(TreeNode* root);//递归释放整个树 //void PrintTreeBYLevel(TreeNode *root);//按层序遍历,每层之后 /*B树的查找,查找成功返回1,查找失败返回0,类似于二分查找分为递归和非递归*/ int SearchBiTree(TreeNode *root, element key);//非递归 int SearchBiTree2(TreeNode *root, element key);//递归 //查找B树最小结点 TreeNode * BiTreeMinimum(TreeNode *root); //查找B树最大结点 TreeNode* BiTreeMaximum(TreeNode *root); /*在B树root中查找元素item是否存在,若存在返回0,若不存在, 把item结点插入到当前结点的左指针或右指针上,并返回1*/ int InsertBiTree(TreeNode ** root,element item); //B树的删除操作 void DeleteBitree(TreeNode* root,element key); bool DeleteBST(TreeNode *root, element key); bool Delete(TreeNode* p); //★★★★★★★递归的本质是编译器生成一个函数调用的栈 #endif
Tree.cpp
#include <iostream> #include <stack> #include <queue> using namespace std; #include "Tree.h" int SearchBiTree(TreeNode *root, element key) { //非递归调用 TreeNode* p=root; if(p==NULL) return 0;//空树返回0 while(p!=NULL) { if(p->data == key) { return 1; }else if(p->data < key){ p=p->rightChild; }else{ p=p->leftChild; } } return 0; } int SearchBiTree2(TreeNode *root, element key) { //递归调用 //《编程之美》p242 关于递归用法的3点注意 TreeNode* p=root; if(p==NULL) return 0;//空树返回0 if(p->data == key) { return 1; }else if(p->data < key){ return SearchBiTree(p->rightChild, key); }else{ return SearchBiTree(p->leftChild, key); } } TreeNode * BiTreeMinimum(TreeNode *root) { TreeNode* p=root; while(p->leftChild != NULL) p = p->leftChild; return p; } TreeNode* BiTreeMaximum(TreeNode *root) { TreeNode* p=root; while(p->rightChild != NULL) p = p->rightChild; return p; } int InsertBiTree(TreeNode ** root,element item) { TreeNode* current = *root;// TreeNode* parent=NULL; TreeNode* p; //查找 while(current!=NULL) { if(current->data == item) { return 0;//查找到则返回0 } parent =current;//记录查找到的最后结点,新结点作为该结点的儿子结点 if(current->data < item){ current=current->rightChild; }else{ current=current->leftChild; } } //查找失败,插入 p=(TreeNode*)malloc(sizeof(TreeNode));//无free if(p==NULL){//空间不足 exit(0); } p->data=item; p->leftChild=NULL; p->rightChild=NULL; if(parent==NULL) *root = p; else if(parent->data > item){ parent->leftChild = p; }else{ parent->rightChild = p; } return 1; } void DeleteBitree(TreeNode* root,element key)//测试有误 { TreeNode* p=root; if(p==NULL) { return ; } if(p->data > key) DeleteBitree(p->leftChild,key); else if(p->data < key) DeleteBitree(p->rightChild,key); else{ if(p->leftChild != NULL && p->rightChild!=NULL) { //p->data=BiTreeMaximum(p->leftChild)->data; //DeleteBitree(p->leftChild,p->data); /**或者*/ p->data=BiTreeMinimum(p->rightChild)->data; DeleteBitree(p->rightChild,p->data); }else{ TreeNode* t=p; p= (p->leftChild != NULL) ? p->leftChild : p->rightChild; delete t; } } } void PreOrder(TreeNode *root) { if(root != NULL) { std::cout << root->data << ","; PreOrder(root->leftChild); PreOrder(root->rightChild); } } void InOrder(TreeNode *root) { if(root != NULL) { InOrder(root->leftChild); std::cout << root->data << ","; InOrder(root->rightChild); } } void PostOrder(TreeNode *root) { if(root != NULL) { PostOrder(root->leftChild); PostOrder(root->rightChild); std::cout << root->data << ","; } } void IterationPreOrder(TreeNode *root) { stack<TreeNode*> stk; TreeNode* p= root; if(p != NULL) stk.push(p); while(!stk.empty())//栈不为空 { p=stk.top(); stk.pop(); cout << p->data << ","; if(p->rightChild != NULL) stk.push(p->rightChild); if(p->leftChild != NULL) stk.push(p->leftChild); } } void IterationInOrder(TreeNode *root) { stack<TreeNode*> stk; TreeNode* p= root; while(true) { while(p != NULL) { stk.push(p); p=p->leftChild; } if(!stk.empty())//栈不为空 { p=stk.top(); stk.pop(); if(p == NULL) break; cout << p->data << ","; p=p->rightChild; }else{ break; } } } void IterationPostOrder(TreeNode *root)//继续学习 { /* 要保证根结点在左孩子和右孩子访问之后才能访问,因此对于任一结点P,先将其入栈。 如果P不存在左孩子和右孩子,则可以直接访问它;或者P存在左孩子或者右孩子,但是其左孩子和右孩子都已被访问过了,则同样可以直接访问该结点。 若非上述两种情况,则将P的右孩子和左孩子依次入栈, 这样就保证了每次取栈顶元素的时候,左孩子在右孩子前面被访问,左孩子和右孩子都在根结点前面被访问。 */ stack<TreeNode*> stk; TreeNode *cur; //当前结点 TreeNode *pre=NULL; //前一次访问的结点 stk.push(root); while(!stk.empty()) { cur=stk.top(); if((cur->leftChild==NULL&&cur->rightChild==NULL)|| (pre!=NULL&&(pre==cur->leftChild||pre==cur->rightChild))) { cout<<cur->data<<" "; //如果当前结点没有孩子结点或者孩子节点都已被访问过 stk.pop(); pre=cur; } else { if(cur->rightChild!=NULL) stk.push(cur->rightChild); if(cur->leftChild!=NULL) stk.push(cur->leftChild); } } } void IterationPostOrder2(TreeNode *root)//继续学习 { stack<TreeNode*> stk; TreeNode* p= root; TreeNode* pre= NULL;//pre表示最近一次访问的结点 while(p||!stk.empty()) { if(p) { stk.push(p); p=p->leftChild; }else{ p=stk.top(); if(p->rightChild && p->rightChild!=pre) { p = p->rightChild; stk.push(p); p = p->leftChild; }else { stk.pop(); cout<<p->data<<","; pre = p; p = NULL; } } } } void IterationPostOrder3(TreeNode *root)//设置标志位 { } void LevelOrder(TreeNode *root) { queue<TreeNode*> que;//队列 TreeNode* p=root; if(p != NULL) { que.push(p); } while(!que.empty()) { p=que.front(); que.pop();//不要忘记删除栈顶元素 cout << p->data << ","; if(p->leftChild != NULL) que.push(p->leftChild); if(p->rightChild != NULL) que.push(p->rightChild); } } int PrintTreeAtLevel(TreeNode *root,int level) { TreeNode* p=root; if(p == NULL || level < 0) return 0; if(level==0) { cout << p->data << ","; } return PrintTreeAtLevel(p->leftChild,level-1) + PrintTreeAtLevel(p->rightChild,level-1); } int TreeDepth(TreeNode *root) { TreeNode* p=root; if(p==NULL) return 0; return TreeDepth(p->leftChild)>TreeDepth(p->rightChild) ? TreeDepth(p->leftChild)+1:TreeDepth(p->rightChild)+1; } void ReleaseTree(TreeNode* root) {//before free root,must free root->left and root->right //所以这是一种后序遍历 if(root != NULL) { ReleaseTree(root->leftChild); ReleaseTree(root->rightChild); free(root); root=NULL; } } bool DeleteBST(TreeNode *root, element key){ //若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素,并返回 //TRUE;否则返回FALSE if(root==NULL) return false; //不存在关键字等于key的数据元素 else{ if(key == root->data) { // 找到关键字等于key的数据元素 return Delete(root); } else if(key < root->data) return DeleteBST(root->leftChild, key); else return DeleteBST(root->rightChild, key); } } bool Delete(TreeNode* p) { TreeNode* q; TreeNode* s; //从二叉排序树中删除结点p,并重接它的左或右子树 if(p->rightChild == NULL){ //右子树空则只需重接它的左子树 q=p; p=p->leftChild; delete q; } else if(p->leftChild == NULL){ //左子树空只需重接它的右子树 q=p; p=p->rightChild; delete q; } else{ //左右子树均不空 q=p; s=p->leftChild; while(s->rightChild){ //转左,然后向右到尽头,找到左子树中最大元素,记录为s,q为s的父节点 q=s; s=s->rightChild; } p->data = s->data; //s指向被删结点的“前驱” /*s->rightChild为空,s->leftChild可能为空也可能不为空, p=q说明s是p(即q)的左子节点,q->leftChild = s->leftChild; p!=q说明s是q的右子节点,q->rightChild = s->leftChild; */ if(q!=p) q->rightChild = s->leftChild; //重接*q的右子树,q为s的父节点 else q->leftChild = s->leftChild; //重接*q的左子树,q为s的父节点 delete s; } return true; }