王道計算機考研 數(shù)據(jù)結(jié)構
二叉樹的 先序，中序，后序，層次遍歷（層次遍歷找bug找了一下午，結(jié)果傳隊列進去只傳的是數(shù)據(jù)域，應該傳結(jié)點進去）希望對大家有用
#include <stdio.h>
#include <stdlib.h>
#define Elemtype char
typedef struct BiTNode
{
? ? Elemtype data;
? ? struct BiTNode *lchild;
? ? struct BiTNode *rchild;
} BiTNode, *BiTree;
// 鏈式隊列結(jié)點
typedef struct LinkNode
{
? ? BiTNode *data;
? ? struct LinkNode *next;
} LinkNode;
// 鏈式隊列
typedef struct
{
? ? LinkNode *head;
? ? LinkNode *rear;
} LinkQueue;
// 初始化隊列
void InitQueue(LinkQueue &Q)
{
? ? Q.head = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
? ? Q.head->next = NULL;
}
// 入隊
void EnQueue(LinkQueue &Q, BiTNode *x) ?//讓結(jié)點入隊所以傳結(jié)點BiTNode *x
{
? ? LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
? ? s->data = (BiTNode *)malloc(sizeof(BiTNode));
? ? s->data = x;
? ? s->next = NULL;
? ? Q.rear->next = s; // 新結(jié)點插入到rear之后
? ? Q.rear = s; ? ? ? // 修改表尾指針
}
// 出隊
bool DeQueue(LinkQueue &Q, BiTNode *&x) //讓結(jié)點出隊所以傳出（用&引用出來）的應該是結(jié)點（而不是單純的數(shù)據(jù)域！?。。?/p>
{
? ? if (Q.head == Q.rear) // 空隊
? ? ? ? return false;
? ? LinkNode *p = Q.head->next; // p指向隊首
? ? // p->data = (BiTNode *)malloc(sizeof(BiTNode));
? ? x = p->data; ? ? ? ? ? ?// 用x返回隊首元素
? ? Q.head->next = p->next; // 修改頭結(jié)點的頭指針
? ? if (Q.rear == p) ? ? ? ?// 此次是最后一個結(jié)點出隊
? ? ? ? Q.rear = Q.head; ? ?// 修改rear指針
? ? free(p);
? ? return true;
}
// 判斷隊列是否為空
bool isEmpty(LinkQueue Q)
{
? ? if (Q.head == Q.rear)
? ? ? ? return true;
? ? else
? ? ? ? return false;
}
// 創(chuàng)建二叉樹
BiTree
CreateTree()
{
? ? BiTNode *root;
? ? Elemtype ch;
? ? scanf("%c", &ch); // 通過輸入的ch是否為特殊符號來判斷該節(jié)點是否有孩子節(jié)點
? ? if (ch == '#') ? ?// 不存在孩子節(jié)點
? ? ? ? return NULL;
? ? else
? ? {
? ? ? ? root = (BiTNode *)malloc(sizeof(BiTNode));
? ? ? ? if (root == NULL)
? ? ? ? {
? ? ? ? ? ? printf("Created false\n");
? ? ? ? ? ? return NULL;
? ? ? ? }
? ? ? ? root->data = ch;
? ? ? ? root->lchild = CreateTree(); // 存放左孩子結(jié)點，遞歸調(diào)用本函數(shù)，使得左孩子結(jié)點先被賦值
? ? ? ? root->rchild = CreateTree();
? ? ? ? return root;
? ? }
}
// 訪問根節(jié)點
Elemtype Vist(BiTree T)
{
? ? printf("%c", T->data);
? ? return T->data;
}
// 先序遍歷
void PreOrder(BiTree T)
{
? ? if (T != NULL)
? ? {
? ? ? ? Vist(T);
? ? ? ? PreOrder(T->lchild);
? ? ? ? PreOrder(T->rchild);
? ? }
}
// 中序遍歷
void InOrder(BiTree T)
{
? ? if (T != NULL)
? ? {
? ? ? ? InOrder(T->lchild);
? ? ? ? Vist(T);
? ? ? ? InOrder(T->rchild);
? ? }
}
// 后序遍歷
void PostOrder(BiTree T)
{
? ? if (T != NULL)
? ? {
? ? ? ? PostOrder(T->lchild);
? ? ? ? PostOrder(T->rchild);
? ? ? ? Vist(T);
? ? }
}
// 層次遍歷
void LevelOrder(BiTree T)
{
? ? LinkQueue Q;
? ? InitQueue(Q); // 初始化輔助隊列
? ? BiTree p;
? ? p = T;
? ? EnQueue(Q, T); // 將根結(jié)點入隊
? ? while (!isEmpty(Q)) // 隊列不空則循環(huán)
? ? {
? ? ? ? DeQueue(Q, p); // 隊頭結(jié)點出隊
? ? ? ? Vist(p); ? ? ? // 訪問出隊結(jié)點
? ? ? ? if (p->lchild != NULL)
? ? ? ? ? ? EnQueue(Q, p->lchild); // 左孩子入隊
? ? ? ? if (p->rchild != NULL)
? ? ? ? ? ? EnQueue(Q, p->rchild); // 右孩子入隊
? ? }
}
// 后序遍歷的應用
// 求樹的深度
int TreeDepth(BiTree T)
{
? ? if (T == NULL)
? ? {
? ? ? ? return 0;
? ? }
? ? else
? ? {
? ? ? ? int l = TreeDepth(T->lchild);
? ? ? ? int r = TreeDepth(T->rchild);
? ? ? ? // 樹的深度=max(左子樹的深度，右子樹的深度)+1（根節(jié)點獨占一個深度）
? ? ? ? return l > r ? l + 1 : r + 1;
? ? }
}
void test()
{
? ? BiTree T;
? ? printf("Please enter a binarytree ('#' is NULL):");
? ? T = CreateTree(); // 用Createtree建立出來樹（結(jié)構體），賦值給T，下面才能用T進行遍歷操作
? ? if (T != NULL)
? ? {
? ? ? ? // printf("The PreOrder is :\n");
? ? ? ? // PreOrder(T);
? ? ? ? // printf("\n");
? ? ? ? // printf("The InOrder is:\n");
? ? ? ? // InOrder(T);
? ? ? ? // printf("\n");
? ? ? ? // printf("The PostOrder is:\n");
? ? ? ? // PostOrder(T);
? ? ? ? // printf("\n");
? ? ? ? printf("The LevelOrder is :\n");
? ? ? ? LevelOrder(T);
? ? ? ? printf("\n");
? ? ? ? // printf("The binarytree's depth is %d\n", TreeDepth(T));
? ? }
? ? else
? ? ? ? printf("Created false\n");
}
int main()
{
? ? test();
? ? return 0;
}
