二叉树的介绍
二叉树是树这种数据结果的一种特殊情况，其每个节点的子节点树不能超过两个，二叉树差不多就是树中最常用的特殊结构了。
二叉树的分类
满二叉树
国外定义：由度为0和2的结点构成的树，没有度为1的节点。
国内定义：每一层都是满结点，高度为k的二叉树的结点固定为。
完全二叉树
按层序从上到下，从左到右编号，空缺只能出现在最后一层的最右侧，前面所有层必须满。
完美二叉树
国外定义：每一层都是满结点，高度为k的二叉树的结点固定为。
国内定义：每一层都是满结点，高度为k的二叉树的结点固定为。
扩充二叉树
在原二叉树所有空子树的位置添加上空结点。
二叉树的性质
①二叉树的第k层最多有个节点。
②深度为d的二叉树最多有个节点
③设一棵树中，度为i的节点数为，
则总节点数N==
可以推出
解释：主要是解释N=，由于一个度为2的结点会挂两个结点，一个度为1的结点会挂1个节点，一个度为0的叶子节点不挂节点，所以按道理
就是树的总结点数，但是根节点没有其它节点挂着它，所以上述式子没有算上根节点，如果算上根节点的话就加1就行了。
二叉树的实现
二叉树的数据结构
typedef int ElementType; struct TreeNode; typedef struct TreeNode *PtrToNode; typedef PtrToNode Tree; struct TreeNode { ElementType Element; Tree Left; Tree Right; }; Tree CreateTree(ElementType rootElement); PtrToNode CreateNode(ElementType element); void InsertLeftChild(PtrToNode parent, ElementType element); void InsertRightChild(PtrToNode parent, ElementType element); void PreOrderTraversal(Tree T); void InOrderTraversal(Tree T); void PostOrderTraversal(Tree T); void DestroyTree(Tree T);这里依然把二叉树的所有节点都看成是一个个指向struct TreeNode对象的指向，每个节点包含存储的数据，以及这个节点指向其左右两个子节点的指针。
树和节点的创建及销毁
Tree CreateTree(ElementType rootElement) { Tree T = (Tree)malloc(sizeof(struct TreeNode)); if (T == NULL) { printf("Failed to allocate memory for the new Tree\n"); return NULL; } T->Element = rootElement; T->Left = NULL; T->Right = NULL; return T; } PtrToNode CreateNode(ElementType element) { PtrToNode node = (PtrToNode)malloc(sizeof(struct TreeNode)); if (node == NULL) { printf("Failed to allocate memory for the new Tree\n"); return NULL; } node->Element = element; node->Left = NULL; node->Right = NULL; return node; } void DestroyTree(Tree T) { if (T != NULL) { DestroyTree(T->Left); DestroyTree(T->Right); free(T); } }创建一个二叉树对象其实就是创建一个根节点，如果想要实现节点与节点之间的联系，就需要用到左右子节点插入的函数。
左右子节点的插入
void InsertLeftChild(PtrToNode parent,ElementType element) { if (parent == NULL) { printf("Parent is NULL\n"); return; } if (parent->Left != NULL) { printf("The LeftChild already exists"); return; } parent->Left = CreateNode(element); } void InsertRightChild(PtrToNode parent,ElementType element) { if (parent == NULL) { printf("Parent is NULL\n"); return; } if (parent->Right != NULL) { printf("The RightChild already exists"); } parent->Right = CreateNode(element); }对于左子节点插入的函数，其逻辑就是先创建一个数据为element的节点，然后让parent这个父节点的Left指针指向这个节点。右子节点的插入也是同理。
前中后序遍历
void PreOrderTraversal(Tree T) { if (T != NULL) { printf("%d", T->Element); PreOrderTraversal(T->Left); PreOrderTraversal(T->Right); } } void InOrderTraversal(Tree T) { if (T != NULL) { InOrderTraversal(T->Left); printf("%d", T->Element); InOrderTraversal(T->Right); } } void PostOrderTraversal(Tree T) { if (T != NULL) { PostOrderTraversal(T->Left); PostOrderTraversal(T->Right); printf("%d", T->Element); } }得益于树的结构，其前中后序的遍历只需要简单的递归就能实现，以前序遍历(根左右)为例，先打印输出根节点的值，然后再遍历根节点的左边，左边也是一棵树，这样根节点的左子节点就相当于这棵树的头节点，根据根左右的顺序就遍历这个头节点，然后再以它的左节点开始，把它的左节点看成头节点，周而复始地进行根左右这个顺序的遍历。其他情况同理。
实例
int main() { Tree T = CreateTree(1); InsertLeftChild(T, 2); InsertRightChild(T, 3); InsertLeftChild(T->Left, 4); InsertRightChild(T->Left, 5); PreOrderTraversal(T); printf("\n"); InOrderTraversal(T); printf("\n"); PostOrderTraversal(T); DestroyTree(T); return 0; }结果如下：
表达式树的介绍
表达式树指的是其树上的节点存储的都是表达式的元素，由于加减乘除这样的运算都是对两个值进行的运算，而二叉树的每个节点的子节点又可以恰好为两个，所有理所应当地就可以用二叉树来存储一个由加减乘除构成的表达式了。以下算法可以实现后缀表达式的输入，而进行中缀表达式及其式子运算后的值的输出。程序由豆包生成。
表达式树的实现
表达式树的结构
typedef union { char op; // 操作符 int num; // 操作数（这里用整数举例） } ElementType; struct TreeNode; typedef struct TreeNode *PtrToNode; typedef PtrToNode Tree; struct TreeNode { ElementType data; int isOperator; // 标记是操作符(1)还是操作数(0) Tree Left; Tree Right; };树的节点有四个变量，首先是存储的值，这个值可以是一个数字，也可以是一个运算符，所有其数据类型为union；其次还需要一个用于标记这个节点存储的是数字还有运算符的记号；最后就是指向左右节点的指针。
栈的辅助结构
// 栈的辅助结构（用于存储树的指针） typedef struct StackNode { Tree tree; struct StackNode *next; } StackNode, *Stack; // 创建空栈 Stack CreateStack() { Stack s = (Stack)malloc(sizeof(StackNode)); s->next = NULL; return s; } // 判断栈空 int IsStackEmpty(Stack s) { return s->next == NULL; } // 压栈 void Push(Stack s, Tree t) { StackNode *newNode = (StackNode *)malloc(sizeof(StackNode)); newNode->tree = t; newNode->next = s->next; s->next = newNode; } // 弹栈 Tree Pop(Stack s) { if (IsStackEmpty(s)) { printf("栈空，无法弹栈！\n"); exit(1); } StackNode *top = s->next; Tree t = top->tree; s->next = top->next; free(top); return t; }由于算法涉及到需要把一个后缀表达式拆解再将每个部分放到二叉树中，所以这里用栈这种数据结构来方便以上步骤的进行。
后缀表达式转表达式树
// 创建操作数节点 Tree CreateNumNode(int num) { Tree t = (Tree)malloc(sizeof(struct TreeNode)); t->data.num = num; t->isOperator = 0; t->Left = NULL; t->Right = NULL; return t; } // 创建操作符节点 Tree CreateOpNode(char op, Tree left, Tree right) { Tree t = (Tree)malloc(sizeof(struct TreeNode)); t->data.op = op; t->isOperator = 1; t->Left = left; t->Right = right; return t; } // 后缀表达式转表达式树 Tree BuildExpressionTree(char *postfix) { Stack s = CreateStack(); int len = strlen(postfix); for (int i = 0; i < len; i++) { char c = postfix[i]; if (c == ' ') continue; // 跳过空格 if (c >= '0' && c <= '9') { // 处理多位数（简单处理：假设是单个数字） int num = c - '0'; Tree numTree = CreateNumNode(num); Push(s, numTree); } else if (c == '+' || c == '-' || c == '*' || c == '/') { // 操作符：弹出右子树、左子树 Tree right = Pop(s); Tree left = Pop(s); Tree opTree = CreateOpNode(c, left, right); Push(s, opTree); } } Tree exprTree = Pop(s); free(s); // 释放栈 return exprTree; }需要说明的是为了简便这个算法不能识别多位数字。首先开始对后缀表达式遍历，如果遍历到的是数字，那就存入栈中，如果遍历到操作符，先把这个操作符封装成一个节点，然后从栈中弹出两个节点，让这个操作符节点的左右子节点分别为这两个节点，最后再将这个操作符节点压栈，以便之后成为别的操作符节点的子节点。最后整个栈只会有一个节点，这个节点其实就是最终的表达式树，把它弹出来后，栈就是空栈了，此时就可以释放栈的空间了。
中缀表达式的输出
// 中序遍历（输出中缀表达式，自动加括号） void InOrderExpr(Tree t) { if (t == NULL) return; if (t->isOperator) printf("("); InOrderExpr(t->Left); if (t->isOperator) { printf("%c", t->data.op); } else { printf("%d", t->data.num); } InOrderExpr(t->Right); if (t->isOperator) printf(")"); }当得到表达式二叉树后，对它进行后序遍历得到的就是后序表达式，对它进行中序遍历得到的就是中序表达式。
表达式树的求值
// 表达式树求值 int EvaluateExprTree(Tree t) { if (t == NULL) return 0; if (!t->isOperator) { return t->data.num; // 操作数直接返回 } int leftVal = EvaluateExprTree(t->Left); int rightVal = EvaluateExprTree(t->Right); switch (t->data.op) { case '+': return leftVal + rightVal; case '-': return leftVal - rightVal; case '*': return leftVal * rightVal; case '/': return leftVal / rightVal; default: printf("未知操作符！\n"); exit(1); } }这里通过后序遍历得到表达式树的值。其表达式树长这样：
实例
int main() { // 后缀表达式："3 4 + 5 *" → 对应中缀 (3+4)*5 char postfix[] = "3 4 + 5 *"; Tree exprTree = BuildExpressionTree(postfix); printf("中缀表达式："); InOrderExpr(exprTree); printf("\n"); int result = EvaluateExprTree(exprTree); printf("表达式结果：%d\n", result); // （可选）销毁树 // DestroyTree(exprTree); return 0; }结果如下：
