二叉树的C++实现算法
链式存储结构来表示二叉树,每一个二叉树节点包含树节点的值、树的左孩子指针、树的右孩子指针:
class BiNode{ public: char data; struct BiNode *lchild,*rchild; };
那么对于一个二叉树来说,只需要存放指向树根节点的指针即可,另外还需要声明二叉树的一些功能,比如遍历方法、求树高等(BiTree.h):
#ifndef BITREE_H_INCLUDED #define BITREE_H_INCLUDED #include<iostream> #include<string> using namespace std; class BiNode{ public: char data; struct BiNode *lchild,*rchild; }; class BiTree{ private: BiNode * root; int height; void pre_Order(BiNode * t); void in_Order(BiNode * t); void post_Order(BiNode * t); BiNode* create(string &s ,int&pos); void get_Height(BiNode *t,int h); public: BiTree(){root=NULL;height=0;} ///按照前序遍历序列创建二叉树 void createBiTree(string s); ///前序遍历二叉树 void preOrder(); ///中序遍历二叉树 void inOrder(); ///后序遍历二叉树(递归方法) void postOrder(); ///后序遍历二叉树(使用栈的非递归方法) void postOrder1(); ///层序遍历二叉树 void levelOrder(); ///求树的高度 int getHeight(); ///求两个节点的最大公共祖先 void ancestor(char A,char B); }; #endif // BITREE_H_INCLUDED
二叉树类的成员函数定义(BiTree.cpp)
#include "BiTree.h" #include "queue" #include "stack" #include "vector" #include<iostream> using namespace std; ///递归创建二叉树,如果是#表示空节点 BiNode * BiTree::create(string &s,int &pos){ ++pos; BiNode * t; if((unsigned)pos>=s.size()) return NULL; else{ if(s[pos]=='#') t=NULL; else{ t=new BiNode; t->data=s[pos]; t->lchild=create(s,pos); t->rchild=create(s,pos); } return t; } } ///按照前序遍历序列创建二叉树 void BiTree::createBiTree(string s){ int pos = -1; root=create(s,pos); } ///前序遍历二叉树 void BiTree::preOrder(){ pre_Order(root); cout<<endl; } void BiTree::pre_Order(BiNode * t){ if(t!=NULL){ cout<<t->data<<' '; pre_Order(t->lchild); pre_Order(t->rchild); } } ///中序遍历二叉树 void BiTree::inOrder(){ in_Order(root); cout<<endl; } void BiTree::in_Order(BiNode *t){ if(t!=NULL){ in_Order(t->lchild); cout<<t->data<<' '; in_Order(t->rchild); } } ///后序遍历二叉树(递归方法) void BiTree::postOrder(){ post_Order(root); cout<<endl; } void BiTree::post_Order(BiNode *t){ if(t!=NULL){ post_Order(t->lchild); post_Order(t->rchild); cout<<t->data<<' '; } } ///后序遍历二叉树(使用栈的非递归方法) ///后续遍历先遍历左子树,再遍历右子树,最后遍历根节点 ///对于一个节点而言,先一直遍历到最左节点 ///然后用r记录右子树是否遍历,如果没有遍历,则遍历右子树 void BiTree::postOrder1(){ ///p表示当前树节点指针, ///r表示最近访问的树节点指针 BiNode *p,*r; r = NULL; p = root; stack<BiNode*> my_stack; while(p!=NULL || !my_stack.empty()){ if(p){ ///一直走到树的最左边 my_stack.push(p); p=p->lchild; } else{ p=my_stack.top(); ///如果右子树没有遍历,遍历右子树 if(p->rchild!=NULL && p->rchild!=r){ p=p->rchild; my_stack.push(p); ///注意这里需要向左转,因为如果不向左转, ///将会遍历右子树节点两边 p=p->lchild; } ///否则遍历根节点 else{ p=my_stack.top(); my_stack.pop(); cout<<p->data<<' '; ///更新最近遍历的节点 r=p; ///将遍历后的节点设为NULL,进行下一个节点的遍历 p=NULL; } } } cout<<endl; } ///使用队列进行层序遍历二叉树 void BiTree::levelOrder(){ if(root==NULL) return; queue<BiNode*> q; q.push(root); while(!q.empty()){ BiNode * t; t=q.front(); q.pop(); cout<<t->data<<' '; if(t->lchild!=NULL) q.push(t->lchild); if(t->rchild!=NULL) q.push(t->rchild); } cout<<endl; } ///求树的高度 int BiTree::getHeight(){ get_Height(root,0); return height; } void BiTree::get_Height(BiNode *t,int h){ if(t!=NULL){ ++h; if(h>height) height=h; get_Height(t->lchild,h); get_Height(t->rchild,h); } }
一般关于树的编程题适合用递归的方法来求解
测试(main.cpp)
#include <iostream> #include "BiTree.h" using namespace std; int main() { BiTree a; string s; s="ABD##E#F##C##"; a.createBiTree(s); cout<<"前序遍历:"<<endl; a.preOrder(); cout<<"中序遍历:"<<endl; a.inOrder(); cout<<"后序遍历1:"<<endl; a.postOrder(); cout<<"后序遍历2:"<<endl; a.postOrder1(); cout<<"层序遍历:"<<endl; a.levelOrder(); cout<<"树高:"<<endl; cout<<a.getHeight()<<endl; return 0; }
每一成功的背后都有个人的努力和家人的支持