注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Mr.Right

不顾一切的去想,于是我们有了梦想。脚踏实地的去做,于是梦想成了现实。

 
 
 

日志

 
 
关于我

人生一年又一年,只要每年都有所积累,有所成长,都有那么一次自己认为满意的花开时刻就好。即使一时不顺,也要敞开胸怀。生命的荣枯并不是简单的重复,一时的得失不是成败的尺度。花开不是荣耀,而是一个美丽的结束,花谢也不是耻辱,而是一个低调的开始。

网易考拉推荐

C/C++二叉树的创建和遍历---亲自验证通过  

2013-02-20 13:39:44|  分类: 编程 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

二叉树的结点结构是:
1、根结点(存放结点数据)
2、左子树指针
3、右子树指计
对二叉树的遍历就是访问各个结点中根结点里存放的数据。例如:
    如果结点A有左结点B,右结点C,记作A(B,C),不同结点我用"\"隔开。那么有这样一个(BitTree)二叉树表A(B,C) \B(D,E)\E(F.G)\C(空,H)\H(I.空)

要想把所有的数据都访问到则必需按照一定的原则,即当前结点的下一个结点是哪个结点。
       无论是先、中还是后序算法都是先将左结点视为下一个结点,当左结点不存在(即为空时)才将右结点视作下一个结点,如果右结点也不存在就返回当前结点的上层结点再向右访问,如此类推。
   于是对二叉树的遍历问题就被抽象成三个基本步骤:
1、访问根结点。
2、访问该点的所有左子树。
3、访问该点的所有右子树。
   先序遍历的策略是按123的步骤执行,中序是按213来,后序则是231,它们之间的不同只是“访问根结点”在这三个步骤中的位置。
   看着你刚画好的那个BitTree跟着我的思路走。在先序遍历算法PriorOrder中,先将BitTree的头结点A传进来,按步骤123的处理。123是抽象实现,记住所表达的思想,下面是具体实现。为了避免混乱用中文数字记录步骤。
一、即是读取结点A的数据内容A(此时A为当前函数处理结点),将A的右结点C放入栈S中,S中的内容为S(C)[注意这一步是算法的一个辅助,并不是先向右访问,下同],将左结点B传给PriorOrder处理。此时读取了A
二、读取B的内容B(此时B为当前结点),将B的右结点E放入S中,S中的内容为S(C,E),将B的左结点D传给PriorOrder处理。此时读取了AB
三、D为当前结点,D的右为空没有东西放入S,S中的内容仍为S(C,E),D的左也为空,没有访问可访问的。此时就从S中取出E(因为栈是先进后出的所以取的就是E,此时S中的内容为S(C),正好是上一层没访问过的右子树),将E传给PriorOrder处理。此时读取了AB D
四、E为当前结点,对于结点E类似的有S(C,G),读取了ABDE,将F传入PriorOrder
五、F为当前结点,右为空,左也为空,读取了ABDEF,从栈中取出G传给PriorOrder处理,S的内容为S(C);
六、类似的读取了ABDEFG,从S中取出了C,传给PriorOrder处理。此时S()。
七、当前结点为C,从将C的右结点放入S,S中内容为S(H),C的左为空,从S取出H,将H传给PriorOrder处理。此时S为S().于是就读取了ABDEFGC
八,类似的读取了ABDEFGCH
九,最后ABDEFGCHF
   你再对照的书上的算法想想,画画就应该能明白点。特别要理角的一点是为什么用递归算法时计算机能按这样的方式是因为函数调用是“先调用,后执行完”,或者说“后调用,先执行完”。注意我加一个“完”字
// Creating and traversing a binary tree
// preorder, inorder, and postorder
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// self-referential structure                           
struct treeNode {                                          
   struct treeNode *leftPtr; // pointer to left subtree
   int data; // node value                              
   struct treeNode *rightPtr; // pointer to right subtree
}; // end structure treeNode                            

typedef struct treeNode TreeNode; // synonym for struct treeNode
typedef TreeNode *TreeNodePtr; // synonym for TreeNode*

// prototypes
void insertNode( TreeNodePtr *treePtr, int value );
void inOrder( TreeNodePtr treePtr );
void preOrder( TreeNodePtr treePtr );
void postOrder( TreeNodePtr treePtr );

// function main begins program execution
int main( void )
{
   unsigned int i; // counter to loop from 1-10
   int item; // variable to hold random values
   TreeNodePtr rootPtr = NULL; // tree initially empty

   srand( time( NULL ) );
   puts( "The numbers being placed in the tree are:" );

   // insert random values between 0 and 14 in the tree
   for ( i = 1; i <= 10; ++i ) {
      item = rand() % 15;
      printf( "%3d", item );
      insertNode( &rootPtr, item );
   } // end for

   // traverse the tree preOrder
   puts( "\n\nThe preOrder traversal is:" );
   preOrder( rootPtr );

   // traverse the tree inOrder
   puts( "\n\nThe inOrder traversal is:" );
   inOrder( rootPtr );

   // traverse the tree postOrder
   puts( "\n\nThe postOrder traversal is:" );
   postOrder( rootPtr );
} // end main

