#include <stdio.h>
#include <stdlib.h>
struct binode {
int data;
struct binode* lchild;
struct binode* rchild;
};
typedef struct binode* bitree;
typedef struct binode binode;
void creatbitree(bitree* T) {
int ch;
- scanf_s("%d", &ch);
(*T) = (bitree)malloc(sizeof(binode));
if (ch == -1)
(*T) = NULL;
if ((*T) == NULL)
return;
else
{
(*T)->data = ch;
creatbitree(&((*T)->lchild));
creatbitree((&(*T)->rchild));
}
}
int main() {
int* T;
T = (int*)malloc(sizeof(int));
creatbitree(T);
return;
}
uj5u.com熱心網友回復：
僅供參考：#include <locale.h>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct BiTNode {//二叉樹結點
char data; //資料
struct BiTNode *lchild,*rchild; //左右孩子指標
} BiTNode,*BiTree;
int nn=0;
int CreateBiTree(BiTree *T) {//按先序序列創建二叉樹
char data;
scanf("%c",&data);//按先序次序輸入二叉樹中結點的值（一個字符），‘#’表示空樹
if (data == '#') {
*T = NULL;
} else {
*T = (BiTree)malloc(sizeof(BiTNode)); nn++;
(*T)->data = data; //生成根結點
CreateBiTree(&(*T)->lchild);//構造左子樹
CreateBiTree(&(*T)->rchild);//構造右子樹
}
return 0;
}
void Visit(BiTree T) {//輸出
if (T->data != '#') {
printf("%c ",T->data);
}
}
void PreOrder(BiTree T) {//先序遍歷
if (T != NULL) {
Visit(T); //訪問根節點
PreOrder(T->lchild); //訪問左子結點
PreOrder(T->rchild); //訪問右子結點
}
}
void InOrder(BiTree T) {//中序遍歷
if (T != NULL) {
InOrder(T->lchild); //訪問左子結點
Visit(T); //訪問根節點
InOrder(T->rchild); //訪問右子結點
}
}
void PostOrder(BiTree T) {//后序遍歷
if (T != NULL) {
PostOrder(T->lchild); //訪問左子結點
PostOrder(T->rchild); //訪問右子結點
Visit(T); //訪問根節點
}
}
void PreOrder2(BiTree T) {//先序遍歷(非遞回)
//訪問T->data后，將T入堆疊，遍歷左子樹；遍歷完左子樹回傳時，堆疊頂元素應為T，出堆疊，再先序遍歷T的右子樹。
BiTree *stack=(BiTree *)malloc(nn*sizeof(BiTree));
int sp=0;
BiTree p = T;//p是遍歷指標
while (p || sp) { //堆疊不慷訓者p不空時回圈
if (p != NULL) {
stack[sp]=p;sp++; //存入堆疊中
printf("%c ",p->data); //訪問根節點
p = p->lchild; //遍歷左子樹
} else {
sp--;p=stack[sp]; //退堆疊
p = p->rchild; //訪問右子樹
}
}
free(stack);
}
void InOrder2(BiTree T) {//中序遍歷(非遞回)
//T是要遍歷樹的根指標，中序遍歷要求在遍歷完左子樹后，訪問根，再遍歷右子樹。
//先將T入堆疊，遍歷左子樹；遍歷完左子樹回傳時，堆疊頂元素應為T，出堆疊，訪問T->data，再中序遍歷T的右子樹。
BiTree *stack=(BiTree *)malloc(nn*sizeof(BiTree));
int sp=0;
BiTree p = T;//p是遍歷指標
while (p || sp) { //堆疊不慷訓者p不空時回圈
if (p != NULL) {
stack[sp]=p;sp++; //存入堆疊中
p = p->lchild; //遍歷左子樹
} else {
sp--;p=stack[sp]; //退堆疊
printf("%c ",p->data);
p = p->rchild; //訪問右子樹
}
}
free(stack);
}
typedef struct BiTNodePost{
BiTree biTree;
char tag;
} BiTNodePost,*BiTreePost;
void PostOrder2(BiTree T) {//后序遍歷(非遞回)
BiTreePost *stack=(BiTreePost *)malloc(nn*sizeof(BiTreePost));
int sp=0;
BiTree p = T;//p是遍歷指標
BiTreePost BT;
while (p != NULL || sp) {//堆疊不慷訓者p不空時回圈
while (p != NULL) {//遍歷左子樹
BT = (BiTreePost)malloc(sizeof(BiTNodePost));
BT->biTree = p;
BT->tag = 'L';//訪問過左子樹
stack[sp]=BT;sp++; //存入堆疊中
p = p->lchild;
}
while (sp && (stack[sp-1])->tag == 'R') {//左右子樹訪問完畢訪問根節點
sp--;BT=stack[sp]; //退堆疊
printf("%c ",BT->biTree->data);
free(BT);
}
if (sp) {//遍歷右子樹
BT=stack[sp-1];
BT->tag = 'R';//訪問過右子樹
p = BT->biTree;
p = p->rchild;
}
}
free(stack);
}
void LevelOrder(BiTree T) {//層次遍歷
BiTree p;
BiTree *queue;
int h=0,t=0,n=0;
if (T == NULL) return;
p=T;
queue=(BiTree *)malloc(nn*sizeof(BiTree));
queue[t]=p;t=(t+1)%10;n++;//根節點入隊
while (n) { //佇列不慷訓圈
p=queue[h]; //對頭元素出隊
printf("%c ",p->data); //訪問p指向的結點
h=(h+1)%10;n--; //退出佇列
if (p->lchild != NULL) {//左子樹不空，將左子樹入隊
queue[t]=p->lchild;t=(t+1)%10;n++;
}
if (p->rchild != NULL) {//右子樹不空，將右子樹入隊
queue[t]=p->rchild;t=(t+1)%10;n++;
}
}
free(queue);
}
int main() {
BiTree T;
setlocale(LC_ALL,"chs");
CreateBiTree(&T);
printf("先序遍歷 ：");PreOrder (T);printf("\n");
printf("先序遍歷(非遞回)：");PreOrder2 (T);printf("\n");
printf("\n");
printf("中序遍歷 ：");InOrder (T);printf("\n");
printf("中序遍歷(非遞回)：");InOrder2 (T);printf("\n");
printf("\n");
printf("后序遍歷 ：");PostOrder (T);printf("\n");
printf("后序遍歷(非遞回)：");PostOrder2(T);printf("\n");
printf("\n");
printf("層次遍歷 ：");LevelOrder(T);printf("\n");
return 0;
}
//ABC##DE#G##F###
//先序遍歷 ：A B C D E G F
//先序遍歷(非遞回)：A B C D E G F
//
//中序遍歷 ：C B E G D F A
//中序遍歷(非遞回)：C B E G D F A
//
//后序遍歷 ：C G E F D B A
//后序遍歷(非遞回)：C G E F D B A
//
//層次遍歷 ：A B C D E F G
//
/// A
/// /
/// B
/// / \
/// C D
/// / \
/// E F
/// \
/// G
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/275918.html
標籤：C語言
上一篇：剛學c語言求大佬幫忙解答.
下一篇：用C++實作圖片滾動效果