树的非递归中序和层次遍历实现

Size: px

Start display at page:

Download "树的非递归中序和层次遍历实现"

以围完颜
4 years ago
Views:

1 相信大家对树的各种递归的遍历很了解, 利用递归使得代码变得简单而且比较好理解, 但是利用递归是需要代价的, 特别是当递归层次比较深的时候, 可能会导致递归栈溢出而且递归一般运行速度比较慢, 那么这种情况下, 我们就可以采用非递归来实现, 非递归相对递归来说, 代码相对比较难理解, 而且代码量也一般比较多, 可是它的执行效率却是很不错的在树的中序非递归遍历中需要用到栈, 在层次遍历中需要用到队列, 非递归中序遍历的思想如下 : 1. 先设一个栈 st 和一个指向树根的指针 pval, 用 pval 指指向结点的 m_pleft( 左孩子 ) 并顺其而下直到 pval ==NULL 跳出循环, 在这一过程中把每个节点入栈, 则此时的 pval 指向的是树的最左结点 2. 栈顶元素出栈以访问最左结点 ( 此步很重要, 是为了实现按栈内元素的顺序后入先出访问结点访问最左结点的根结点栈内元素逐一退栈即为中序遍历的元素顺序 ) 3. 访问最左结点的根结点 4. 由于将右子树理解为一个子树, 对其的遍历也是采用中序遍历的方法, 故将右子树的根结点理解为开始遍历树时的根结点, 故可用语句 pval = pval->m_pright, 则又开始了对一个树的遍历,pVal 指针又会走遍右子树的每一个结点非递归中序遍历的思想如下 : 1. 按层次遍历需要一个队列, 开始将二叉树的头结点入队 2. 然后每次从队列中删除一个节点并输出节点信息, 接下来把它的非空 3. 左右孩子入队, 下一个输出的位它的右面堂兄弟或兄弟节点信息, 在把它的 4. 左右孩子入队, 这两个孩子在上面两个孩子的后面 ( 紧跟其后 ) 5. 这样当队列为空时算法结束算法实现 : #include <stdio.h> #include <stdlib.h> // Author: 过往记忆 // wyphao.2007@163.com // Blog: // TreeNode ////////////////////////////////////////////////////////////////////////// typedef struct TreeNode char m_cval; TreeNode* m_pleft; TreeNode* m_pright; 1 / 7

2 ; TreeNode(char cval); ~TreeNode(); TreeNode::TreeNode(char cval) m_cval = cval; m_pleft = 0; m_pright = 0; TreeNode::~TreeNode() //Stack ////////////////////////////////////////////////////////////////////////// class Stack public: Stack(int iamount = 10); ~Stack(); //return 1 means succeeded, 0 means failed. int Pop(TreeNode* &pval); int Push(TreeNode* pval); int Top(TreeNode* &pval); //1 means not null, 0 means null. int NotNull(); private: TreeNode **m_ppdata; int m_icount; int m_iamount; ; Stack::Stack(int iamount) m_ppdata = new TreeNode*[iAmount]; m_icount = 0; m_iamount = iamount; Stack::~Stack() 2 / 7

3 delete m_ppdata; int Stack::Pop(TreeNode* &pval) if(m_icount>0) --m_icount; pval = m_ppdata[m_icount]; int Stack::Push(TreeNode* pval) if(m_icount<m_iamount) m_ppdata[m_icount] = pval; ++m_icount; int Stack::Top(TreeNode* &pval) if(m_icount>0 && m_icount<=m_iamount) pval = m_ppdata[m_icount-1]; int Stack::NotNull() if(m_icount!=0) //Queue ////////////////////////////////////////////////////////////////////////// class Queue 3 / 7

4 public: Queue(int nmounts); ~Queue(); //operator int EnQueue(TreeNode *node); int DeQueue(TreeNode *&node); int IsFull(); int IsEmpty(); private: TreeNode **Q; int front; int rear; int totalnode; ; Queue::Queue(int nmounts = 10) Q = new TreeNode*[nMounts]; totalnode = nmounts; rear = 0; front = 0; Queue::~Queue() delete Q; int Queue::EnQueue(TreeNode *node) if(!isfull()) Q[rear] = node; rear = (rear + 1) % totalnode; else //printf("queue is full!\n"); int Queue::DeQueue(TreeNode *&node) if(!isempty()) node = Q[front]; front = (front + 1) % totalnode; else //printf("queue is empty!\n"); 4 / 7

5 int Queue::IsFull() if((rear + 1) % totalnode == front) int Queue::IsEmpty() if(rear == front) int main(int argc, char* argv[]) TreeNode na('a'); TreeNode nb('b'); TreeNode nc('c'); TreeNode nd('d'); TreeNode ne('e'); TreeNode nf('f'); TreeNode ng('g'); TreeNode nh('h'); TreeNode ni('i'); TreeNode nj('j'); TreeNode nk('k'); TreeNode nl('l'); na.m_pleft = &nb; na.m_pright = &nc; nb.m_pright = &nd; nd.m_pright = &ng; nc.m_pleft = ≠ nc.m_pright = &nf; nf.m_pright = &nh; nh.m_pleft = &ni; nh.m_pright = &nj; ni.m_pleft = &nk; ni.m_pright = &nl; 5 / 7

6 Stack st; // 非递归中序遍历 TreeNode *pval = &na; int ipopped = 0; while(pval!=0) if(pval->m_pleft!=0 && ipopped==0) st.push(pval); pval = pval->m_pleft; ipopped = 0; else if(pval->m_pright!=0) printf("%c ", pval->m_cval); pval = pval->m_pright; ipopped = 0; else printf("%c ", pval->m_cval); if(0==st.pop(pval)) break; ipopped = 1; printf("\n"); // 层次遍历 pval = &na; Queue queue; while(pval!= NULL) if(pval->m_pleft!= NULL && pval->m_pright!= NULL) queue.enqueue(pval->m_pleft); queue.enqueue(pval->m_pright); else if(pval->m_pleft!= NULL) queue.enqueue(pval->m_pleft); else if(pval->m_pright!= NULL) queue.enqueue(pval->m_pright); printf("%c ", pval->m_cval); if(0 == queue.dequeue(pval)) break; 6 / 7

7 Powered by TCPDF ( printf("\n"); 本博客文章除特别声明, 全部都是原创! 转载本文请加上 : 转载自过往记忆 ( 本文链接 : () 7 / 7

PowerPoint Presentation

PowerPoint Presentation 数据结构与算法 ( 六 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 6 章树 C 树的定义和基本术语树的链式存储结构子结点表表示方法静态左孩子 / 右兄弟表示法动态表示法动态左孩子 / 右兄弟表示法父指针表示法及其在并查集中的应用