二叉树的中序遍历（两种实现方式）

浅浅的花香味﹌ 2023-07-24 03:04 5阅读 0赞

## 二叉树的中序遍历（递归与非递归实现） ##

二叉树采用[链式存储结构][Link 1]进行保存。

二叉树的定义为：

typedef struct Node{
        
        ElemType data;		        //数据元素
        struct Node *lchild;		//指向左孩子
    	struct Node *rchild;		//指向右孩子
    }BiTree;

*  [中序遍历][Link 2]

中序遍历（LDR）是[二叉树遍历][Link 3]的一种，也叫做[中根遍历][Link 4]、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。

示例:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center]  
递归实现：

左子树递归输出，输出该结点值，再右子树递归输出。

void InOrder(BiTree *tree){
        
    	if(!tree) return ; //递归结束条件
    	InOrder(tree->lchild);
    	cout<<tree->data<<" ";
    	InOrder(tree->rchild);
    }

非递归方式实现（栈实现）：

1.  借助于临时结点temp。
2.  从根节点开始遍历左子树，并依次进栈，直到树底。（根节点第一个进栈）
3.  对栈中结点出栈，输出，并获得该结点的右子树，
4.  重复2，3过程,直到栈为空。

void InOrder1(BiTree *tree){
        
    	BiTree *temp=tree; 
        stack<BiTree*> stk;  //采用系统栈stack
    	while(temp||!stk.empty()){
        
    		while(temp){
        
    			stk.push(temp);
    			temp=temp->lchild;
    		}
    		temp = stk.top();
    		stk.pop();
    		cout<<temp->data<<" ";
    		temp = temp->rchild;
    	}
    }

[Link 1]: https://baike.baidu.com/item/%E9%93%BE%E5%BC%8F%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84/4921270?fr=aladdin
[Link 2]: https://baike.baidu.com/item/%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86/757281?fr=aladdin
[Link 3]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91%E9%81%8D%E5%8E%86/9796049
[Link 4]: https://baike.baidu.com/item/%E4%B8%AD%E6%A0%B9%E9%81%8D%E5%8E%86/1703566
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/3e4914d6f12c4b7c9d3cbc2933aab6cf.png