二叉樹的遍歷

????1、二叉樹的先序遍歷（樹根——左子樹——右子樹）

????2、二叉樹的中序遍歷（左子樹——樹根——右子樹）

????3、二叉樹的后序遍歷（左子樹——右子樹——樹根）

以上一般使用遞歸實現(xiàn)

????4、二叉樹的層序遍歷（一般使用隊列實現(xiàn)）

????5、根據(jù)遍歷還原樹

練習(xí)：

? ? ????先——?ABDTFONECKXS

????????中——DTOFNBACESXK

????????后——ONFTDBCSXKEA

????????層序遍歷——ABEDCKTXFSON

生成隨機二叉樹：

#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 preorder(node *root){

????if(root == NULL){//結(jié)點為空

????????return ;

????}

????printf("%c", root->data);//根結(jié)點

????preorder(root->left);//左子樹

????preorder(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[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));//基于時間生成隨機數(shù)

????int n;

????scanf("%d",&n);

????node *root = null;

????for(int i = 0; i < n; i++){//生成隨機樹

????????int x = rand() % 26;

????????while(mark[x] == 1){

????????????x =?rand() % 26;

????????}

????????mark[x] = 1;

????????root = insert_node(root, 'A' + x);

?????}

????preorder(root);

????printf("\n");

????inorder(root);

????printf("\n");

??? postorder(root);

????printf("\n");

????levelorder(root);

????return 0;

}

運行結(jié)果：

根據(jù)遍歷還原二叉樹

? ? 根據(jù)先序遍歷和中序遍歷還原樹——先序遍歷第一個元素必為樹根，在中序遍歷中找樹根，分左子樹、右子樹兩部分分別處理；

????根據(jù)中序遍歷和后序遍歷還原樹——后序遍歷最后一個元素必為樹根，中序遍歷中找樹根，分左子樹、右子樹兩部分分別處理；

????根據(jù)先序遍歷和后序遍歷不能還原樹；

????根據(jù)中序遍歷和層序遍歷還原樹

練習(xí)：

????先序遍歷——CZAFLYXMGP

????中序遍歷——FALZYXCGMP

????還原二叉樹并輸出后序遍歷。

????