二叉树的先序遍历（两种实现）

系统管理员 2023-07-24 02:09 4阅读 0赞

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

二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

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

二叉树的定义为

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

### 先序遍历： ###

首先访问根，再先序遍历左子树，最后先序遍历右子树。

示例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center]

递归方法实现：

按照输出根结点，然后左子树递归输出，右子树递归输出。

void preOrder(BiTree *tree){
        
    	if(!tree) return ;//结束条件为该节点为空
    	cout<<tree->data<<" ";
    	preOrder(tree->lchild);
    	preOrder(tree->rchild);
    }

非递归方法（借助于栈实现）：

1.  将根节点（不为空）存入栈中
    
    循环内容：
2.  循环开始先输出栈顶，再出栈，
3.  先右子树进栈，后左子树进栈（利用栈先进先出）

void PreOrder(BiTree *tree){
        
    	BiTree *temp;
    	stack<BiTree*> stk;
        if(tree) stk.push(tree);
        while(!stk.empty()){
        
        	temp = stk.top();
        	stk.pop();
        	cout<<temp->data<<" ";
        	if(temp->rchild) stk.push(temp->rchild);
            if(temp->lchild) stk.push(temp->lchild);
        }
    }

[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
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/f8bc91cb6c224ec8a06d505c2ccd6fc7.png