c++二叉树的各种操作
程序员文章站
2022-06-24 20:40:44
头文件
#ifndef _binarytree_h_
#define _binarytree_h_
const int maxsize = 100;
template...
头文件
#ifndef _binarytree_h_ #define _binarytree_h_ const int maxsize = 100; template struct btnode { t data; btnode *lchild; btnode *rchild; }; template class binarytree { public: binarytree(); //构造函数 ~binarytree(); //析构函数 void preorder(){preorder(r);} //递归前序遍历 void inorder(){inorder(r);} //递归中序遍历 void postorder(){postorder1(r);} //递归后序遍历 void preorder1(){preorder1(r);} //非递归前序遍历 void inorder1(){inorder1(r);} //非递归中序遍历 void postorder1(){postorder(r);} //非递归后序遍历 void levelorder(){levelorder(r);}//层序遍历 btnode* findnode(t x){findnode(r,x);}//查找结点 int btnodeheigth(){btnodeheigth(r);}//树的高度 int nodecount1(){nodecount1(r);} //基于前序遍历求结点个数 int nodecount2(){nodecount2(r);} //基于中序遍历求结点个数 int nodecount3(){nodecount3(r);} //基于后序遍历求结点个数 int nodecount4(){nodecount4(r);} //递归求结点个数 void displeaf(){displeaf(r);} //输出树的叶子结点 void printroutelength(){printleavesdepth(r, 0);}//输出树的叶子结点到根结点的路径长度 bool printancestor(t x){printancestor(r,x);} //输出值为x的结点的祖先结点 private: btnode *r; btnode* createtree(btnode *t);//构造函数调用 void destroytree(btnode *t); //析构函数调用 void preorder(btnode *t); //递归前序遍历调用 void inorder(btnode *t); //递归中序遍历调用 void postorder(btnode *t); //递归后序遍历调用 void preorder1(btnode *t); //非递归前序遍历调用 void inorder1(btnode *t); //非递归中序遍历调用 void postorder1(btnode *t); //非递归后序遍历调用 void levelorder(btnode *t); //层序遍历调用 btnode* findnode(btnode *t, t x); int btnodeheigth(btnode *t); int nodecount1(btnode *t); //前序遍历求结点个数调用 int nodecount2(btnode *t); //中序遍历求结点个数调用 int nodecount3(btnode *t); //后序遍历求结点个数调用 int nodecount4(btnode *t); //递归求结点个数调用 void displeaf(btnode *t); void printleavesdepth(btnode *t,int depth); bool printancestor(btnode *t,t x); }; // template binarytree::binarytree() { r = createtree(r); } // template binarytree::~binarytree() { destroytree(r); } // template void binarytree::destroytree(btnode *t) { if(t != null) { destroytree(t->lchild); destroytree(t->rchild); delete t; } } // template btnode* binarytree::createtree(btnode *t) { t ch; std::cin>>ch; if(ch == '#') { t = null; } else { t = new btnode; t->data = ch; t->lchild = createtree(t->lchild); t->rchild = createtree(t->rchild); } return t; } // template void binarytree::preorder(btnode *t) { if(t != null) { std::cout<data<<" "; preorder(t->lchild); preorder(t->rchild); } } // template void binarytree::inorder(btnode *t) { if(t != null) { inorder(t->lchild); std::cout<data<<" "; inorder(t->rchild); } } // template void binarytree::postorder(btnode *t) { if(t != null) { postorder(t->lchild); postorder(t->rchild); std::cout<data<<" "; } } // template btnode* binarytree::findnode(btnode *t,t x) { btnode *p; if(t == null) { return null; } else if(t->data == x) { return t; } else { p = findnode(t->lchild,x); if(p != null) { return p; } return findnode(t->rchild,x); } } // template int binarytree::btnodeheigth(btnode *t) { int lchildh,rchildh; if(t == null) { return 0; } else { lchildh = btnodeheigth(t->lchild); rchildh = btnodeheigth(t->rchild); return (lchildh > rchildh)?(lchildh + 1):(rchildh + 1); } } // template int binarytree::nodecount4(btnode *t) { if(t == null) { return 0; } else { return (nodecount4(t->lchild) + nodecount4(t->rchild) + 1); } } // template int binarytree::nodecount1(btnode *t) { int m,n,k; if(t != null) { m = nodecount1(t->lchild); k = 1; n = nodecount1(t->rchild); return m + n + k; } return 0; } // template int binarytree::nodecount2(btnode *t) { int m,n,k; if(t != null) { m = nodecount2(t->lchild); n = nodecount2(t->rchild); k = 1; return m + n + k; } return 0; } // template int binarytree::nodecount3(btnode *t) { int m,n,k; if(t != null) { k = 1; m = nodecount3(t->lchild); n = nodecount3(t->rchild); return m + n + k; } return 0; } // template void binarytree::displeaf(btnode *t) { if(t != null) { if((t->lchild == null)&&(t->rchild == null)) { std::cout<data<<" "; } displeaf(t->lchild); displeaf(t->rchild); } } // template //输出路径长度 void binarytree::printleavesdepth(btnode *t, int depth) { if (t == null) return; if (t->lchild == null && t->rchild == null) { std::cout<data<<": "<lchild, depth+1); printleavesdepth(t->rchild, depth+1); } } // template bool binarytree::printancestor(btnode *t, t x) { if(t == null) { return false; } if((t->lchild != null)&&(t->lchild->data == x)) { std::cout<data<<" "; return true; } if((t->rchild != null)&&(t->rchild->data == x)) { std::cout<data<<" "; return true; } if((printancestor(t->lchild,x))||(printancestor(t->rchild,x))) { std::cout<data<<" "; return true; } return false; } // template void binarytree::preorder1(btnode *t) { btnode *st[maxsize]; int top = -1; btnode *p; top++; st[top] = t; //将根结点入栈 while(top != -1) //栈非空 { p = st[top]; top--; std::cout<data<<" "; if(p->rchild != null) //右孩子先进栈 { top++; st[top] = p->rchild; } if(p->lchild != null) //左孩子再进栈 { top++; st[top] = p->lchild; } } } //中序遍历非递归算法 template void binarytree::inorder1(btnode *t) { btnode *st[maxsize]; btnode *p; int top = -1; p = t; while((top != -1)||(p!=null)) //栈不空或p不为空时 { while(p != null) //扫描所有左结点并进栈 { top++; st[top] = p; p = p->lchild; } if(top > -1) //若栈不为空 { p = st[top]; top--; std::cout< data<<" "; p = p->rchild; //转向处理右子树 } } } // template void binarytree::postorder1(btnode *t) { btnode *st[maxsize],*p,*q; p = t; int top = -1; bool flag; do { while(p != null) //将p结点及所有的左下结点进栈 { top++; st[top] = p; p = p->lchild; } q = null; //q指向栈顶结点的前一个已经访问的结点 flag =true; //表示p结点的左子树已经遍历完 while((top != -1)&&(flag == true))//若p结点及其右子树已访问或为空 { p = st[top]; if(p->rchild == q) { std::cout<data<<" "; top--; q = p; } else { p = p->rchild; flag = false; } } } while(top != -1); } // template void binarytree::levelorder(btnode *t) { btnode *qu[maxsize],*p; int front = 0, rear = 0; rear++; qu[rear] = t; while(front != rear) //队列不为空 { front = (front + 1) % maxsize; p = qu[front]; std::cout< data<<" "; if(p->lchild != null) { rear = (rear + 1) % maxsize; qu[rear] = p->lchild; } if(p->rchild != null) { rear = (rear + 1) % maxsize; qu[rear] = p->rchild; } } } #endif // _binaryree_h_
源文件
#include #include "binarytree.h" using namespace std; int main() { binarytree a; cout<<"前序遍历: "; a.preorder(); cout<