C语言实现二叉树的遍历（数据结构）

2023-09-25 13:55| 来源: 网络整理| 查看: 265

二叉树的定义

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树

二叉树的性质

在这里插入图片描述

二叉树遍历

二叉树有三种遍历方式，分别为先序遍历、中序遍历、后序遍历

先序遍历：（1）先访问根节点。（2）再访问左子树。（3）最后访问右子树。中序遍历：（1）先访问左子树。（2）再访问根节点。（3）最后访问右子树。后序遍历：（1）先访问左子树。（2）再访问右子树。（3）最后访问根节点。

比如如下的二叉树在这里插入图片描述

先序遍历结果为 ABCDEFG

中序遍历结果为 CBEDAFG

后序遍历结果为 CEDBGFA

二叉树结构 typedef struct binarytreenode { int data; struct binarytreenode *Lnode; struct binarytreenode *Rnode; } BiTNode,*BiTree; 创建二叉树 void CreateBiTree(BiTree *T) { char ch; scanf("%c",&ch); if(ch == '#') { *T = NULL; } else { *T = (BiTree)malloc(sizeof(BiTNode)); if(!*T){return;} (*T)->data = ch; CreateBiTree(&(*T)->Lnode); CreateBiTree(&(*T)->Rnode); } } 三种遍历 //二叉树的先序遍历 void PreOrderTraverse(BiTree T) { if(T == NULL) return; printf("%c ",T->data); PreOrderTraverse(T->Lnode); PreOrderTraverse(T->Rnode); } //二叉树的中序遍历 void InOrderTraverse(BiTree T) { if(T == NULL) return; InOrderTraverse(T->Lnode); printf("%c ",T->data); InOrderTraverse(T->Rnode); } //二叉树的后序遍历 void PostOrderTraverse(BiTree T) { if(T == NULL) return; PostOrderTraverse(T->Lnode); PostOrderTraverse(T->Rnode); printf("%c ",T->data); } //二叉树的层次遍历 void LevelOrderTraverse(BiTree T) { if(T == NULL) return; Q_Push(T); //取树的第一个节点加入队列 while(!Q_empty()){ //树不为空时 BiTree tmp = Q_Pop(T); //删除队列的第一个元素 printf("%c ",tmp->data); if(tmp->Lnode) Q_Push(tmp->Lnode); //取队列的左子树 if(tmp->Rnode) Q_Push(tmp->Rnode);//取队列的右子树 } } 层次遍历 /* 完整代码 */ #include #include #include #define MaxSize 100 struct tree { int data; struct tree* left; struct tree* right; }; typedef struct queue{ struct tree* numQ[MaxSize]; int front; int rear; }Queue; Queue Q; void initilize() { //初始化队列 Q.front = 0; Q.rear = 0; } void Push(struct tree* root) { //入队 Q.numQ[++Q.rear] = root; } struct tree* Pop() { //出队 return Q.numQ[++Q.front]; } int empty() { //判断对列是否为空 return Q.rear == Q.front; } struct tree* creatTree (struct tree* root) { int value; scanf("%d", &value); if (value == -1) return NULL; root = (struct tree*)malloc(sizeof(struct tree)); root->data = value; printf("请输入%d的左子树：", root->data); root->left = creatTree(root->left); printf("请输入%d的右子树：", root->data); root->right = creatTree(root->right); return root; } void LevelOrderTraversal (struct tree* root) { //二叉树的层次遍历 struct tree* temp; Push(root); while (!empty()) { temp = Pop(); printf("%d ", temp->data); //输出队首结点 if (temp->left) //把Pop掉的结点的左子结点加入队列 Push(temp->left); if (temp->right) 把Pop掉的结点的右子结点加入队列 Push(temp->right); } } int main() { printf("请输入头节点："); struct tree* root = creatTree(root); initilize(); //初始化队列 LevelOrderTraversal(root); putchar('\n'); return 0; } 完整代码 //#include #include #include #include #include #define MaxSize 100 using namespace std; typedef struct binarytreenode { int data; struct binarytreenode *Lnode; struct binarytreenode *Rnode; } BiTNode,*BiTree; typedef struct queue{ BiTree numQ[MaxSize]; int front; int rear; }Queue; Queue Q; void Q_initilize() { Q.front = 0; Q.rear = 0; } void Q_Push(BiTree root) { Q.numQ[++Q.rear] = root; } BiTree Q_Pop(BiTree root) { return Q.numQ[++Q.front] ; } int Q_empty() { //判断对列是否为空 return Q.rear == Q.front; } void CreateBiTree(BiTree *T) { char ch; scanf("%c",&ch); if(ch == '#') { *T = NULL; } else { *T = (BiTree)malloc(sizeof(BiTNode)); if(!*T){return;} (*T)->data = ch; CreateBiTree(&(*T)->Lnode); CreateBiTree(&(*T)->Rnode); } } //二叉树的先序遍历 void PreOrderTraverse(BiTree T) { if(T == NULL) return; printf("%c ",T->data); PreOrderTraverse(T->Lnode); PreOrderTraverse(T->Rnode); } //二叉树的中序遍历 void InOrderTraverse(BiTree T) { if(T == NULL) return; InOrderTraverse(T->Lnode); printf("%c ",T->data); InOrderTraverse(T->Rnode); } //二叉树的后序遍历 void PostOrderTraverse(BiTree T) { if(T == NULL) return; PostOrderTraverse(T->Lnode); PostOrderTraverse(T->Rnode); printf("%c ",T->data); } //二叉树的层次遍历 void LevelOrderTraverse(BiTree T) { if(T == NULL) return; Q_Push(T); while(!Q_empty()){ BiTree tmp = Q_Pop(T); printf("%c ",tmp->data); if(tmp->Lnode) Q_Push(tmp->Lnode); if(tmp->Rnode) Q_Push(tmp->Rnode); } } int main() { BiTree T; CreateBiTree(&T); printf("前序遍历结果为 :\n"); PreOrderTraverse(T); printf("\n\n中序遍历结果为 :\n"); InOrderTraverse(T); printf("\n\n后序遍历结果为 :\n"); PostOrderTraverse(T); printf("\n\n层次遍历结果为 :\n\n"); LevelOrderTraverse(T); return 0; } 补充：

（1）建立二叉树时，这里是以前序遍历的方式，输入的是扩展二叉树，也就是要告诉计算机什么是叶结点，否则将一直递归，当输入“#”时，指针指向NULL，说明是叶结点。

（2）输入的时候一定要注意因为有缓冲区的原因，用scanf输入的话，一定要把所有要输入的数据一次性输入，再回车

（3）不要输入一个数据回车一次，这样就永远也走不出递归函数了，界面一直停留在输入界面，或者想一个一个输入用cin

如图为扩展二叉树：（前序遍历为：ABC##DE###F#G##）

在这里插入图片描述

【本文地址】

公司简介

联系我们