=================先序遍历===============
先序遍历伪代码1：
void preOrder1(TNode *root)
{
Stack st;
while((root != NULL) || !st.empty())
{
if(root!=NULL)
{
visit(root); //先访问再入栈
st.push(root);
root = root->left;
}
else
{
root = st.pop();
root = root->right;
}
}
}
先序遍历伪代码2：
void preOrder2(TNode* root)
{
if(root != NULL)
{
Stack st;
st.push(root);
while( !st.empty() )
{
TNode* node = st.pop();
visit(node); //先访问根节点，然后根节点就不用入栈了
st.push(node->right); //先push右节点，然后是左节点
st.push(node->left); //这样上边先访问到左节点
}
}
}
先序遍历不用栈：
void preOrder3(TNode* root)
{
while(root != NULL)
{
if(!root->bVisited)
{
visit(root);
root->bVisited = true;
}
if(root->left && !root->left->bVisited)
{
root = root->left;
}
else if(root->right!=NULL && !root->right->bVisited)
{
root = root->right;
}
else
{ //回溯
root = root->parent;
}
}
}
=================中序遍历===============
中序遍历伪代码：
void inOrder1(TNode* root)
{
Stack s;
while(root != NULL || !s.empty())
{
while(root!=NULL) //找到左子树
{
s.push(root); //先入栈
root = root->left;
}
if(!s.empty())
{
root = s.pop(); //再访问
visit(root);
root = root->right; //通过下一次循环遍历右子树
}
}
}
中序遍历不用栈：
void inOrder3(TNode* root)
{
while(root!=NULL)
{
while(root->left!=NULL && !root->left->bVisited)
{
root = root->left;
}
if(!root->bVisited)
{
visit(root);
root->bVisited = true;
}
if(root->right!=NULL && !root->right->bVisited)
{
root = root->right;
}
else
{
root = root->parent; // 回溯
}
}
}
=================后序遍历===============
后序遍历的伪代码：
void PostOrder(TNode* root)
{
stack s;
if(root != NULL)
s.push(root);
while(!s.empty())
{
TNode* node = s.pop();
if(node->bPushed) //其左右子树都已入栈，则访问该节点
{
visit(node);
}
else
{ //左右子树尚未入栈，则依次将根节点、右节点和左节点入栈
s.push(node); // 1> root入栈
if( node->right != NULL)
{
node->right->bPushed = false; //先把左右子树设为false
s.push(node->right); // 2> 右子树入栈
}
if( node->left != NULL)
{
node->left->bPushed = false; //先把左右子树设为false
s.push(node->left); // 3> 左子树入栈
}
node->bPushed = true; // 左右子树都已入栈，根节点可以访问了
}
}
}
=================层序遍历===============
分层遍历伪代码：
void levelOrder(TNode* root)
{
Queue Q;
Q.push(root);
while(!Q.empty())
{
TNode* node = Q.front();
visit(node);
if( node->left != NULL)
{
Q.push(node->left);
}
if(node->right != NULL)
{
Q.push(node->right);
}
}
}
《编程之美》中使用vector容器来储存n个节点信息，并用一个游标变量last记录前一层的访问结束条件，实现如下:
void PrintNodeByLevel(Node* root)
{
vector vec; // 这里我们使用STL 中的vector来代替数组，可利用到其动态扩展的属性
vec.push_back(root);
int cur = 0;
int last = 1;
while(cur < vec.size()) {
Last = vec.size(); // 新的一行访问开始，重新定位last于当前行最后一个节点的下一个位置
while(cur < last) {
cout << vec[cur]->data << " "; // 访问节点
if(vec[cur] -> lChild) // 当前访问节点的左节点不为空则压入
vec.push_back( vec[cur]->lChild );
// 当前访问节点的右节点不为空则压入，注意左右节点的访问顺序不能颠倒
if( vec[cur]->rChild )
vec.push_back( vec[cur]->rChild );
cur++;
}
cout << endl; // 当cur == last时,说明该层访问结束，输出换行符
}
}
另外，
============求树深==========
//若T为空树，则深度为0，否则其深度等于左子树或右子树的最大深度加1
int getDepth(BiTree T)
{
if (T==NULL) return 0;
else{
dep1 = getDepth(T-> lchild);
dep2 = getDepth(T-> rchild);
return dep1 > dep2 ? dep1+1 : dep2+1;
}
小结一下：
用栈来实现比增加指向父节点指针回溯更方便：
1.采用栈的方法，就是跟踪指针移动，用栈保存中间结果的实现方式，先序与中序难度一致，后序很困难。先序与中序只需要修改一下访问的位置即可。
2.采用增加父节点的方法，直接用栈来模拟递归，先序非常简单；而中序与后序难度一致。先序简单是因为节点可以直接访问，访问完毕后无需记录。
而中序与后序时，节点在弹栈后还不能立即访问，还需要等其他节点访问完毕后才能访问，因此节点需要设置标志位来判定，因此需要额外的O(n)空间。
附：C源程序
#include
#include
#define MAX 20
#define NULL 0
typedef char TElemType;
typedef int Status;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status CreateBiTree(BiTree *T){
char ch;
ch=getchar();
if (ch== '# ') (*T)=NULL; /* #代表空指针*/
else {
(*T)=(BiTree) malloc(sizeof(BiTNode));/*申请结点 */
(*T)-> data=ch; /*生成根结点 */
CreateBiTree(&(*T)-> lchild) ; /*构造左子树 */
CreateBiTree(&(*T)-> rchild) ; /*构造右子树 */
}
return 1;
}
void PreOrder(BiTree T){
if (T) {
printf( "%2c ",T-> data); /*访问根结点，此处简化为输出根结点的数据值*/
PreOrder(T-> lchild); /*先序遍历左子树*/
PreOrder(T-> rchild); /*先序遍历右子树*/
}
}
void LevleOrder(BiTree T){
/*层次遍历二叉树T，从第一层开始，每层从左到右*/
/*用一维数组表示队列，front和rear分别表示队首和队尾指针*/
BiTree Queue[MAX],b;
int front,rear;
front=rear=0;
if(T) /*若树非空*/
{
Queue[rear++]=T; /*根结点入队列*/
while(front != rear){ /*当队列非空*/
b=Queue[front++]; /*队首元素出队列，并访问这个结点*/
printf( "%2c ",b-> data);
if(b-> lchild!=NULL)
Queue[rear++]=b-> lchild; /*左子树非空，则入队列*/
if(b-> rchild!=NULL)
Queue[rear++]=b-> rchild; /*右子树非空，则入队列*/
}
}
}//LevelOrder
int getDepth(BiTree T)
{
if (T==NULL) return 0;
else{
dep1 = getDepth(T-> lchild);
dep2 = getDepth(T-> rchild);
return dep1 > dep2 ? dep1+1 : dep2+1;
}//depth
main(){
BiTree T=NULL;
printf( "\nCreate a Binary Tree\n ");
CreateBiTree(&T); /*建立一棵二叉树T*/
printf( "\nThe preorder is:\n ");
PreOrder(T); /*先序遍历二叉树*/
printf( "\nThe level order is:\n ");
LevleOrder(T); /*层次遍历二叉树*/
printf( "\nThe depth is:%d\n ",depth(T));
}
阅读(2427) | 评论(2) | 转发(4) |
