首页 > 代码库 > 二叉树(2)----中序遍历,递归和非递归实现
二叉树(2)----中序遍历,递归和非递归实现
1、二叉树定义:
typedef struct BTreeNodeElement_t_ { void *data; } BTreeNodeElement_t; typedef struct BTreeNode_t_ { BTreeNodeElement_t *m_pElemt; struct BTreeNode_t_ *m_pLeft; struct BTreeNode_t_ *m_pRight; } BTreeNode_t;
2、中序遍历
定义:首先访问左子树,然后访问根节点,最后访问右子树
(1)递归实现
如果根节点为NULL,则返回
如果根节点不为NULL,则首先访问左子树,然后访问根节点,最后访问右子树
void InorderTraverse( BTreeNode_t *pRoot){ if( pRoot == NULL ) return ; InorderTraverse( pRoot->m_pLeft); Visiste( pRoot ); InorderTraverse( pRoot->m_pRight); }
(2)非递归实现
第一步:给定根节点pRoot,判断pRoot是否为空,如果不为空,然后进行第二步;如果为空,则进行第三步;
第二步:将pRoot入栈,将pRoot的左结点赋给pRoot,然后进行第一步;
第三步:判断栈是否为空;如果为空,则结束,如果不为空,则取出栈顶元素给pRoot,并出栈,访问pRoot,然后将pRoot的右结点赋给pRoot,然后进行第一步。
void InorderTraverse( BTreeNode_t *pRoot){ if( pRoot == NULL ) return ; stack < BTreeNode_t *> st; while( pRoot != NULL || !st.empty() ){ while( pRoot != NULL ){ st.push( pRoot); pRoot = pRoot->m_pLeft; } if( !st.empty() ){ pRoot = st.top(); st.pop(); Visit( pRoot ); pRoot = pRoot->m_pRight; } } return; }
二叉树(2)----中序遍历,递归和非递归实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。