手机培训网站建设,个人网站建设论文绪论,线上培训平台,做门户网站用什么模板好9 二叉树的遍历 文章目录9 二叉树的遍历9.1 递归函数基础9.2 深度优先遍历的实现9.3 二叉树层次遍历9.1 递归函数基础 什么是递归#xff1f;调用自身就是叫递归#xff0c;如下所示#xff1a;
void r(){r();
}我们习惯借用阶梯图来帮助我们理解这些知识。如果是同一层函数…9 二叉树的遍历 文章目录9 二叉树的遍历9.1 递归函数基础9.2 深度优先遍历的实现9.3 二叉树层次遍历9.1 递归函数基础 什么是递归调用自身就是叫递归如下所示
void r(){r();
}我们习惯借用阶梯图来帮助我们理解这些知识。如果是同一层函数体那么习惯上在同一层阶梯中如下所示 如果是像上述的方式一样来写递归函数我们不难发现这个循环是无限的。故我们需要加一个终止条件,一般来说我们习惯将终止条件写于函数体的最开头当符合终止条件时函数遍不会继续执行如下所示
int i 0;void r()
{if(i3){i;r();}
}当同一层阶梯中有多个执行语句我们习惯用一个结点来表示它执行的效果如下所示 多个递归 在考研中一般不考查一个递归而是喜好考查多个递归在这里给出代码示例和阶梯图望仔细研究。 int i 0;
void r()
{if(i2){i;r();r();}
}9.2 深度优先遍历的实现 递归遍历
通过上面递归的学习我想我们可以看穿下面这个恐怖的遍历代码了。
void r(BTNode p)
{if(p ! nullptr){//(1)r(p-lChild);//(2)r(p-rChild);//(3)}
}对于一下这颗树来说 结合上述代码的遍历方式我们可以画出如下的阶梯图。 如果想要先序遍历结合上一讲我们讲过的原理可知遍历方式的不同在于经过第几次时去访问该元素。如果在经过第一次时就拿出结点中的元素则为先序遍历其他遍历懂得都懂这里不过多赘述不清楚的可以看看上一讲。
如果想要在代码中使用先序遍历只需要在前面的框架中将(1)替换为visit§其中visit()这个函数可以是自己写的访问结点元素的一个函数。
void r(BTNode p)
{if(p ! NULL){visit(p)r(p-rChild);//(2)r(p-lChild);//(3)}
}如果是中序则将visit()放在(2)后序则放在(3)。 先序遍历非递归
我们在栈那一讲中知道栈的作用和递归一样。故如果不想使用递归来解决遍历的话可以考虑用栈来解决这个问题。
入栈完读取数据后就可以出栈。左右孩子入栈时遵循先右后左这是因为栈是后入先出只有先右后左出栈时才能先左后右。如下 我们定义一个栈。则出入栈顺序应该是
1入栈1读取数据发现两个孩子结点1出栈先右后左则3进栈后2进栈而后读2发现有孩子故2出栈5入栈后4入栈读取4发现4没有孩子4出栈而后5在栈顶读取55没有孩子5出栈而后是3读取3其有孩子3出栈7入栈后6入栈读取6有孩子6出栈8入栈8读取后没有孩子8出栈栈顶为7读取7其无孩子7出栈。至此先序遍历结束。
我们来看看代码的实现
void preorderNonrecursion(BTNode *bt)
{if(bt! NULL){BTNode * Stack[maxSize];//定义顺序栈int top -1;//定义栈顶指针BTNode *p NULL;//定义遍历指针Stack[top] bt;//根节点入栈while(top ! -1){p Stack[top--];Visit(p);//取元素if(p-rChild ! NULL)Stack[top] p-rChild;if(p-lChild ! NULL)Stack[top] p-lChild;}}
}后序遍历非递归
先将后序遍历的原因是后序遍历和先序遍历有一些关系。
我们将后序遍历的倒排叫做逆后序。如下图所示 仔细观察逆后序我们可以发现一件事。先序遍历是先遍历根然后遍历左子树然后遍历右子树。而逆后序是先遍历根然后右子树最后左子树。
得到逆序后后我们可以使用C容器特有resort方法也可以将得到的元素全部压入栈中然后取出即可得到后序遍历。
void postorderNonrecursion(BTNode *bt)
{if(bt! NULL){BTNode * Stack1[maxSize],*Stack2[maxSize];//定义顺序栈int top1,top2 -1;//定义栈顶指针BTNode *p NULL;//定义遍历指针Stack1[top1] bt;//根节点入栈while(top1 ! -1){p Stack1[top1--];Stack2[top2] p;if(p-lChild ! NULL)Stack1[top] p-lChild;if(p-rChild ! NULL)Stack1[top] p-rChild;}while(top ! -1){p Stack2[top2--];Visit(p);}}
}中序遍历非递归化 中序遍历是这么做的开始直接一直往左的深处走途中经过的结点全部压入栈如上图压入栈的有1,2,4。
而后出栈并读取栈顶元素。若栈顶元素子树元素非空则入栈则4出栈栈顶元素为2。2读取元素并出栈2有子树故5入栈栈中元素为1,5。
5读取元素并出栈无子树。
1读取元素并出栈有子树3入栈。3有左子树故一直往左子树深处走。途经6,8,故6,8入栈。此时栈中元素3,6,8栈顶元素为8。
8读取元素并出栈无子树。
6读取元素并出栈无子树。
3读取元素并出栈有子树故7入栈。
7读取元素并出栈无子树。
故全程中序遍历元素为4,2,5,1,8,6,3,7
void inorderNonrecursion(BTNode *bt)
{if(bt! NULL){BTNode * Stack[maxSize];//定义顺序栈int top -1;//定义栈顶指针BTNode *p NULL;//定义遍历指针p bt;//将遍历指针指向根节点while(top ! -1 || p! nullptr){while(p ! nullptr){Stack[top] p;p p-lChild;}if(top ! -1){p Stack[top--];Visit(p);p p-rChild;}}}
}9.3 二叉树层次遍历 想要层次遍历二叉树我们需要辅助队列。 首先是1入队然后1出队访问1的左右子树。存在2和3。
2入队后3入队然后2出队访问2的左右子树。存在。故4,5入队。
3出队访问3的左右子树存在。故6,7入队。
4出队访问4的左右子树不存在。
5出队访问5的左右子树不存在。
6出队访问6的左右子树存在88入队。
7出队访问7的左右子树不存在。
8出队访问8的左右子树不存在。
至此遍历完成。
void level(BTNode * bt)
{if(bt ! NULL){int front,rear;BTNode *que[maxSize];front rear 0;BTNode *p;rear (rear 1)%maxSize;que[rear] bt;while(front ! rear){front (front 1) % maxSize;p que[front];Visit(p);if(p-lChild ! NULL){rear (rear 1)%maxSize;que[rear] p-lChild;}if(p-rChild ! NULL){rear (rear 1)%maxSize;que[rear] p-rChild;}}}
}
