1、二叉树的遍历
为什么要有遍历操作:将线性结构-------->非线性结构;
将递归程序-------->非递归程序;
2、二叉树的三种递归遍历:
先序遍历:先访问根(父)结点,在访问左分支,最后访问右分支;
中序遍历:先访问左分支,在根结点,最后右分支;
后序遍历:先访问左分支,在访问右分支,最后访问根节点;
所有程序皆正确测试过,后面将给完整程序和测试程序,测试结果。
以下就是递归遍历,先序,中序,后序:
下面的都是在类外定义的函数,所以为模板函数:
//先序遍历
template<typename Type>
void BinTree<Type>::prevOrder(BinTreeNode<Type> *t)const{
if(t == NULL){
return;
}else{
cout<<t->data<<" ";
prevOrder(t->leftChild);
prevOrder(t->rightChild);
}
}
//中序遍历
template<typename Type>
void BinTree<Type>::inOrder(BinTreeNode<Type> *t)const{
if(t == NULL){
return;
}else{
inOrder(t->leftChild);
cout<<t->data<<" ";
inOrder(t->rightChild);
}
}
//后序遍历
template<typename Type>
void BinTree<Type>::endOrder(BinTreeNode<Type> *t)const{
if(t == NULL){
return;
}else{
endOrder(t->leftChild);
endOrder(t->rightChild);
cout<<t->data<<" ";
}
}
3、二叉树的4种非递归遍历
(1)、深度优先用栈
先序的非递归遍历:栈先入后出,根结点入栈,栈不空,出栈访问,此时将右孩子入栈,在将左孩子入栈,栈不空,出栈访问,就是循环了;
代码如下:
template<typename Type>
void BinTree<Type>::prevOrder_1(BinTreeNode<Type>* t)const{
stack<BinTreeNode<Type> *> st; //栈里面放的是指向节点的指针
BinTreeNode<Type> *tmp;
if(t != NULL){ //根不为空
st.push(t); //根入栈
while(!st.empty()){ //栈非空
tmp = st.top(); //读栈顶元素
st.pop(); //出栈
cout<<tmp->data<<" "; //访问
if(tmp->rightChild){ //右孩子存在
st.push(tmp->rightChild); //入栈
}
if(tmp->leftChild){ //左孩子存在
st.push(tmp->leftChild); //入栈
}
}
}
}
中序的非递归遍历:就是先把根及左分支一直压栈,栈不空,出栈访问,再看右孩子,有的话,压栈,结束条件想清楚就行。
代码如下:
template<typename Type>
void BinTree<Type>::inOrder_1(BinTreeNode<Type>* t)const{
stack<BinTreeNode<Type> *> st; //栈里面放的是指向节点的指针
BinTreeNode<Type> *p = t;
//用的是do while()循环
do{
while(p != NULL){ //将根和左子树一直入栈
st.push(p);
p = p->leftChild;
}
if(!st.empty()){ //栈不空,
p = st.top(); //读栈顶元素
st.pop(); //出栈
cout<<p->data<<" "; //访问
p = p->rightChild; //此时往刚才栈顶元素的右孩子走;
} //中序遍历时,当root出栈时,此时栈空,没有p!=NULL的话,将出错。
}while(p != NULL || !st.empty()); //为根的时候右边还要入栈。
}
后序的非递归遍历:思想就是要有一个标志,当为右边回来的时候才能访问根节点!!!
代码如下:
typedef enum{L, R}Tag; //枚举定义新的类型
template<typename Type> //定义一个类,为的是做标志
class stkNode{
public:
stkNode(BinTreeNode<Type> *p = NULL) : ptr(p), tag(L){}
public: //数据成员为公有,便于访问
BinTreeNode<Type> *ptr;
Tag tag; //L R
};
template<typename Type>
void BinTree<Type>::endOrder_1(BinTreeNode<Type>* t)const{
stkNode<Type> n;
stack<stkNode<Type>> st; //此时栈中存放的是对象!
BinTreeNode<Type> *p = t;
do{
while(p != NULL){ //不为空,一路向左入栈
n.ptr = p; //将指针给过去
n.tar = L; //记为左边入栈
st.push(n);
p = p->leftChild;
}
bool isRun = true; //是否继续的标志
while(isRun && !st.empty()){
n = st.top(); //读栈顶
st.pop(); //出栈
switch(n.tag){ //根据L和R选择
case L:
p = n.ptr;
n.tag = R; //更改为R
st.push(n); //压入栈
p = p->rightChild; //看有没有右孩子,有的话,结束循环,要入栈的;
isRun = false; //特别重要,保证了右孩子的入栈!
break;
case R:
cout<<n.ptr->data<<" ";
break;
}
}
}while(!st.empty());//不用p1=NULL,因为当栈空时,最后一个节点刚好被访问完成。
}
画图跟踪后序如下:
(2)、广度优先用队列
层次遍历:根结点入队列,队列非空,出队访问,在将左右孩子入队,非空,访问,构成循环;
代码如下:
template<typename Type>
void BinTree<Type>::levelOrder(BinTreeNode<Type>* t)const{
queue<BinTreeNode<Type> *> qu; //队列里面放的是指向节点的指针
BinTreeNode<Type> *p;
if(t != NULL){ //根非空
qu.push(t); //根入队
while(!qu.empty()){ //队列非空
p = qu.front(); //读队首
qu.pop(); //出队
cout<<p->data<<" "; //访问
if(p->leftChild){ //左孩子存在
qu.push(p->leftChild); //入队
}
if(p->rightChild){ //右孩子存在
qu.push(p->rightChild); //入队
}
}
}
}
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。