// insert node into tree
void insertNode( TreeNodePtr *treePtr, int value )
{
   // if tree is empty
   if ( *treePtr == NULL ) {  
      *treePtr = malloc( sizeof( TreeNode ) );

      // if memory was allocated, then assign data
      if ( *treePtr != NULL ) {
         ( *treePtr )->data = value;
         ( *treePtr )->leftPtr = NULL;
         ( *treePtr )->rightPtr = NULL;
      } // end if
      else {
         printf( "%d not inserted. No memory available.\n", value );
      } // end else
   } // end if
   else { // tree is not empty
      // data to insert is less than data in current node
      if ( value < ( *treePtr )->data ) {                  
         insertNode( &( ( *treePtr )->leftPtr ), value );  
      } // end if                                       

      // data to insert is greater than data in current node
      else if ( value > ( *treePtr )->data ) {                
         insertNode( &( ( *treePtr )->rightPtr ), value );    
      } // end else if                                     
      else { // duplicate data value ignored
         printf( "%s", "dup" );
      } // end else
   } // end else
} // end function insertNode

// begin inorder traversal of tree
void inOrder( TreeNodePtr treePtr )
{
   // if tree is not empty, then traverse
   if ( treePtr != NULL ) {               
      inOrder( treePtr->leftPtr );        
      printf( "%3d", treePtr->data );     
      inOrder( treePtr->rightPtr );       
   } // end if                         
} // end function inOrder

// begin preorder traversal of tree
void preOrder( TreeNodePtr treePtr )
{
   // if tree is not empty, then traverse
   if ( treePtr != NULL ) {               
      printf( "%3d", treePtr->data );     
      preOrder( treePtr->leftPtr );       
      preOrder( treePtr->rightPtr );      
   } // end if                         
} // end function preOrder

// begin postorder traversal of tree
void postOrder( TreeNodePtr treePtr )
{
   // if tree is not empty, then traverse
   if ( treePtr != NULL ) {               
      postOrder( treePtr->leftPtr );      
      postOrder( treePtr->rightPtr );     
      printf( "%3d", treePtr->data );     
   } // end if                         
} // end function postOrder
?
用C语言写程序解答了下面两个算法题:
(1)给出一棵二叉树的中序与后序遍历序列,求出它的先序遍历序列。
(2)给出一棵二叉树的中序与先序遍历序列,求出它的后序遍历序列。
#include <iostream>
#include <string>

using namespace std;

//存储节点数据,为简便起见,这里选用字符
typedef char   DATA_TYPE;

typedef struct tagBINARY_TREE_NODE  BINARY_TREE_NODE, *LPBINARY_TREE_NODE;

struct tagBINARY_TREE_NODE
{
      DATA_TYPEdata;           //节点数据
     LPBINARY_TREE_NODE    pLeftChild;     //左孩子指针
  LPBINARY_TREE_NODE       pRightChild;    //右孩子指针
};

//
//函数名称:TreeFromMidPost
//函数功能:给出一棵二叉树的中序与后序序列,构造这棵二叉树。
//输入参数:LPBINARY_TREE_NODE & lpNode:二叉树的结点
//          string mid:存储了二叉树的中序序列的字符串
//          string post:存储了二叉树的后序序列的字符串
//          int lm, int rm:二叉树的中序序列在数组mid中的左右边界
//          int lp, int rp:二叉树的后序序列在数组post中的左右边界
//
void TreeFromMidPost(LPBINARY_TREE_NODE & lpNode, string mid, string post, int lm, int rm, int lp, int rp)
{
//构造二叉树结点
    lpNode = new BINARY_TREE_NODE;
    lpNode->data = post[rp];
    lpNode->pLeftChild = NULL;
lpNode->pRightChild = NULL;

    int pos = lm;

    while (mid[pos] != post[rp])
{
        pos++;
}
    int iLeftChildLen = pos - lm;

    if (pos > lm)//有左孩子,递归构造左子树
{
        TreeFromMidPost(lpNode->pLeftChild, mid, post, lm, pos - 1, lp, lp + iLeftChildLen - 1);
}

    if (pos < rm)//有右孩子,递归构造右子树
{
        TreeFromMidPost(lpNode->pRightChild, mid, post, pos + 1, rm, lp + iLeftChildLen, rp - 1);
}
}

