二叉树遍历源代码

C++数据结构已知二叉树的前序遍历与中序遍历结果求后序遍历二叉树的遍历问题描述输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。

输入输入文件为tree.in，共两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。

树的结点一律用小写字母表示。

输出输出文件为tree.out，仅一行，表示树的后序遍历序列。

样例输入abdecdbeac样例输出debca--------------------------------------------------------------------- --------------------------------------------------------------------- #includeusing namespace std;struct tree{char data;tree *l,*r;};tree * create(char pre[],char in[]){tree *root;if(strlen(pre)==0) {root=NULL;}else{root=new tree;root->data=pre[0];char pre1[20];pre1[0]='\0';char pre2[20];pre2[0]='\0';char in1[20];in1[0]='\0';char in2[20];in2[0]='\0';int n=1;for(int i=0;i<strlen(in);i++){< p=""> if(in[i]!=pre[0]&&n==1){in1[i]=in[i];in1[i+1]='\0';}if(in[i]==pre[0]) n=2;if(in[i]!=pre[0]&&n==2){in2[i-strlen(in1)-1]=in[i];in2[i-strlen(in1)+1]='\0';}}for(int i=1;i<strlen(pre);i++){< p=""> if(i<strlen(in1)+1){< p="">pre1[i-1]=pre[i];pre1[i]='\0';}else {pre2[i-1-strlen(pre1)]=pre[i];pre2[i-strlen(pre1)]='\0';}}root->l=create(pre1,in1);root->r=create(pre2,in2);}return root;}void post(tree * root){if(root==NULL) return; else {post(root->l);post(root->r);cout<data;}}int main(){char pre[100];char in[100];cin>>pre;cin>>in;tree * root=create(pre,in); post(root);return 0;}</strlen(in1)+1){<></strlen(pre);i++){<></strlen(in);i++){<>。

一、软件背景介绍树的遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。

访问结点所做的操作依赖于具体的应用问题。

遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算的基础。

从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。

因此，在任一给定结点上，可以按某种次序执行三个操作：⑴访问结点本身（N），⑵遍历该结点的左子树（L），⑶遍历该结点的右子树（R）。

所以二叉树的遍历也包括三种：先序遍历，中序遍历，和后序遍历。

图1：程序显示结果二、核心算法思想二叉树的存储：在内存中为数组binary分配一个大小为63（0，0，0）的存储空间，所有数组元素初始化为0，用来存放二叉树。

每三个连续的数组地址存放一个节点：第一个地址存放节点的值；第二个地址存放有无左孩子的信息，如果有则将其置为1，否则为0；第三个地址存放有无右孩子的信息，如果有则将其置为1，否则为0。

将binary的首址偏移赋给si，cx初始化为0用来计数，用回车代表输入的为空，即没有输入。

按先根存储的方式来存二叉树，首先输入一个字符，若为回车则退出程序，否则cx+3且调用函数root。

然后该结点若有左孩子，调用leftchild函数，置该结点标志即第二个地址中的0为1，该结点进栈，再存储左孩子结点，递归调用左右，若没有左孩子，看有没有右孩子，若有，则调用rightchild置该结点标志位即上第三个地址中的0为1，然后该结点进栈，再存储右孩子结点，递归调用左右，整个用cx计数，数组binary中每多一个节点，cx加3。

此存储方式正好符合先序遍历思想。

遍历二叉树的执行踪迹：三种递归遍历算法的搜索路线相同，具体线路为：从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途径三次，最后回到根结点。

二叉树的遍历有常用的三种方法，分别是：先根次序、中根次序、后根次序。

为了验证这几种遍历算法的区别，本次的实验将会实现所有的算法。

叉树的随机生成及其遍历张 zhaohan 10804XXXXX2010/6/12问题重述利用随机函数产生50个(不大于1 00且各不相同的)随机整数，用这些整数来生成一棵二叉树，分别对二叉树进行先根遍历，中根遍历和后根遍历并输出树中结点元素序列。

程序设计(一) 需求分析：•问题的定义与要求： 1 、产生50个不大于100且各不相同的随机整数 (由系统的随机函数生成并对100取模)；2、先根遍历并输出结果；3、中根遍历并输出结果；4、后根遍历并输出结果；按层次浏览二叉树结5、点；6、退出程序。

