c语言实现二叉树的建立和遍历（C语言二叉树的遍历）

目录

• 这里给一个样例树：
• 总结

这里给一个样例树：

代码：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

#include <stdio.h> #include <string.h> #include <stdlib.h> /* 二叉树的二叉链表结点结构定义 */ typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree T=NULL; /* 先序遍历建立一个二叉树 */ void Create (BiTree *T) // 二级指针改变地址的地址 { char ch; scanf("%c",&ch); if(ch=='#') *T=NULL; else { *T=(BiTree)malloc(sizeof(BiTNode)); if(!*T) return ; else { (*T)->data=ch; Create(&(*T)->lchild); Create(&(*T)->rchild); } } } /* 二叉树的前序递归遍历算法 */ void PreOrderTraverse(BiTree T) { if(T==NULL) return ; printf("%c ",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } /* 二叉树的中序递归遍历算法 */ void InOrderTraverse(BiTree T) { if(T==NULL) return ; InOrderTraverse(T->lchild); printf("%c ",T->data); InOrderTraverse(T->rchild); } /* 二叉树的后序递归遍历算法 */ void PostOrderTraverse(BiTree T) { if(T==NULL) return ; PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%c ",T->data); } int main() { printf("请按先序遍历的结果输入树，例如：ABDH#K###E##CFI###G#J##\n"); Create(&T); printf("先序遍历的结果为：\n"); PreOrderTraverse(T); printf("\n"); printf("中序遍历的结果为：\n"); InOrderTraverse(T); printf("\n"); printf("后序遍历的结果为：\n"); PostOrderTraverse(T); printf("\n"); return 0; }

输出结果如下

PS：下面是一个用C++里面的取引用代替了二级指针

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

#include<bits/stdc++.h> using namespace std; /* 二叉树的二叉链表结点结构定义 */ typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree T=NULL; /* 先序遍历建立一个二叉树 */ void Create (BiTree &T) // C++取引用 { char ch; scanf("%c",&ch); if(ch=='#') T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode)); if(!T) return ; else { T->data=ch; Create(T->lchild); Create(T->rchild); } } } /* 二叉树的前序递归遍历算法 */ void PreOrderTraverse(BiTree T) { if(T==NULL) return ; printf("%c ",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } /* 二叉树的中序递归遍历算法 */ void InOrderTraverse(BiTree T) { if(T==NULL) return ; InOrderTraverse(T->lchild); printf("%c ",T->data); InOrderTraverse(T->rchild); } /* 二叉树的后序递归遍历算法 */ void PostOrderTraverse(BiTree T) { if(T==NULL) return ; PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%c ",T->data); } int main() { printf("请按先序遍历的结果输入树，例如：ABDH#K###E##CFI###G#J##\n"); Create(T); printf("先序遍历的结果为：\n"); PreOrderTraverse(T); printf("\n"); printf("中序遍历的结果为：\n"); InOrderTraverse(T); printf("\n"); printf("后序遍历的结果为：\n"); PostOrderTraverse(T); printf("\n"); return 0; }

PS:遍历的PLus版，想要的自取。

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205

#include <iostream> #include <queue> #include <stack> #include <cstdio> #include <cstdlib> using namespace std; const int cmax=1e2+5; typedef struct BiTNode { char data; struct BiTNode *lchild ,*rchild; }BiTNode,*BiTree; void CreateBiTree (BiTree &T) { char ch; scanf("%c",&ch); if(ch=='#') T=NULL; else { T=(BiTNode *)malloc(sizeof(BiTNode)); T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return ; } void PreOrder(BiTree T) { if(T) { printf("%c",T->data); PreOrder(T->lchild); PreOrder(T->rchild); } } void InOrder(BiTree T) { if(T) { InOrder(T->lchild); printf("%c",T->data); InOrder(T->rchild); } } void PostOrder(BiTree T) { if(T) { PostOrder(T->lchild); PostOrder(T->rchild); printf("%c",T->data); } } // 非递归中序遍历 void InOrderTraverse(BiTree T) { stack<BiTree> S; BiTree p; S.push(T); while(!S.empty()) { p=new BiTNode; while((p=S.top())&&p) S.push(p->lchild); S.pop(); if(!S.empty()) { p=S.top(); S.pop(); cout<<p->data<<" "; S.push(p->rchild); } } } // 先序非递归遍历 void PreOrder_Nonrecursive(BiTree T) { stack<BiTree> S; BiTree p; S.push(T); while(!S.empty()) { while((p=S.top())&&p) { cout<<p->data<<" "; S.push(p->lchild); } S.pop(); if(!S.empty()) { p=S.top(); S.pop(); S.push(p->rchild); } } } int visit(BiTree T) { if(T) { printf("%c ",T->data); return 1; } else return 0; } // 非递归层次遍历 void LeverTraverse(BiTree T) { queue <BiTree> Q; BiTree p; p=T; if(visit(p)==1) Q.push(p); while(!Q.empty()) { p=Q.front(); Q.pop(); if(visit(p->lchild)==1) Q.push(p->lchild); if(visit(p->rchild)==1) Q.push(p->rchild); } } //主函数 int main() { BiTree T; char j; int flag=1; printf("本程序实现二叉树的操作。\n"); printf("叶子结点以#表示。\n"); printf("可以进行建立二叉树，递归先序、中序、后序遍历，非递归先序、中序遍历及非递归层序遍历等操作。\n"); printf("请建立二叉树。\n"); printf("建树将以三个空格后回车结束。\n"); printf("例如:1 2 3 4 5 6 (回车)\n\n"); CreateBiTree(T); //初始化队列 getchar(); printf("\n"); printf("请选择: \n"); printf("1.递归先序遍历\n"); printf("2.递归中序遍历\n"); printf("3.递归后序遍历\n"); printf("4.非递归中序遍历\n"); printf("5.非递归先序遍历\n"); printf("6.非递归层序遍历\n"); printf("0.退出程序\n"); while(flag) { scanf(" %c",&j); switch(j) { case '1':if(T) { printf("递归先序遍历二叉树:"); PreOrder(T); printf("\n"); } else printf("二叉树为空!\n"); break; case '2':if(T) { printf("递归中序遍历二叉树:"); InOrder(T); printf("\n"); } else printf("二叉树为空!\n"); break; case '3':if(T) { printf("递归后序遍历二叉树:"); PostOrder(T); printf("\n"); } else printf("二叉树为空!\n"); break; case '4':if(T) { printf("非递归中序遍历二叉树:"); InOrderTraverse(T); printf("\n"); } else printf("二叉树为空!\n"); break; case '5':if(T) { printf("非递归先序遍历二叉树:"); PreOrder_Nonrecursive(T); printf("\n"); } else printf("二叉树为空!\n"); break; case '6':if(T) { printf("非递归层序遍历二叉树:"); LeverTraverse(T); printf("\n"); } else printf("二叉树为空!\n"); break; default:flag=0;printf("程序运行结束，按任意键退出!\n"); } } }

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注服务器之家的更多内容！

原文链接：https://blog.csdn.net/weixin_45882303/article/details/107941789