//
//函数名称:TreeFromMidPre
//函数功能:给出一棵二叉树的先序与中序序列,构造这棵二叉树。
//输入参数: BINARY_TREE_NODE & lpNode:二叉树的结点
//          string mid:存储了二叉树的中序序列的字符串
//          string pre:存储了二叉树的先序序列的字符串
//          int lm, int rm:二叉树的中序序列在数组mid中的左右边界
//          int lp, int rp:二叉树的先序序列在数组pre中的左右边界
//
void TreeFromMidPre(LPBINARY_TREE_NODE & lpNode, string mid, string pre, int lm, int rm, int lp, int rp)
{
//构造二叉树结点
    lpNode = new BINARY_TREE_NODE;
    lpNode->data = pre[lp];
    lpNode->pLeftChild = NULL;
lpNode->pRightChild = NULL;

    int pos = lm;

    while (mid[pos] != pre[lp])
{
        pos++;
}
    int iLeftChildLen = pos - lm;

    if (pos > lm)//有左孩子,递归构造左子树
{
        TreeFromMidPre(lpNode->pLeftChild, mid, pre, lm, pos - 1, lp + 1, lp + iLeftChildLen);
}

    if (pos < rm)//有右孩子,递归构造右子树
{
        TreeFromMidPre(lpNode->pRightChild, mid, pre, pos + 1, rm, lp + iLeftChildLen + 1, rp);
}
}

//先序遍历
void PreOrder(LPBINARY_TREE_NODE p)
{
       if(p != NULL)
       {
              cout << p->data;          //输出该结点
              PreOrder(p->pLeftChild);  //遍历左子树
              PreOrder(p->pRightChild); //遍历右子树
       }
}

//中序遍历
void MidOrder(LPBINARY_TREE_NODE p)
{
       if(p != NULL)
       {
              MidOrder(p->pLeftChild);   //遍历左子树
  cout << p->data;           //输出该结点
              MidOrder(p->pRightChild);  //遍历右子树
       }
}

//后序遍历
void PostOrder(LPBINARY_TREE_NODE p)
{
       if(p != NULL)
       {
              PostOrder(p->pLeftChild);  //遍历左子树
              PostOrder(p->pRightChild); //遍历右子树
  cout << p->data;           //输出该结点
       }
}

//释放二叉树
void Release(LPBINARY_TREE_NODE lpNode)
{
if(lpNode != NULL)
{
Release(lpNode->pLeftChild);
Release(lpNode->pRightChild);
delete lpNode;
lpNode = NULL;
}
}


int main(int argc, char* argv[])
{
stringpre;            //存储先序序列
    stringmid;            //存储中序序列
stringpost;           //存储后序序列

    LPBINARY_TREE_NODElpRoot;         //二叉树根节点指针


cout<<"程序1已知二叉树的中序与后序序列,求先序序列"<<endl;
cout<<"请先输入中序序列,回车后输入后序序列:"<<endl;

cin >> mid;
cin >> post;

TreeFromMidPost(lpRoot, mid, post, 0, mid.size()-1, 0, post.size()-1);
cout<<"先序遍历结果:";
PreOrder(lpRoot);
cout<<endl;

cout<<"中序遍历结果:";
MidOrder(lpRoot);
cout<<endl;

cout<<"后序遍历结果:";
PostOrder(lpRoot);
cout<<endl;
Release(lpRoot);
cout<<endl;

cout<<"程序2已知二叉树的中序与先序序列,求后序序列"<<endl;
cout<<"请先输入先序序列,回车后输入中序序列:"<<endl;
cin >> pre;
cin >> mid;

TreeFromMidPre(lpRoot, mid, pre, 0, mid.size()-1, 0, pre.size()-1);
cout<<"先序遍历结果:";
PreOrder(lpRoot);
cout<<endl;

cout<<"中序遍历结果:";
MidOrder(lpRoot);
cout<<endl;

cout<<"后序遍历结果:";
PostOrder(lpRoot);
cout<<endl;
Release(lpRoot);
cout<<endl;

    return 0;
}

(1)程序1的输入方式:
已知二叉树的中序与后序序列,求先序序列,请先输入中序序列,回车后输入后序序列:
例如输入:
DGBAECHF
GDBEHFCA

输出:
先序遍历结果:ABDGCEFH
中序遍历结果:DGBAECHF
后序遍历结果:GDBEHFCA
(2)程序2的输入方式:
已知二叉树的先序与中序序列,求后序序列,请先输入先序序列,回车后输入中序序列:
例如输入:
abdefgc
debgfac

输出:
先序遍历结果:abdefgc
中序遍历结果:debgfac
后序遍历结果:edgfbca

  评论这张
 
阅读(1126)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016