•俞入：所需功能，选项为1〜6。

•输出：按照用户功能选择输出结果。

•限制：输入的功能选择在1〜6之间，否则无回应。

•模块功能及要求：RandDif(): 生成50个随机不大于100的整数，每次生成不同随机整数。

CreateBitree(): 给数据结点生成二叉树，使每个结点的左右儿子指针指向左右儿子。

NRPreOrder(): 非递归算法的先根遍历。

inOrderTraverse(): 递归算法的中根遍历。

P ostOrderTraverseO：递归算法的后根遍历。

Welcome(): 欢迎窗口。

Menu()：菜单。

Goodbye()：再见窗口。

(二) 概要设计：首先要生成二叉树，由于是对随机生成的50个数生成二叉树，故可以采取顺序存储的方式，对结点的左右儿子进行赋值。

生成的二叉树是完全二叉树。

先根遍历的非递归算法：1、根结点进栈2、结点出栈，被访问3、结点的右、左儿子（非空）进栈4、反复执行2、3 ，至栈空为止。

先根遍历的算法流程图：根结点进栈( a[0]=T->boot,p=a[0] ) 访问结点printf(*p)右儿子存在则进栈a[i]=(*p).rchild; i++;左儿子存在则进栈a[i]=(*p).rchild; i++;栈顶降低top--：i--;p=a[i];栈非空while(i>-1)返回中根遍历的递归算法流程图：T为空Return;inOrderTraverse(T->lchild)Printf(T->data) inOrderTraverse(T->rchild)返回后根遍历的递归算法流程图：T为空Return;inOrderTraverse(T->lchild) inOrderTraverse(T->rchild)Printf(T->data)返回遍历输出均按链式存储。

二叉树的随机生成及其遍历张zhaohan 10804XXXXX2010/6/12问题重述利用随机函数产生50个(不大于100且各不相同的)随机整数，用这些整数来生成一棵二叉树，分别对二叉树进行先根遍历，中根遍历和后根遍历并输出树中结点元素序列。

程序设计(一)需求分析：●问题的定义与要求：1、产生50个不大于100且各不相同的随机整数（由系统的随机函数生成并对100取模）；2、先根遍历并输出结果；3、中根遍历并输出结果；4、后根遍历并输出结果；5、按层次浏览二叉树结点；6、退出程序。

●输入：所需功能，选项为1～6。

●输出：按照用户功能选择输出结果。

●限制：输入的功能选择在1～6之间，否则无回应。

●模块功能及要求：RandDif():生成50个随机不大于100的整数，每次生成不同随机整数。

CreateBitree():给数据结点生成二叉树，使每个结点的左右儿子指针指向左右儿子。

NRPreOrder():非递归算法的先根遍历。

inOrderTraverse():递归算法的中根遍历。

PostOrderTraverse():递归算法的后根遍历。

Welcome():欢迎窗口。

Menu():菜单。

Goodbye():再见窗口。

(二)概要设计：首先要生成二叉树，由于是对随机生成的50个数生成二叉树，故可以采取顺序存储的方式，对结点的左右儿子进行赋值。

生成的二叉树是完全二叉树。

先根遍历的非递归算法：1、根结点进栈2、结点出栈，被访问3、结点的右、左儿子（非空）进栈4、反复执行2、3 ，至栈空为止。

先根遍历的算法流程图：根结点进栈（a[0]=T->boot,p=a[0]）访问结点printf(*p)右儿子存在则进栈a[i]=(*p).rchild; i++;左儿子存在则进栈a[i]=(*p).rchild; i++;栈顶降低top--：i--;p=a[i];栈非空while(i>-1)返回中根遍历的递归算法流程图：T为空YNReturn;inOrderTraverse(T->lchild)Printf(T->data)inOrderTraverse(T->rchild)返回后根遍历的递归算法流程图：T为空YNReturn;inOrderTraverse(T->lchild)inOrderTraverse(T->rchild)Printf(T->data)返回遍历输出均按链式存储。

二叉树c语言实现完整代码二叉树是一种非常常见的数据结构，它由节点和边组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。

在计算机科学中，二叉树被广泛应用于搜索、排序、编译器等领域。

本文将介绍如何使用C语言实现二叉树的完整代码。

我们需要定义二叉树的节点结构体。

每个节点包含三个成员变量：数据、左子节点和右子节点。

