二叉树：中序遍历，递归和非递归达成
发布时间：2021-11-19 16:59:15 所属栏目：教程 来源：互联网
导读：. 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、二叉树定义： 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; }  （编辑：宁德站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
