知识点整理:
1、前序遍历:根-左-右
2、中序遍历:左-根-右
3、后序遍历:左-右-根
4、层序遍历:从树根出发一层一层从左往右遍历
代码展示:
#include<stdio.h>#include<stdlib.h>#include<time.h>typedef struct node{char data;struct node *left,*right;}Node;Node *insert_node(Node *root,char c){if(root==NULL){Node *p=(Node *)malloc(sizeof(Node));p->data=c;p->left=p->right=NULL;return p;}int x=rand()%2;if(x==0){//往左子树插入root->left=insert_node(root->left,c);}else root->right=insert_node(root->right,c);return root;}void perorder(Node *root){//前序遍历if(root==NULL)//当前结点为空return ;printf("%c",root->data);//自身perorder(root->left);//左子树perorder(root->right);//右子树}void inorder(Node *root){//中序遍历if(root==NULL)//当前结点为空return ;inorder(root->left);//左子树printf("%c",root->data);//自身inorder(root->right);//右子树}void postorder(Node *root){//后序遍历if(root==NULL)//当前结点为空return ; postorder(root->left);//左子树postorder(root->right);//右子树printf("%c",root->data);//自身}void levelorder(Node *root){//层序遍历Node *num[30];//队列int front=0,rear=1;//num[front]、num[rear]首、尾指针num[0]=root;while(front!=rear){Node *p=num[front];front++;printf("%c",p->data);if(p->left!=NULL) num[rear++]=p->left;if(p->right!=NULL) num[rear++]=p->right;}printf("\n");}int main(){srand(time(0));int n,mark[26];//标记数组,避免产生重复字母scanf("%d",&n);//二叉树的结点数Node *root=NULL;for(int i=0;i<n;i++){int x=rand()%26;//使'A'+x在26个字母范围内while(mark[x]==1)x=rand()%26;//避免重复mark[x]=1;//标记已出现的字母root=insert_node(root,'A'+x);//随机生成字母二叉树}printf("先序遍历: ");perorder(root);printf("\n中序遍历: ");inorder(root);printf("\n后序遍历: ");postorder(root);printf("\n层序遍历: ");levelorder(root);}
运行结果示例:
先序遍历: HBZUDA中序遍历: BHDUZA后序遍历: BDUAZH层序遍历: HBZUAD
该示例二叉树如下图所示: