二叉树和表达式树的实现

二叉树的介绍二叉树是树这种数据结果的一种特殊情况其每个节点的子节点树不能超过两个二叉树差不多就是树中最常用的特殊结构了。二叉树的分类满二叉树国外定义由度为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 * → 对应中缀 (34)*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; }结果如下