目录

1. 二叉树的遍历规则

2. 二叉树的结构体设计 【leftchild  data  rightchild】

3. 二叉树的递归先序、中序、后序遍历

4. 利用已知字符串（二叉树的先序序列）递归创建一棵二叉树

（1）购买节点函数

（2）创建二叉树

5. 使用先序遍历序列和中序遍历序列创建一棵二叉树

6. 使用中序遍历序列和后序遍历序列创建一棵二叉树

 7. 对二叉树的物理存储数组进行递归先序、中序、后序遍历

1. 二叉树的遍历规则

先序遍历：根 -> 左 -> 右；中序遍历： 左 -> 根 -> 右；后序遍历：左 -> 右 ->根 。

2. 二叉树的结构体设计 【leftchild  data  rightchild】

typedef char ELEMTYPE;//typedef给char类型起别名ELEMTYPE
//二叉树结构体设计
typedef struct BtNode
{struct BtNode* leftchild;ELEMTYPE data;struct BtNode* rightchild;
}BtNode,* PBtNode;

3. 二叉树的递归先序、中序、后序遍历

void PreOrder(struct BtNode* ptr) //先序遍历（根左右）
{if (nullptr == ptr) return;printf("%3c", ptr->data);PreOrder(ptr->leftchild);PreOrder(ptr->rightchild);
}
void InOrder(struct BtNode* ptr) //中序遍历（左根右）
{if (nullptr == ptr) return;InOrder(ptr->leftchild);printf("%3c", ptr->data);InOrder(ptr->rightchild);
}
void LastOrder(struct BtNode* ptr) //后序遍历（左右根）
{if (nullptr == ptr) return;LastOrder(ptr->leftchild);LastOrder(ptr->rightchild);printf("%3c", ptr->data);
}

4. 利用已知字符串（二叉树的先序序列）递归创建一棵二叉树

（1）购买节点函数

struct BtNode* Buynode()
{BtNode* s = (BtNode*)malloc(sizeof(BtNode));if (s == nullptr) exit(1);memset(s, 0, sizeof(BtNode));//此处不要写sizeof(s),由于指针永远为4bit(32bit系统下)return s;
}

（2）创建二叉树

注意：函数参数为引用！！确保每次递归时传参是对同一字符串前置++。

BtNode* CreateBT(const char*& str)//参数为引用！！是由于递归时传参为++str~为了保证每次++同步执行（即在同一个字符串序列）
{//根据先序序列创建树~根左右if (str == nullptr || strlen(str) <= 0) return nullptr;//空树BtNode* s = nullptr;if (*str != '#'){s = Buynode();s->data = *str;//根s->leftchild = CreateBT(++str);//左s->rightchild = CreateBT(++str);//右}return s;
}
int main()
{const char* str = "ABC##DE##F##G#H##";BtNode* s=CreateBT(str);PreOrder(s);printf("\n");InOrder(s);printf("\n");LastOrder(s);printf("\n");return 0;
}

运行结果如图：

5. 使用先序遍历序列和中序遍历序列创建一棵二叉树

//根据先序遍历+中序遍历创建一棵二叉树
int Find(const char* istr, int n, char str) //中序序列中找根对应的下标
{int pos = -1;for (int i = 0; i < n; ++i){if (istr[i] == str){pos = i;break;}}return pos;
}
BtNode* CreatePITree(const char* pstr, const char* istr, int n)//此处n代表规模
{BtNode* s = nullptr;if (n > 0){s = Buynode();s->data = pstr[0];//先序首位为根int pos = Find(istr, n, pstr[0]);//中序序列中找根对应的下标if (pos == -1) exit(1);s->leftchild = CreatePITree(pstr+1,istr,pos);s->rightchild = CreatePITree(pstr+pos+1,istr+pos+1,n-pos-1);}return s;
}
BtNode* CreatePIT(const char* pstr, const char* istr)
{int n = strlen(pstr);int m = strlen(istr);if (pstr == nullptr || istr == nullptr || n < 1 || m < 1 || n != m) return nullptr;else return CreatePITree(pstr, istr, n);
}int main()
{//const char* str = "ABC##DE##F##G#H##";//BtNode* s=CreateBT(str);const char* pstr = "ABCDEFGH";const char* istr = "CBEDFAGH";BtNode* s = CreatePIT(pstr, istr);PreOrder(s);printf("\n");InOrder(s);printf("\n");LastOrder(s);printf("\n");return 0;
}

6. 使用中序遍历序列和后序遍历序列创建一棵二叉树

//根据中序遍历+后序遍历创建一棵二叉树
BtNode* CreateILTree(const char* istr, const char* lstr, int n)//此处n代表规模
{BtNode* s = nullptr;if (n > 0){s = Buynode();s->data = lstr[n - 1];//后序遍历的最后一个为根int pos = Find(istr, n, lstr[n - 1]);s->leftchild = CreateILTree(istr,lstr,pos);s->rightchild = CreateILTree(istr+pos+1,lstr+pos,n-pos-1);}return s;
}
BtNode* CreateILT(const char* istr, const char* lstr)
{ int n = strlen(istr);int m = strlen(lstr);if (nullptr == istr || nullptr == lstr || n < 1 || m < 1 || n != m) return nullptr;else return CreateILTree(istr, lstr, n);
}int main()
{//const char* str = "ABC##DE##F##G#H##";//BtNode* s=CreateBT(str);const char* pstr = "ABCDEFGH";const char* istr = "CBEDFAGH";const char* lstr = "CEFDBHGA";//BtNode* s = CreatePIT(pstr, istr);BtNode* s = CreateILT(istr, lstr);PreOrder(s);printf("\n");InOrder(s);printf("\n");LastOrder(s);printf("\n");return 0;
}

 7. 对二叉树的物理存储（数组）进行递归先序、中序、后序遍历

主要依据：二叉树的物理存储对应逻辑存储的关系。

二叉树物理下标为i：其左孩子对应下标为i*2+1；其右孩子对应下标为i*2+2。

//对二叉树的物理存储数组进行递归先序、中序、后序遍历
void PreOrder(const int* nums, int i, int n)//遍历规模：i~n
{if (i < n && nums[i] != -1) //i==n时规模为1{printf("%3d", nums[i]);//根PreOrder(nums, i * 2 + 1, n);//左 左子树下标：i*2+1PreOrder(nums, i * 2 + 2, n);//右}
}
void InOrder(const int* nums, int i, int n)
{if (i < n && nums[i] != -1){InOrder(nums, i * 2 + 1, n);//左printf("%3d", nums[i]);//根InOrder(nums, i * 2 + 2, n);//右}
}
void LastOrder(const int* nums, int i, int n)
{if (i < n && nums[i] != -1){LastOrder(nums, i * 2 + 1, n);//左LastOrder(nums, i * 2 + 2, n);//右printf("%3d", nums[i]);//根}
}
int main()
{const int nums[] = {31,23,12,66,-1,5,17,70,62,-1,-1,-1,88,-1,55};int n = sizeof(nums) / sizeof(nums[0]);PreOrder(nums, 0, n);printf("\n");InOrder(nums, 0, n);printf("\n");LastOrder(nums, 0, n);printf("\n");return 0;
}