代码如下：```struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;};```接下来，我们需要实现二叉树的基本操作，包括创建节点、插入节点、删除节点、查找节点等。

这些操作可以通过递归实现。

代码如下：```// 创建节点struct TreeNode* createNode(int val) {struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));node->val = val;node->left = NULL;node->right = NULL;return node;}// 插入节点struct TreeNode* insertNode(struct TreeNode* root, int val) {if (root == NULL) {return createNode(val);}if (val < root->val) {root->left = insertNode(root->left, val);} else {root->right = insertNode(root->right, val);}return root;}// 删除节点struct TreeNode* deleteNode(struct TreeNode* root, int val) {if (root == NULL) {return NULL;}if (val < root->val) {root->left = deleteNode(root->left, val);} else if (val > root->val) {root->right = deleteNode(root->right, val);} else {if (root->left == NULL) {struct TreeNode* temp = root->right;free(root);return temp;} else if (root->right == NULL) {struct TreeNode* temp = root->left;free(root);return temp;}struct TreeNode* temp = findMin(root->right); root->val = temp->val;root->right = deleteNode(root->right, temp->val); }return root;}// 查找节点struct TreeNode* searchNode(struct TreeNode* root, int val) {if (root == NULL || root->val == val) {return root;}if (val < root->val) {return searchNode(root->left, val);} else {return searchNode(root->right, val);}}// 查找最小节点struct TreeNode* findMin(struct TreeNode* root) {while (root->left != NULL) {root = root->left;}return root;}```我们需要实现二叉树的遍历操作，包括前序遍历、中序遍历和后序遍历。

⼆叉树遍历（前中后序遍历，三种⽅式）⽬录刷题中碰到⼆叉树的遍历，就查找了⼆叉树遍历的⼏种思路，在此做个总结。

对应的LeetCode题⽬如下：，，，接下来以前序遍历来说明三种解法的思想，后⾯中序和后续直接给出代码。

⾸先定义⼆叉树的数据结构如下：//Definition for a binary tree node.struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};前序遍历，顺序是“根-左-右”。

使⽤递归实现：递归的思想很简单就是我们每次访问根节点后就递归访问其左节点，左节点访问结束后再递归的访问右节点。

代码如下：class Solution {public:vector<int> preorderTraversal(TreeNode* root) {if(root == NULL) return {};vector<int> res;helper(root,res);return res;}void helper(TreeNode *root, vector<int> &res){res.push_back(root->val);if(root->left) helper(root->left, res);if(root->right) helper(root->right, res);}};使⽤辅助栈迭代实现：算法为：先把根节点push到辅助栈中，然后循环检测栈是否为空，若不空，则取出栈顶元素，保存值到vector中，之后由于需要想访问左⼦节点，所以我们在将根节点的⼦节点⼊栈时要先经右节点⼊栈，再将左节点⼊栈，这样出栈时就会先判断左⼦节点。

