二叉树的遍历

ゝ一纸荒年。 2022-02-05 09:53 200阅读 0赞

一 先序遍历

#include<iostream>
    #include<cstdio>
    using namespace std;
    typedef struct node{
    	int data;//存储数据 
        struct node* lchild;
    	struct node* rchild;//申请左右孩子 
    }Node;//改一下名字，便于以后使用； 
    void printTree(Node*n1){
    	if(n1!=NULL){
    		printf("%d\n",n1->data);
    		printTree(n1->lchild);
    		printTree(n1->rchild);
    	}
    }
    int main(){
    	Node n1;
    	Node n2;
    	Node n3;
    	Node n4;
    	Node n5; 
    	n1.data =5;
    	n2.data =4;
    	n3.data =3;
    	n4.data =2;
    	n5.data =1;
    	n1.lchild =&n2;
    	n1.rchild =&n5;
    	n2.lchild =&n3;
    	n2.rchild =&n4;
    	n3.lchild =NULL;
    	n3.rchild =NULL;
    	n4.lchild =NULL;
    	n4.rchild =NULL;
    	n5.lchild =NULL;
    	n5.rchild =NULL;
    	printTree(&n1);
    	return 0;
    } 
    ```![在这里插入图片描述](https://img-blog.csdnimg.cn/20190505153825592.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9fbGVf,size_16,color_FFFFFF,t_70)
    最终结果就是5 4 3 2 1
    二 中序遍历
    简单介绍一下中序遍历，就是从最开始的根节点开始向下搜索，把全部的左边先走完然后再走根节点最后走右节点，对于上面的图最后输出的结果是3 4 2 5 1；

\#include  
\#include  
using namespace std;  
typedef struct node\{  
int data;//存储数据  
struct node\* lchild;  
struct node\* rchild;//申请左右孩子  
\}Node;//改一下名字，便于以后使用；  
void printTree(Node\*n1)\{  
if(n1!=NULL)\{  
printTree(n1->lchild);  
printf("%d\\n",n1->data);//just be different in this place  
printTree(n1->rchild);  
\}  
\}  
int main()\{  
Node n1;  
Node n2;  
Node n3;  
Node n4;  
Node n5;  
n1.data =5;  
n2.data =4;  
n3.data =3;  
n4.data =2;  
n5.data =1;  
n1.lchild =&n2;  
n1.rchild =&n5;  
n2.lchild =&n3;  
n2.rchild =&n4;  
n3.lchild =NULL;  
n3.rchild =NULL;  
n4.lchild =NULL;  
n4.rchild =NULL;  
n5.lchild =NULL;  
n5.rchild =NULL;  
printTree(&n1);  
return 0;  
\}