MyException - 我的异常网
当前位置:我的异常网» 编程 » 数据结构口试之六——二叉树的常见操作2(非递归遍

数据结构口试之六——二叉树的常见操作2(非递归遍历&二叉排序树)

www.MyException.Cn  网友分享于:2013-09-17  浏览:8次
数据结构面试之六——二叉树的常见操作2(非递归遍历&二叉排序树)

数据结构面试之六——二叉树的常见操作2(非递归遍历&二叉排序树)

题注:《面试宝典》有相关习题,但思路相对不清晰,排版有错误,作者对此参考相关书籍和自己观点进行了重写,供大家参考。

六、二叉树的基本操作(非递归遍历)&二叉排序树的操作

       接上一节第五部分,主要分析二叉树的非递归遍历和二叉排序树的操作。

1.      非递归中序遍历

//1.依次将根节点root的左子树入栈,直到lchild=NULL,执行2

//2.将栈的元素出栈、访问;将当前指针指向节点的rchild,循环遍历。直到栈空为止!

      

 template<typenameelemType>
       voidbinaryTreeType<elemType>::noRecursionInorderTraversal()                      //非递归中序遍历
       {
              cout<< "noRecursionInorderTraversal--------------------------->"<< endl;
              linkedStackType<nodeType<elemType>* > stack;
              nodeType<elemType>*current = root;
              while(current!= NULL || !stack.isEmptyStack())  //或者||
              {
                     if(current!= NULL)
                     {
                            stack.push(current);
                            current= current->llink;
                     }
                     else
                     {
                            stack.pop(current);
                            cout<< current->info << "\t"; //出栈的时候访问节点
                            current= current->rlink;
                     }
              }
              cout<< endl;
              cout<< "<------------------------noRecursionInorderTraversal"<< endl;
       }

2.      非递归先序遍历

       //在中序遍历的基础上,访问次序发生变化;

       //先序遍历,需要先逐个遍历根节点,然后依次处理其左、右孩子节点。

     

  template<typenameelemType>
       voidbinaryTreeType<elemType>::noRecursionPreorderTraversal()                     //非递归前序遍历
       {
              cout<<"noRecursionPreorderTraversal--------------------------->"<< endl;
              linkedStackType<nodeType<elemType>* > stack;
              nodeType<elemType>*current = root;
              while(current!= NULL || !stack.isEmptyStack())  //或者||
              {
                     if(current!= NULL)
                     {
                            cout<< current->info << "\t";   //先访问节点后入栈
                            stack.push(current);
                            current= current->llink;
                     }
                     else
                     {
                            stack.pop(current);
                            current= current->rlink;
                     }
              }
              cout<< endl;
              cout<< "<------------------------noRecursionPreorderTraversal"<< endl;
       }

3.      非递归后序遍历

由于访问的顺序为先左子树、然后右子树,最后根节点。并且对于每一个节点都是上述操作,所以,对于遍历来讲,需要识别当前节点类型是根(相对)、左孩子节点 、右孩子节点。故,我们设定了flag标记变量flag=0初始标记,节点尚未入栈;在访问左孩子之前将flag置为1;在访问右孩子之前将flag置为2;并且在访问右孩子之后,将flag置为0。

       //后序非递归遍历比较复杂..

     

  template<typenameelemType>
voidbinaryTreeType<elemType>::noRecursionPostorderTraversal()                    //非递归后序遍历
       {
              cout<<"noRecursionPostorderTraversal--------------------------->"<< endl;
              linkedStackType<nodeType<elemType>* > stack;
              linkedStackType<int>intStack;                       //标记位同步栈.
              nodeType<elemType>*current = root;
              intnflag = 0;                                      //初始标记为0.
              if(current== NULL)
              {
                     cout<< "The Stack is Empty!" << endl;
              }
              else
              {
                     //1.将头节点先入栈,
                     stack.push(current);
                     intStack.push(1);
               current = current->llink;        //注意此处需要调整指向******
                     while(!stack.isEmptyStack()&& !intStack.isEmptyStack())         
                     {
                            if(current!= NULL && nflag == 0)                                     
                            {
                               stack.push(current);
                                   intStack.push(1);   //标记位为1,[在访问左孩子之前,将其值置为1]。
                               current = current->llink;
                            }
                            else
                            {
                                   stack.pop(current);
                                   intStack.pop(nflag);    //此时的标记位为返回值,需要根据其做判断
                                   if(nflag== 1)         //说明下一步需要入栈的为右孩子.
                                   {
                                          stack.push(current);   //继续将该节点入栈,                                                              
                                         intStack.push(2);      //但[在访问右孩子之前,将其置为2]。
                                          current= current->rlink;           //访问右节点,
                                          nflag= 0;                                  //置标记位为0
                                   }
                                   else
                                   {
                                          cout<< current->info << " ";  //待左右子树都为空再访问节点。
                                   }
                            }
                     }
                     cout<< endl;
                     cout<< "<------------------------noRecursionPostorderTraversal"<< endl;
              }    
       }

 

4.      二叉排序树的搜索操作

明确概念,国内、国外的著作里提及的下三个概念等价,二叉搜索树=二叉查找树=二叉排序树。

//二叉排序树的查找存在以下几种情况:

//1.链表为空,提示并返回;

//2.链表非空,需要循环查找直到指针为空,若存在,则bfound=true;否则查找至最后bfound=缺省false。

template <class elemType>
boolbSearchTreeType<elemType>::search(const elemType& searchItem)
{
       nodeType<elemType>*current = new nodeType<elemType>;
       boolbFound = false;
 
       if(root== NULL)
       {
              cout<< "The bSearchTree is NULL\n";       //case1: 链表为空!
              returnfalse;
       }
       else
       {
              current= root;
              while(current!= NULL && !bFound) //case2:在链表中查找,根据大小锁定左、右子树.
              {
                     if(current->info== searchItem)
                     {
                            bFound= true;
                     }
                     elseif(current->info > searchItem)
                     {
                            current= current->llink;              //左子树
                     }
                     elseif(current->info < searchItem)
                     {
                            current= current->rlink;             //右子树
                     }
              }
       }
 
       returnbFound;
}

5.      二叉排序树的插入存在以下几种情况:

//1.链表为空,插入元素即为根节点;

//2.链表非空,需要寻找插入位置后插入。

//2.1插入元素已经存在,则提示出错。

//2.2总能找到大于或小于某节点的位置,记录trailcurrent完成插入操作。

template <class elemType>
voidbSearchTreeType<elemType>::insert(const elemType& insertItem)
{
       nodeType<elemType>*newNode = new nodeType<elemType>;
       nodeType<elemType>*current;
       nodeType<elemType>*trailCurrent;
 
       newNode->info= insertItem;
       newNode->llink= NULL;
       newNode->rlink= NULL;
 
       if(root== NULL)
       {
              root= newNode;                                //case1:树为空.
       }
       else
       {
              current= root;
              while(current!= NULL)                          //case2,3,4搜索才知道!
              {
                     trailCurrent= current;
                     if(current->info== insertItem)
                     {
                            cout<< "the elem is already exist!\n";  //case2:元素已经存在
                            return;
                     }
                     else
                     {
                            if(current->info> insertItem)
                            {
                                   current= current->llink;           //case3:锁定左侧位置...
                            }
                            else
                            {
                                   current= current->rlink;           //case4:锁定右侧位置...
                            }
                     }
              }//endwhile
 
              //case3,4根据大小进行链接
              if(trailCurrent->info< insertItem)           
              {
                     trailCurrent->rlink= newNode;
              }
              else
              {
                     trailCurrent->llink= newNode;
              }
 
       }//end else
}

6.      二叉排序树的删除存在以下几种情况【此处可能复杂些】:

//删除一个节点,要首先判断元素值在二叉排序树中是否存在,

//若不存在则返回;

//若存在则需要锁定其对应位置为1根节点;2叶节点;3其余节点。

//根据要删除的节点是否含有左右子树的不同,分为4种情况考虑,

//见deleteFromTree()函数。

template <class elemType>
voidbSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
{
       //1.查找节点
       //2.1找不到,不存在;
       //2.2找到,删除,调用函数
       nodeType<elemType>*current;
       nodeType<elemType>*trailCurrent;
       boolbFound = false;
 
       if(root== NULL)
       {
              cout<< "Can't delete an Empty BST" << endl;
              return;
       }
       else
       {
              current= root;
              trailCurrent= root;
              while(current != NULL && !bFound)
              {
                     if(current->info== deleteItem)
                     {
                            bFound= true;
                     }
                     elseif(current->info > deleteItem)
                     {
                            trailCurrent= current;
                            current= current->llink;    //左
                     }
                     else
                     {
                            trailCurrent= current;
                            current= current->rlink;   //右
                     }
              }//endwhile
 
              if(current== NULL)
              {
                     cout<< deleteItem << " is not Exist in the BST!\n" <<endl;
              }
              elseif(bFound)
              {
                     if(current== root)
                     {
                            deleteFromTree(root);                  //可能是根节点
                     }
                     elseif(trailCurrent->info > deleteItem)
                     {
                            deleteFromTree(trailCurrent->llink);//左半分支,调整trailCurrent的指向
                     }
                     elseif(trailCurrent->info < deleteItem)
                     {
                            deleteFromTree(trailCurrent->rlink);  //右半分支,调整trailCurrent的指向
                     }
              }//endif bFound
         }//end else
}


//[原理]:某节点的前驱是该节点左子树的最右端的节点(中序遍历的结果)

template <class elemType>
voidbSearchTreeType<elemType>::deleteFromTree(nodeType<elemType>*&p)
{
       nodeType<elemType>*temp;
       nodeType<elemType>*current;
       nodeType<elemType>*trailCurrent;
 
       if(p== NULL)
       {
              cout<< "The BST is NULL!" << endl;
              return;
       }
       if(p->llink== NULL && p->rlink == NULL)      //情况1,左右节点都为空(叶节点)
       {
              temp= p;
              p= NULL;
              deletetemp;
       }
       elseif( p->rlink == NULL)                     //情况2,右子树为空,左非空
       {
              temp= p;
              p= temp->llink;
              deletetemp;
       }
       elseif(p->llink == NULL)                      //情况3,左子树为空,右非空
       {
              temp= p;
              p= temp->rlink;
              deletetemp;
       }
       else                           //情况4,左右都非空[用中序遍历的前一个节点替换]
       {
              current= p->llink;
              trailCurrent= NULL;
 
              while(current->rlink!= NULL)
              {
                     trailCurrent= current;   //trailCurrent最终指向准备删除节点的前一个节点
                     current= current->rlink;
              }
 
              p->info= current->info;                //信息赋值
 
              if(trailCurrent== NULL)              //仅一个左孩子节点
              {
                     p->rlink = current->llink;         
              }
              else
              {
                     trailCurrent->rlink= current->llink; //给删除前点的前面一个节点调整指针指向
              }
              deletecurrent;
       }
 
}


文章评论

科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
 程序员的样子
程序员的样子
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
老程序员的下场
老程序员的下场
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
我是如何打败拖延症的
我是如何打败拖延症的
漫画:程序员的工作
漫画:程序员的工作
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
旅行,写作,编程
旅行,写作,编程
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
鲜为人知的编程真相
鲜为人知的编程真相
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
程序员必看的十大电影
程序员必看的十大电影
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
一个程序员的时间管理
一个程序员的时间管理
程序员应该关注的一些事儿
程序员应该关注的一些事儿
10个调试和排错的小建议
10个调试和排错的小建议
程序员都该阅读的书
程序员都该阅读的书
总结2014中国互联网十大段子
总结2014中国互联网十大段子
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
编程语言是女人
编程语言是女人
程序员的鄙视链
程序员的鄙视链
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
每天工作4小时的程序员
每天工作4小时的程序员
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
程序员和编码员之间的区别
程序员和编码员之间的区别
中美印日四国程序员比较
中美印日四国程序员比较
Java程序员必看电影
Java程序员必看电影
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有