代码如下：class Solution {public:vector<int> preorderTraversal(TreeNode* root) {if(root == NULL) return {};vector<int> res;stack<TreeNode*> st;st.push(root);while(!st.empty()){//将根节点出栈放⼊结果集中TreeNode *t = st.top();st.pop();res.push_back(t->val);//先⼊栈右节点，后左节点if(t->right) st.push(t->right);if(t->left) st.push(t->left);}return res;}};Morris Traversal⽅法具体的详细解释可以参考如下链接：这种解法可以实现O(N)的时间复杂度和O(1)的空间复杂度。

#include <stdio.h>#include <iostream>#include <queue>#include <stack>#include <malloc.h>#define SIZE 100using namespace std;typedef struct BiTNode //定义二叉树节点结构{char data; //数据域struct BiTNode *lchild,*rchild; //左右孩子指针域}BiTNode,*BiTree;int visit(BiTree t);void CreateBiTree(BiTree &T); //生成一个二叉树void PreOrder(BiTree); //递归先序遍历二叉树void InOrder(BiTree); //递归中序遍历二叉树void PostOrder(BiTree); //递归后序遍历二叉树void InOrderTraverse(BiTree T); //非递归中序遍历二叉树void PreOrder_Nonrecursive(BiTree T);//非递归先序遍历二叉树void LeverTraverse(BiTree T);//非递归层序遍历二叉树//主函数void main(){BiTree T;char j;int flag=1;//---------------------程序解说-----------------------printf("本程序实现二叉树的操作。

\n");printf("叶子结点以空格表示。

\n");printf("可以进行建立二叉树，递归先序、中序、后序遍历，非递归先序、中序遍历及非递归层序遍历等操作。

\n");//----------------------------------------------------printf("\n");printf("请建立二叉树。

C语言实现二叉树的前序遍历二叉树是一种非线性数据结构，由节点和边组成。

每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树可以用递归或迭代的方法进行前序、中序和后序遍历。

在本文中，我们将重点介绍如何使用递归方法实现二叉树的前序遍历。

前序遍历是指首先访问根节点，然后按照左子树->右子树的顺序遍历二叉树。

在实际编程中，我们可以通过递归的方式来遍历每个节点。

首先，让我们定义二叉树的节点结构。

```c//定义二叉树节点结构struct TreeNodeint val; // 节点值struct TreeNode* left; // 左子节点指针struct TreeNode* right; // 右子节点指针};```接下来，让我们实现二叉树的前序遍历函数。

```c//二叉树的前序遍历函数void preorderTraversal(struct TreeNode* root)if (root == NULL) { // 如果根节点为空，则返回return;}//首先打印根节点的值printf("%d ", root->val);//然后递归遍历左子树preorderTraversal(root->left);//最后递归遍历右子树preorderTraversal(root->right);```首先，我们判断根节点是否为空。

如果为空，表示已经遍历到叶子节点，直接返回。

然后，我们打印当前节点的值。

接下来，我们递归调用前序遍历函数，遍历左子树和右子树。

接下来，我们可以通过构建一个简单的二叉树来测试我们的前序遍历函数。

```c//创建一个二叉树用于测试前序遍历struct TreeNode* createTestTrestruct TreeNode* root = (structTreeNode*)malloc(sizeof(struct TreeNode)); // 创建根节点root->val = 1;root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode)); // 创建左子节点root->left->val = 2;root->left->left = NULL;root->left->right = NULL;root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode)); // 创建右子节点root->right->val = 3;root->right->left = NULL;root->right->right = NULL;return root;```在主函数中，我们创建一个测试二叉树，并调用前序遍历函数进行遍历。

集合了树的各种算法，已经运行过，本人亲自所写，先序，后序，等全包括#include<stdio.h>#include<malloc.h>#define Max 100typedef int Status;typedef struct BiTNode{char data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;int count;Status CreatBiTree(BiTree *bt) /*1.按先序遍历序列创造二叉树的二叉链表*/ {char ch;getchar();scanf("%c",&ch);if (ch == ' '){*bt = NULL;}else{*bt = (BiTree)malloc(sizeof(BiTNode));(*bt)->data = ch;printf("\n\t请输入%c结点的左孩子:",(*bt)->data);CreatBiTree(&((*bt)->lchild));printf("\n\t请输入%c结点的右孩子:",(*bt)->data);CreatBiTree(&((*bt)->rchild));}return 1;}void PreOrder(BiTree bt) /*2.先序遍历二叉树*/{if (bt != NULL){printf("%c\n",bt->data);PreOrder(bt->lchild);PreOrder(bt->rchild);}}void InOrder(BiTree bt) /*3.中序遍历二叉树*/{if (bt != NULL){InOrder(bt->lchild);printf("%c\n",bt->data);InOrder(bt->rchild);}}void PostOrder(BiTree bt) /*4.后序遍历二叉树*/{if (bt != NULL){PostOrder(bt->lchild);PostOrder(bt->rchild);printf("%c\n",bt->data);}}void PreOrderLeaf(BiTree bt) /*5.输出所有的叶子结点*/{if (bt != NULL){if ((bt->lchild == NULL) && (bt->rchild == NULL)){printf("%c\n",bt->data);}PreOrderLeaf(bt->lchild);PreOrderLeaf(bt->rchild);}}Status Leaf(BiTree bt) /*6.统计叶子结点数目，即度为零的结点数目*/ {if (bt == NULL){count = 0;}else if ((bt->lchild == NULL) && (bt->rchild == NULL)){count = 1;}else{count = Leaf(bt->lchild) + Leaf(bt->rchild);}return count;}void Degree1Node(BiTree bt) /*7.输出度为一的结点*/{if (bt != NULL){if (((bt->lchild != NULL) || (bt->rchild != NULL))&& (!((bt->lchild != NULL) && (bt->rchild != NULL)))) {printf("%c\n",bt->data);}Degree1Node(bt->lchild);Degree1Node(bt->rchild);}}void Degree2Node(BiTree bt) /*8.输出度为二的结点*/{if ( bt != NULL){if ((bt->lchild != NULL) && (bt->rchild != NULL)){printf("%c\n",bt->data);}Degree2Node(bt->lchild);Degree2Node(bt->rchild);}}Status CountNode(BiTree bt) /*9.统计二叉树中结点的总数*/{if (bt == NULL){return 0;}else{count++;CountNode(bt->lchild);CountNode(bt->rchild);return count;}}Status TreeDepth(BiTree bt) /*10.求二叉树的深度*/{int ldep, rdep;if (bt == NULL){return 0;}else{ldep = TreeDepth(bt->lchild);rdep = TreeDepth(bt->rchild);if (ldep > rdep){return (ldep +1);}else{return (rdep + 1);}}}void PrintTree(BiTree bt, int nlayer) /*11.按树状打印二叉树*/ {if (bt == NULL) /*如果是空则直接退出函数*/{return;}PrintTree(bt->rchild,nlayer + 1);for ( int i = 0; i < nlayer; i++){printf("----");}printf("%c\n",bt->data);PrintTree(bt->lchild,nlayer + 1);}void PreOrderTree(BiTree bt) /*12.非递归先序遍历*/BiTree Stack[Max];BiTree p = bt;int top = 0;while (p != NULL || top != 0){if (p != NULL){printf("%c",p->data);top++;Stack[top] = p;p = p->lchild;}else{p = Stack[top];top--;p = p->rchild;}}}void InOrderTree(BiTree bt) /*13.非递归中序遍历*/ {BiTree Stack[Max];BiTree p = bt;int top = 0;do{while (p != NULL){top++;Stack[top] = p;p = p->lchild;}if (top != 0){p = Stack[top];top--;printf("%c",p->data);p = p->rchild;}}while ((p != NULL) || (top != 0));void PostOrderTree(BiTree bt) /*14.非递归后序遍历*/ {BiTree p, q;int top = 0;BiTree Stack[Max];q = NULL;p = bt;while ((p != NULL) || (top != 0)){while (p != NULL){top++;Stack[top] = p;p = p->lchild;}if (top > 0){p = Stack[top];if ((p->rchild == NULL) || (p->rchild == q)){printf("%c",p->data);q = p;p = NULL;top--;}else{p = p->rchild;}}}}void LayerOrder(BiTree bt) /*15.层次遍历*/{int front,rear;BiTree Q[Max];front = 0;rear = front;BiTree r, s, p;r = s = p = bt;if (p == NULL) return;Q[rear] = p;rear++;while (front != rear){s = r = Q[front];printf("%c",Q[front]->data);front++;if (r->lchild){Q[rear] = r->lchild;rear++;}if (s->rchild){Q[rear] = s->rchild;rear++;}}}int main(){BiTree bt;int choice;int i,j,k;int nlayer = 1;printf("请用数字选择操作：\n");printf("1.按先序序列创建二叉树（二叉链表）\n");printf("2.递归先序遍历二叉树\n");printf("3.递归中序遍历二叉树\n");printf("4.递归后序遍历二叉树\n");printf("5.输出叶子结点（即度为零的结点）\n");printf("6.统计叶子结点数目\n");printf("7.输出度为一的结点\n");printf("8.输出度为二的结点\n");printf("9.统计二叉树中结点总数\n");printf("10.求二叉树的高度（即深度）\n");printf("11.按树状打印二叉树\n");printf("12.非递归先序遍历二叉树\n");printf("13.非递归中序遍历二叉树\n");printf("14.非递归后序遍历二叉树\n");printf("15.层次遍历二叉树\n");printf("0.则退出\n");while (1){printf("请输入你要执行的操作(0-15):");scanf("%d",&choice);if (choice == 0){break;}else switch (choice){case 1 : printf("\n请输入按先序建立二叉树的结点序列：");printf("\n说明：逐个输入，输入空格代表后继结点为空，按回车输入下一个结点。