二叉树每个结点最多有2个孩子，所以为它设计一个数据域和2个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。
正常的情况下，二叉树的单独前序、中序、后续，都不能唯一的确定一个二叉树，因为前序和后续，能确定根结点，但是区分不开左右子树。
而中序没办法知道哪个是根结点。
但是我们通常使用二叉树的扩展来进行创建树，原因是扩展二叉树的前序和后续，都能确定唯一的二叉树，至于原因，我会再单独写一篇文章说明，而中序不能确定，这里暂时给出代码实现。
先直接上代码，这里只是实现了二叉树的生成和遍历，生成采用前序遍历，遍历采用三种方法
#include<iostream> using namespace std; //二叉树的二叉链表结点结构定义 typedef struct BitNode { int data;//数据域 struct BitNode*lchild, *rchild;//左右孩子指针 }BitNode; typedef struct BitNode* BitTree; //二叉树的先序遍历 void PreOrder(BitTree Node) { if (Node == NULL) { return; } //先访问根结点 printf("%c\n", Node->data); if (Node->lchild != NULL) { PreOrder(Node->lchild); } if (Node->rchild != NULL) { PreOrder(Node->rchild); } } //中序遍历 void InOrder(BitTree Node) { if (Node == NULL) { return; } if (Node->lchild != NULL) { InOrder(Node->lchild); } //先访问根结点 printf("%c\n", Node->data); if (Node->rchild != NULL) { InOrder(Node->rchild); } } //后续遍历 void PostOrder(BitTree Node) { if (Node == NULL) { return; } if (Node->lchild != NULL) { PostOrder(Node->lchild); } if (Node->rchild != NULL) { PostOrder(Node->rchild); } //先访问根结点 printf("%c\n", Node->data); } //创建一个二叉树 /*按照前序输入二叉树中结点的值*/ /*其中#表示空树，构造二叉链表 表示二叉树T*/ //传二级指针的目的是为了修改一级指针的值 void CreateBitTree(BitTree *T) { char ch; scanf("%c", &ch); if (ch == '#') { *T = NULL; } else { *T = (BitTree)malloc(sizeof(BitNode)); if (*T == NULL) { printf("error \n"); return; } (*T)->data = ch;//生成根结点 CreateBitTree(&(*T)->lchild);//构造左子树 CreateBitTree(&(*T)->rchild);//构造右子树 } } int main(int argc, char *argv[]) { BitTree tmp = (BitTree)malloc(sizeof(BitNode));//相当于传入头指针 CreateBitTree(&tmp); printf("enter end\n"); printf("start preorder\n"); PreOrder(tmp); printf("start inorder\n"); InOrder(tmp); printf("start postorder\n"); PostOrder(tmp); return 0; }输出结果如下：
下面的代码是用后续进行创建树，后续要用到栈的数据结构，代码如下：
#include<iostream> #include<cstdlib> #include<string> #include<stack> using namespace std; #define OK 1 #define ERROR 0 typedef int Status; typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; typedef char SElemType; stack<char> S; Status InitBiTree(BiTree *); BiTree PreCreateBiTree(BiTree *); //先序扩展序列递归建树 BiTree PostCreateBiTree(BiTree *); //后序扩展序列建树准备工作 BiTree PostCreateBiTree2(BiTree *); //后序扩展序列递归建树 Status PreOrder(BiTree); Status InOrder(BiTree); Status PostOrder(BiTree); Status InitBiTree(BiTree *BT) { *BT = NULL; return 0; } //先序扩展序列递归建树 BiTree PreCreateBiTree(BiTree *BT) { TElemType ch; scanf("%c", &ch); if (ch == '#') { *BT = NULL; return *BT; } else { *BT = (BiTNode *)malloc(sizeof(BiTNode)); (*BT)->data = ch; (*BT)->lchild = PreCreateBiTree(&((*BT)->lchild)); (*BT)->rchild = PreCreateBiTree(&((*BT)->rchild)); } return *BT; } //后序扩展序列建树准备工作，接收字符入栈 BiTree PostCreateBiTree(BiTree *BT) { TElemType ch=0; //scanf("%c", &ch); //S.push(ch); while (1) { scanf("%c", &ch); if (ch == '\n') break; S.push(ch); } *BT = PostCreateBiTree2(&(*BT)); return *BT; } //后序扩展序列递归建树 BiTree PostCreateBiTree2(BiTree *BT) { TElemType ch; ch = S.top(); S.pop(); if (ch == '#') { *BT = NULL; return *BT; } else { *BT = (BiTNode *)malloc(sizeof(BiTNode)); (*BT)->data = ch; (*BT)->rchild = PostCreateBiTree2(&((*BT)->rchild)); (*BT)->lchild = PostCreateBiTree2(&((*BT)->lchild)); } return *BT; } Status PreOrder(BiTree BT) { if (BT) { if (!(BT->data)) return ERROR; printf("%c ", BT->data); PreOrder(BT->lchild); PreOrder(BT->rchild); return OK; } return ERROR; } Status InOrder(BiTree BT) { if (BT) { if (!(BT->data)) return ERROR; InOrder(BT->lchild); printf("%c ", BT->data); InOrder(BT->rchild); return OK; } return ERROR; } Status PostOrder(BiTree BT) { if (BT) { if (!(BT->data)) return ERROR; PostOrder(BT->lchild); PostOrder(BT->rchild); printf("%c ", BT->data); return OK; } return ERROR; } int main() { BiTree BT; int flag = 1, select = 0; InitBiTree(&BT); printf(" Please input:"); BT = PostCreateBiTree(&BT); printf("Create BiTree successfully!\n\n"); printf("\t*\tPlease select: *\n"); printf("\t*\t1.PreOrder Traversal *\n"); printf("\t*\t2.InOrder Traversal *\n"); printf("\t*\t3.PostOrder Traversal *\n"); printf("\t*\t7.Exit *\n"); scanf("%d", &select); switch (select) { case 1:printf("\n The PreOrder Traversal of Binary Tree is: "); PreOrder(BT); break; case 2:printf("\n The InOrder Traversal of Binary Tree is: "); InOrder(BT); break; case 3:printf("\n The PostOrder Traversal of Binary Tree is: "); PostOrder(BT); break; } printf("\n"); return 0; }输出结果如下：
