下载文档原格式
⼆叉树的遍历及常⽤算法⼆叉树的遍历及常⽤算法遍历的定义:按照某种次序访问⼆叉树上的所有结点,且每个节点仅被访问⼀次;遍历的重要性:当我们需要对⼀颗⼆叉树进⾏,插⼊,删除,查找等操作时,通常都需要先遍历⼆叉树,所有说:遍历是⼆叉树的基本操作;遍历思路:⼆叉树的数据结构是递归定义(每个节点都可能包含相同结构的⼦节点),所以遍历也可以使⽤递归,即结点不为空则继续递归调⽤每个节点都有三个域,数据与,左孩⼦指针和右孩⼦之指针,每次遍历只需要读取数据,递归左⼦树,递归右⼦树,这三个操作三种遍历次序:根据访问三个域的不同顺序,可以有多种不同的遍历次序,⽽通常对于⼦树的访问都按照从左往右的顺序;设:L为遍历左⼦树,D为访问根结点,R为遍历右⼦树,且L必须位于R的前⾯可以得出以下三种不同的遍历次序:先序遍历操作次序为DLR,⾸先访问根结点，其次遍历根的左⼦树，最后遍历根右⼦树，对每棵⼦树同样按这三步(先根、后左、再右)进⾏中序遍历操作次序为LDR,⾸先遍历根的左⼦树，其次访问根结点，最后遍历根右⼦树，对每棵⼦树同样按这三步(先左、后根、再右)进⾏后序遍历操作次序为LRD,⾸先遍历根的左⼦树，其次遍历根的右⼦树，最后访问根结点，对每棵⼦树同样按这三步(先左、后右、最后根)进⾏层次遍历层次遍历即按照从上到下从左到右的顺序依次遍历所有节点,实现层次遍历通常需要借助⼀个队列,将接下来要遍历的结点依次加⼊队列中;遍历的应⽤“遍历”是⼆叉树各种操作的基础，可以在遍历过程中对结点进⾏各种操作，如:对于⼀棵已知⼆叉树求⼆叉树中结点的个数求⼆叉树中叶⼦结点的个数;求⼆叉树中度为1的结点个数求⼆叉树中度为2的结点个数5求⼆叉树中⾮终端结点个数交换结点左右孩⼦判定结点所在层次等等...C语⾔实现:#include <stdio.h>//⼆叉链表数据结构定义typedef struct TNode {char data;struct TNode *lchild;struct TNode *rchild;} *BinTree, BinNode;//初始化//传⼊⼀个指针令指针指向NULLvoid initiate(BinTree *tree) {*tree = NULL;}//创建树void create(BinTree *BT) {printf("输⼊当前结点值: (0则创建空节点)\n");char data;scanf(" %c", &data);//连续输⼊整形和字符时.字符变量会接受到换⾏,所以加空格if (data == 48) {*BT = NULL;return;} else {//创建根结点//注意开辟的空间⼤⼩是结构体的⼤⼩⽽不是结构体指针⼤⼩,写错了不会⽴马产⽣问题,但是后续在其中存储数据时极有可能出现内存访问异常(飙泪....) *BT = malloc(sizeof(struct TNode));//数据域赋值(*BT)->data = data;printf("输⼊节点 %c 的左孩⼦ \n", data);create(&((*BT)->lchild));//递归创建左⼦树printf("输⼊节点 %c 的右孩⼦ \n", data);create(&((*BT)->rchild));//递归创建右⼦树}}//求双亲结点(⽗结点)BinNode *Parent(BinTree tree, char x) {if (tree == NULL)return NULL;else if ((tree->lchild != NULL && tree->lchild->data == x) || (tree->rchild != NULL && tree->rchild->data == x))return tree;else{BinNode *node1 = Parent(tree->lchild, x);BinNode *node2 = Parent(tree->rchild, x);return node1 != NULL ? node1 : node2;}}//先序遍历void PreOrder(BinTree tree) {if (tree) {//输出数据printf("%c ", tree->data);//不为空则按顺序继续递归判断该节点的两个⼦节点PreOrder(tree->lchild);PreOrder(tree->rchild);}}//中序void InOrder(BinTree tree) {if (tree) {InOrder(tree->lchild);printf("%c ", tree->data);InOrder(tree->rchild);}}//后序void PostOrder(BinTree tree) {if (tree) {PostOrder(tree->lchild);PostOrder(tree->rchild);printf("%c ", tree->data);}}//销毁结点递归free所有节点void DestroyTree(BinTree *tree) {if (*tree != NULL) {printf("free %c \n", (*tree)->data);if ((*tree)->lchild) {DestroyTree(&((*tree)->lchild));}if ((*tree)->rchild) {DestroyTree(&((*tree)->rchild));}free(*tree);*tree = NULL;}}// 查找元素为X的结点使⽤的是层次遍历BinNode *FindNode(BinTree tree, char x) {if (tree == NULL) {return NULL;}//队列BinNode *nodes[1000] = {};//队列头尾位置int front = 0, real = 0;//将根节点插⼊到队列尾nodes[real] = tree;real += 1;//若队列不为空则继续while (front != real) {//取出队列头结点输出数据BinNode *current = nodes[front];if (current->data == x) {return current;}front++;//若当前节点还有⼦(左/右)节点则将结点加⼊队列if (current->lchild != NULL) {nodes[real] = current->lchild;real++;}if (current->rchild != NULL) {nodes[real] = current->rchild;real++;}}return NULL;}//层次遍历// 查找元素为X的结点使⽤的是层次遍历void LevelOrder(BinTree tree) {if (tree == NULL) {return;}//队列BinNode *nodes[1000] = {};//队列头尾位置int front = 0, real = 0;//将根节点插⼊到队列尾nodes[real] = tree;real += 1;//若队列不为空则继续while (front != real) {//取出队列头结点输出数据BinNode *current = nodes[front];printf("%2c", current->data);front++;//若当前节点还有⼦(左/右)节点则将结点加⼊队列if (current->lchild != NULL) {nodes[real] = current->lchild;real++;}if (current->rchild != NULL) {nodes[real] = current->rchild;real++;}}}//查找x的左孩⼦BinNode *Lchild(BinTree tree, char x) {BinTree node = FindNode(tree, x);if (node != NULL) {return node->lchild;}return NULL;}//查找x的右孩⼦BinNode *Rchild(BinTree tree, char x) {BinTree node = FindNode(tree, x);if (node != NULL) {return node->rchild;}return NULL;}//求叶⼦结点数量int leafCount(BinTree *tree) {if (*tree == NULL)return 0;//若左右⼦树都为空则该节点为叶⼦,且后续不⽤接续递归了else if (!(*tree)->lchild && !(*tree)->rchild)return 1;else//若当前结点存在⼦树,则递归左右⼦树, 结果相加return leafCount(&((*tree)->lchild)) + leafCount(&((*tree)->rchild));}//求⾮叶⼦结点数量int NotLeafCount(BinTree *tree) {if (*tree == NULL)return 0;//若该结点左右⼦树均为空,则是叶⼦,且不⽤继续递归else if (!(*tree)->lchild && !(*tree)->rchild)return 0;else//若当前结点存在左右⼦树,则是⾮叶⼦结点(数量+1),在递归获取左右⼦树中的⾮叶⼦结点,结果相加 return NotLeafCount(&((*tree)->lchild)) + NotLeafCount(&((*tree)->rchild)) + 1;}//求树的⾼度(深度)int DepthCount(BinTree *tree) {if (*tree == NULL)return 0;else{//当前节点不为空则深度+1 在加上⼦树的⾼度,int lc = DepthCount(&((*tree)->lchild)) + 1;int rc = DepthCount(&((*tree)->rchild)) + 1;return lc > rc?lc:rc;// 取两⼦树深度的最⼤值 }}//删除左⼦树void RemoveLeft(BinNode *node){if (!node)return;if (node->lchild)DestroyTree(&(node->lchild));node->lchild = NULL;}//删除右⼦树void RemoveRight(BinNode *node){if (!node)return;if (node->rchild)DestroyTree(&(node->rchild));node->rchild = NULL;}int main() {BinTree tree;create(&tree);BinNode *node = Parent(tree, 'G');printf("G的⽗结点为%c\n",node->data);BinNode *node2 = Lchild(tree, 'D');printf("D的左孩⼦结点为%c\n",node2->data);BinNode *node3 = Rchild(tree, 'D');printf("D的右孩⼦结点为%c\n",node3->data);printf("先序遍历为:");PreOrder(tree);printf("\n");printf("中序遍历为:");InOrder(tree);printf("\n");printf("后序遍历为:");PostOrder(tree);printf("\n");printf("层次遍历为:");LevelOrder(tree);printf("\n");int a = leafCount(&tree);printf("叶⼦结点数为%d\n",a);int b = NotLeafCount(&tree);printf("⾮叶⼦结点数为%d\n",b);int c = DepthCount(&tree);printf("深度为%d\n",c);//查找F节点BinNode *node4 = FindNode(tree,'C');RemoveLeft(node4);printf("删除C的左孩⼦后遍历:");LevelOrder(tree);printf("\n");RemoveRight(node4);printf("删除C的右孩⼦后遍历:");LevelOrder(tree);printf("\n");//销毁树printf("销毁树 \n");DestroyTree(&tree);printf("销毁后后遍历:");LevelOrder(tree);printf("\n");printf("Hello, World!\n");return 0;}测试:测试数据为下列⼆叉树:运⾏程序复制粘贴下列内容:ABDGHECKFIJ特别感谢:iammomo。
数据结构与算法系列研究五——树、⼆叉树、三叉树、平衡排序⼆叉树AVL树、⼆叉树、三叉树、平衡排序⼆叉树AVL⼀、树的定义树是计算机算法最重要的⾮线性结构。
树中每个数据元素⾄多有⼀个直接前驱，但可以有多个直接后继。
树是⼀种以分⽀关系定义的层次结构。
a.树是n(≥0)结点组成的有限集合。
{N.沃恩}(树是n(n≥1)个结点组成的有限集合。
{D.E.Knuth})在任意⼀棵⾮空树中：⑴有且仅有⼀个没有前驱的结点----根(root)。
⑵当n>1时，其余结点有且仅有⼀个直接前驱。
⑶所有结点都可以有0个或多个后继。
b. 树是n(n≥0)个结点组成的有限集合。
在任意⼀棵⾮空树中：⑴有⼀个特定的称为根（root）的结点。
⑵当n>1时，其余结点分为ｍ（ｍ≥0）个互不相交的⼦集T1，T2，…，Tm。
每个集合本⾝⼜是⼀棵树，并且称为根的⼦树（subtree）树的固有特性---递归性。
即⾮空树是由若⼲棵⼦树组成，⽽⼦树⼜可以由若⼲棵更⼩的⼦树组成。
树的基本操作1、InitTree(&T) 初始化2、DestroyTree(&T) 撤消树3、CreatTree(&T,F) 按F的定义⽣成树4、ClearTree(&T) 清除5、TreeEmpty(T) 判树空6、TreeDepth(T) 求树的深度7、Root(T) 返回根结点8、Parent(T,x) 返回结点 x 的双亲9、Child(T,x,i) 返回结点 x 的第i 个孩⼦10、InsertChild(&T,&p,i,x) 把 x 插⼊到 P的第i棵⼦树处11、DeleteChild(&T,&p,i) 删除结点P的第i棵⼦树12、traverse(T) 遍历树的结点：包含⼀个数据元素及若⼲指向⼦树的分⽀。
●结点的度: 结点拥有⼦树的数⽬●叶结点: 度为零的结点●分枝结点: 度⾮零的结点●树的度: 树中各结点度的最⼤值●孩⼦: 树中某个结点的⼦树的根●双亲: 结点的直接前驱●兄弟: 同⼀双亲的孩⼦互称兄弟●祖先: 从根结点到某结点j 路径上的所有结点（不包括指定结点）。
基本二叉树知识讲解一、有关二叉树的学习性质1：二叉树上叶子结点数等于度为2的结点数加1。
性质2：二叉树的第i层上至多有2的i次方减1个结点（i>=1）。
性质3：深度为h的二叉树至多有2的h次方减1个结点。
满二叉树：在一棵二叉树中，当第i层的结点树为2的i次方减1个时，称此层的结点数是满的。
当一棵二叉树中的每一层都满时，称此树为满二叉树。
特性：除叶子结点以外的其他的结点的度皆为2，且叶子结点在同一层上。
深度为h的满二叉树中的结点数为2的h次方减1。
性质4：设含有n个结点的完全二叉树的深度为k，则k=(int)(log2n)+1,即深度k等于log2n的整数部分再加1。
二叉树的存储结构1：顺序存储结构二叉树的顺序存储结构类型定义如下：#define TREEMINSIZE 10typedef struct{BTreeDT(数据类型) *base;int spacesize;BTreeDT nullvalue;}SeqTree;2：链式存储结构（一般的二叉树主要采用链式存储结构通常有二叉链表和三叉链表两种形式）1>二叉链表存储结构二叉链表中的每个结点由data，lchild和rchild三个域组成，定义如下：typedef struct bkbtnode{BTreeDT data;struct bkbtnode *lchild;struct bkbtnode *rchild;}BTNode,*BKBTree;在二叉链表中，查找某结点的孩子很容易实现，但查找某结点的双亲不方便。
一棵喊有n个结点的二叉树采用二叉链表存储时，将有2n-（n-1）=n+1个指针域是空的。
2>三叉链表存储结构typedef struct tkbtnode{BTreeDT data;struct tkbtnode *lchild;struct tkbtnode *rchild;struct tkbtnode *parent;}TKBTNode,*TKBTree;其中，parent域存放该结点双亲的指针。
二叉树结点计算方法二叉树是一种常见的数据结构，它由结点和连接结点的边组成。
每个结点最多有两个子结点，称为左子结点和右子结点。
在二叉树中，每个结点都有一个值，可以用来存储任何类型的数据。
计算二叉树结点的方法主要有以下几种：1.求二叉树的结点个数：-递归法：计算二叉树的结点个数可以使用递归的方式，首先判断根结点是否为空，如果为空，则返回0；否则，返回左子树的结点个数加上右子树的结点个数再加1，即根结点自身的个数。
递归地计算左右子树的结点个数，直到叶子结点为空，递归结束。
2.求二叉树的叶子结点个数：-递归法：计算二叉树的叶子结点个数也可以使用递归的方式，首先判断根结点是否为空，如果为空，则返回0；否则，如果根结点的左右子树都为空，则返回1，表示根结点为叶子结点。
递归地计算左右子树的叶子结点个数，通过累计求和的方式得到最终的结果。
3.求二叉树的深度：-递归法：计算二叉树的深度可以使用递归的方式，首先判断根结点是否为空，如果为空，则返回0；否则，分别计算左子树和右子树的深度，然后取两者中的较大值，再加上根结点自身的深度，即可得到二叉树的深度。
递归地计算左右子树的深度，直到叶子结点为空，递归结束。
4.求二叉树的最小深度：-递归法：计算二叉树的最小深度可以使用递归的方式，首先判断根结点是否为空，如果为空，则返回0；否则，如果根结点的左右子树都为空，则返回1，表示根结点为叶子结点。
如果根结点的左子树为空，则取右子树的最小深度；如果根结点的右子树为空，则取左子树的最小深度；否则，取左右子树中的较小深度。
递归地计算左右子树的最小深度，通过取较小值的方式得到最终的结果。
以上是常见的计算二叉树结点的方法，它们都可以通过递归的方式实现。
在实际应用中，可以根据具体的需求选择适当的方法来计算二叉树的结点。
以二叉树或树作为表的组织形式，称为树表，它是一类动态查找表，不仅适合于数据查找，也适合于表插入和删除操作。
常见的树表：二叉排序树平衡二叉树B-树B+树9.3.1 二叉排序树二叉排序树（简称BST）又称二叉查找（搜索）树，其定义为：二叉排序树或者是空树，或者是满足如下性质（BST性质）的二叉树：❶若它的左子树非空，则左子树上所有节点值（指关键字值）均小于根节点值；❷若它的右子树非空，则右子树上所有节点值均大于根节点值；❸左、右子树本身又各是一棵二叉排序树。
注意：二叉排序树中没有相同关键字的节点。
二叉树结构满足BST性质：节点值约束二叉排序树503080209010854035252388例如:是二叉排序树。
66不试一试二叉排序树的中序遍历序列有什么特点？二叉排序树的节点类型如下：typedef struct node{KeyType key;//关键字项InfoType data;//其他数据域struct node*lchild,*rchild;//左右孩子指针}BSTNode;二叉排序树可看做是一个有序表，所以在二叉排序树上进行查找，和二分查找类似，也是一个逐步缩小查找范围的过程。
1、二叉排序树上的查找Nk< bt->keybtk> bt->key 每一层只和一个节点进行关键字比较！∧∧p查找到p所指节点若k<p->data，并且p->lchild=NULL，查找失败。
若k>p->data，并且p->rchild=NULL，查找失败。
查找失败的情况加上外部节点一个外部节点对应某内部节点的一个NULL指针递归查找算法SearchBST()如下（在二叉排序树bt上查找关键字为k的记录，成功时返回该节点指针，否则返回NULL）：BSTNode*SearchBST(BSTNode*bt,KeyType k){if(bt==NULL||bt->key==k)//递归出口return bt;if(k<bt->key)return SearchBST(bt->lchild,k);//在左子树中递归查找elsereturn SearchBST(bt->rchild,k);//在右子树中递归查找}在二叉排序树中插入一个关键字为k的新节点，要保证插入后仍满足BST性质。
二叉树的各种遍历算法及其深度算法一、二叉树的遍历算法二叉树是一种常见的数据结构，遍历二叉树可以按照根节点的访问顺序将二叉树的结点访问一次且仅访问一次。
根据遍历的顺序不同，二叉树的遍历算法可以分为三种：前序遍历、中序遍历和后序遍历。
1. 前序遍历（Pre-order Traversal）：首先访问根节点，然后遍历左子树，最后遍历右子树。
可以用递归或者栈来实现。
2. 中序遍历（In-order Traversal）：首先遍历左子树，然后访问根节点，最后遍历右子树。
可以用递归或者栈来实现。
3. 后序遍历（Post-order Traversal）：首先遍历左子树，然后遍历右子树，最后访问根节点。
可以用递归或者栈来实现。
二、二叉树的深度算法二叉树的深度，也叫做高度，指的是从根节点到叶子节点的最长路径上的节点数目。
可以使用递归或者层次遍历的方式来计算二叉树的深度。
1.递归算法：二叉树的深度等于左子树的深度和右子树的深度的较大值加一、递归的终止条件是当节点为空时，深度为0。
递归的过程中通过不断递归左子树和右子树，可以求出二叉树的深度。
2.层次遍历算法：层次遍历二叉树时，每遍历完一层节点，深度加一、使用一个队列来辅助层次遍历，先将根节点加入队列，然后依次取出队列中的节点，将其左右子节点加入队列，直到队列为空，完成层次遍历。
三、示例为了更好地理解二叉树的遍历和求深度的算法，我们以一个简单的二叉树为例进行说明。
假设该二叉树的结构如下：A/\BC/\/\DEFG其中，A、B、C、D、E、F、G分别代表二叉树的结点。
1.前序遍历：A->B->D->E->C->F->G2.中序遍历：D->B->E->A->F->C->G3.后序遍历：D->E->B->F->G->C->A4.深度：2以上是针对这个二叉树的遍历和深度的计算示例。
完全二叉树的总结点数公式在解决完全二叉树问题时，有一个重要的公式可以帮助我们计算完全二叉树的总结点数。
根据完全二叉树的特性，我们可以通过判断左子树或右子树的高度来确定完全二叉树是满二叉树还是完全二叉树，并利用递归的方式计算总结点数。
下面是完全二叉树总结点数的公式：若完全二叉树的高度为h，根节点的高度为0，那么：-如果左子树的高度等于右子树的高度（即完全二叉树是满二叉树），则左子树为高度为h-1的满二叉树，其总结点数为2^(h-1)-1，右子树为高度为h-2的完全二叉树，其总结点数可以通过递归的方式计算。
-如果左子树的高度大于右子树的高度（即完全二叉树不是满二叉树），则右子树为高度为h-1的满二叉树，其总结点数为2^(h-2)-1，左子树为高度为h-1的完全二叉树，其总结点数可以通过递归的方式计算。
具体地，我们可以通过以下步骤来计算完全二叉树的总结点数：1.对于给定的完全二叉树，首先计算树的高度h。
可以从根节点开始，通过逐层遍历左子树来计算。
2.判断左子树和右子树的高度是否相等。
如果相等，表示完全二叉树是满二叉树，根据上述公式计算左子树和右子树的总结点数。
3.如果左子树的高度大于右子树的高度，表示完全二叉树不是满二叉树，根据上述公式计算左子树和右子树的总结点数。
4.将左子树和右子树的总结点数相加，并加上根节点，即得到完全二叉树的总结点数。
下面是一个具体的例子来说明完全二叉树的总结点数公式：```/\23/\/\4567```对于上述的完全二叉树，根节点的高度为0，左子树的高度为1，右子树的高度为2、因此，左子树为高度为1的完全二叉树，其总结点数为2^1-1=1，右子树为高度为2的完全二叉树，其总结点数为2^2-1=3、将左子树和右子树的总结点数相加，并加上根节点，即1+3+1=5，所以该完全二叉树的总结点数为5综上所述，完全二叉树的总结点数公式为根据完全二叉树的特性来判断树是满二叉树还是完全二叉树，并利用递归的方式计算总结点数。
树和二叉树的计算公式
树和二叉树是计算机科学中重要的数据结构，它们可以用于各种算法和数据处理应用。
在计算树和二叉树的性质和操作时，需要使用一些计算公式。
一、树的计算公式
1. 节点总数公式：假设一棵树有n个节点，那么它的节点总数
为n=1+r1+r2+...+rk，其中r1、r2、...、rk分别表示每个节点的
子节点数。
2. 叶子节点数公式：一棵树的叶子节点数等于每个非叶节点子
节点数之和加1，即l=r1+r2+...+rk+1。
3. 深度公式：一棵树的深度为从根节点到最深叶子节点的路径
长度，可以用递归的方式计算：d(T)=max{d(T1),d(T2),...,d(Tk)}+1，其中T1、T2、...、Tk是根节点的子树，d(Ti)表示第i个子树的深度。
二、二叉树的计算公式
1. 节点总数公式：假设一棵二叉树有n个节点，那么它的节点
总数为n=2^h-1，其中h为树的高度。
2. 叶子节点数公式：一棵二叉树的叶子节点数等于度数为2的
节点数加1，即l=n/2+1。
3. 深度公式：一棵二叉树的深度为从根节点到最深叶子节点的
路径长度，可以用递归的方式计算：d(T)=max{d(T1),d(T2)}+1，其
中T1、T2是根节点的左右子树，d(Ti)表示第i个子树的深度。
以上是树和二叉树的一些常用计算公式，可以用于分析和设计算法，帮助开发人员更好地理解和应用这些数据结构。
数据结构树和二叉树知识点总结
1.树的概念：树是一种非线性的数据结构，由节点和边构成，每个节点只能有一个父节点，但可以有多个子节点。
2. 二叉树的概念：二叉树是一种特殊的树结构，每个节点最多只有两个子节点，一个是左子节点，一个是右子节点。
3. 二叉树的遍历：二叉树的遍历分为前序遍历、中序遍历和后序遍历三种方式。
前序遍历是先访问根节点，再访问左子树，最后访问右子树；中序遍历是先访问左子树，再访问根节点，最后访问右子树；后序遍历是先访问左子树，再访问右子树，最后访问根节点。
4. 二叉搜索树：二叉搜索树是一种特殊的二叉树，它满足左子树中所有节点的值均小于根节点的值，右子树中所有节点的值均大于根节点的值。
因此，二叉搜索树的中序遍历是一个有序序列。
5. 平衡二叉树：平衡二叉树是一种特殊的二叉搜索树，它的左子树和右子树的高度差不超过1。
平衡二叉树的插入和删除操作可以保证树的平衡性，从而提高树的查询效率。
6. 堆：堆是一种特殊的树结构，它分为最大堆和最小堆两种。
最大堆的每个节点的值都大于等于其子节点的值，最小堆的每个节点的值都小于等于其子节点的值。
堆常用于排序和优先队列。
7. Trie树：Trie树是一种特殊的树结构，它用于字符串的匹配和检索。
Trie树的每个节点代表一个字符串的前缀，从根节点到叶子节点的路径组成一个完整的字符串。
以上是数据结构树和二叉树的一些基本知识点总结，对于深入学
习数据结构和算法有很大的帮助。
树与二叉树算法1．以二叉树表示算术表达式，根结点用于存储运算符。
若能先分别求出左子树和右子树表示的子表达式的值，最后就可以根据根结点的运算符的要求，计算出表达式的最后结果。
typedef struct node{ElemType data; float val;char optr; //只取‘+’，‘-’，‘*’，‘/’struct node *lchild，*rchild }BiNode,*BiTree;float PostEval(BiTree bt) // 以后序遍历算法求以二叉树表示的算术表达式的值{float lv,rv;if(bt!=null){lv=PostEval(bt->lchild); // 求左子树表示的子表达式的值rv=PostEval(bt->rchild); // 求右子树表示的子表达式的值switch(bt->optr){ case‘+’: value=lv+rv; break;case‘-’: value=lv-rv;break;case‘*’: value=lv*rv;break;case‘/’: value=lv/rv;} }return(value);}32.二叉树采取顺序结构存储，是按完全二叉树格式存储的。
对非完全二叉树要补上“虚结点”。
由于不是完全二叉树，在顺序结构存储中对叶子结点的判定是根据其左右子女为0。
叶子和双亲结点下标间的关系满足完全二叉树的性质。
int Leaves(int h) //求深度为h以顺序结构存储的二叉树的叶子结点数{ int BT[]; int len=2h-1, count=0; //BT是二叉树结点值一维数组，容量为2hfor (i=1;i<=len;i++) //数组元素从下标1开始存放if (BT[i]!=0) //假定二叉树结点值是整数，“虚结点”用0填充if(i*2)>len) count++; //第i个结点没子女，肯定是叶子else if(BT[2*i]==0 && 2*i+1<=len && BT[2*i+1]==0) count++; //无左右子女的结点是叶子return (count)} //结束Leaves★★建立二叉树算法★★6．二叉树是递归定义的，以递归方式建立最简单。
判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。
BiTree Creat() //建立二叉树的二叉链表形式的存储结构{ElemType x；BiTree bt;scanf(“%d”,&x); //本题假定结点数据域为整型if(x==0) bt=null;else if(x>0){bt=(BiNode *)malloc(sizeof(BiNode));bt->data=x; bt->lchild=creat(); bt->rchild=creat();}else error(“输入错误”)；return(bt);}//结束 BiTreeint JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是，返回1，否则，返回0{int tag=0; BiTree p=bt, Q[]; // Q是队列，元素是二叉树结点指针，容量足够大if(p==null) return (1);QueueInit(Q); QueueIn(Q,p); //初始化队列，根结点指针入队while (!QueueEmpty(Q)){ p=QueueOut(Q); //出队if (p->lchild && !tag) QueueIn(Q,p->lchild); // tag==0结点不空，左子入队else {if (p->lchild) return 0; //tag==1前边已有结点为空，本结点不空else tag=1;} // p->lchild==null首次出现结点为空if (p->rchild && !tag) QueueIn(Q,p->rchild); // tag=0结点不空，右子女入队else {if (p->rchild) return 0; else tag=1; }} //whilereturn 1; //是完全二叉树} //JudgeComplete[算法讨论]完全二叉树证明还有其它方法。
判断时易犯的错误是证明其左子树和右子数都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。
7．BiTree Creat(ElemType A[],int i)//n个结点的完全二叉树存于一维数组A中，本算法据此递归建立以二叉链表表示的完全二叉树{ BiTree tree;if (i<=n){tree=(BiTree)malloc(sizeof(BiNode)); tree->data=A[i];if(2*i>n) tree->lchild=null；else tree->lchild=Creat(A,2*i)；个元素是根结点。
本题中采用队列结构。
typedef struct{BiTree bt; //二叉树结点指针int num; }tnode // num是结点在一维数组中的编号tnode Q[maxsize]; //循环队列,容量足够大void creat(BiTree T,ElemType BT[ ])//深度h的二叉树存于一维数组BT[1:2h-1]中，本算法生成该二叉树的二叉链表存储结构{tnode tq; //tq是队列元素int len=2h-1; //数组长度T=(BiTree)malloc(sizeof(BiNode)); //申请结点T->data=BT[1]; //根结点数据tq.bt=T; tq.num=1;Q[1]=tq; //根入队列front=0;rear=1; //循环队列头、尾指针while(front!=rear) //当队列不空时循环{ front=(front+1) % maxsize ;tq=Q[front] ; p=tq.bt; i=tq.num ; //出队，取出结点及编号if (BT[2*i]==‘#’||2*i>len) p->lchild=null; //左子树为空，‘#’表示虚结点else //建立左子女结点并入队列{ p->lchild=(BiTree) malloc(sizeof(BiNode)); //申请结点空间p->lchild data=BT[2*i]; // 左子女数据tq.bt=p->lchild; tq.num=2*i;rear=(rear+1) % maxsize ;//计算队尾位置Q[rear]=tq; //左子女结点及其编号入队}if(BT[2*i+1]==‘#’|| 2*i+1>len) p->rchild=null; //右子树为空else //建立右子女结点并入队列{ p->rchild=(BiTree)malloc(sizeof (BiNode); //申请结点空间p->rchild->data=BT[2*i+1];tq.bt=p->rchild; tq.num=2*i+1;rear=(rear+1)%maxsize; Q[rear]=tq; //计算队尾位置,右子女及其编号入队}} //while}//结束creat[算法讨论] 本题中的虚结点用‘#’表示。
应根据二叉树的结点数据的类型而定。
10．本题静态链表中结点是按动态二叉链表的前序遍历顺序存放的。
首先对动态二叉链表的二叉树进行前序遍历，填写静态链表的“下标”和data域，再对动态二叉链表的二叉树进行层次遍历，设队列Q，填写静态链表的lchild域和rchild域。
typedef struct node //静态链表结点结构{ ElemType data; //结点数据int row,lchild,rchild ; //下标，左右子女}component；component st[]; //st容量足够大struct node {BiTree t; int idx; }qbt;static int num=0;●void PreOrder(BiTree bt); // 前序遍历二叉树，填写静态链表的“下标”和data域{ if (bt){ st[++num].data=bt->data; st[num].row=num;PreOrder(bt->lchild); PreOrder(bt->rchild);}}●int Locate(ElemType x) //在静态链表中查二叉树结点的下标{ for (i=1;i<=num;i++) if (st[i].data==x) return (i);}●void DynaToST (BiTree bt) //将二叉树的动态二叉链表结构转为静态链表结构{ int i=0; //i为静态链表st的下标if (bt!=null){ QueueInit(Q); //Q是队列，容量足够大，队列元素是qbtqbt.t=bt; qbt.idx=1; QueueIn(Q,qbt); st[1].data=bt->data;while(!QueueEmpty(Q)){ qbt=QueueOut(Q); //出队列p=qbt.t; i=qbt.idx; //二叉树结点及在静态链表中的下标if (p->lchild!=null) //若左子存在,查其在静态链表中的下标, 填lchild域值{ lch=Locate(p->lchild->data)； st[i].lchild=lch; //下标填入“静态链表”qbt.t=p->lchild; qbt.idx=lch; QueueIn(Q,qbt); }else st[i].lchild=0; //无左子，其lchild域填0if (p->rchild!=null) //若右子存在,查其在静态链表中的下标，填rchild域值{ rch=Locate(p->->rchild->data)； st[i].rchild=rch;qbt.t=p->rchild; qbt.idx=rch; QueueIn(Q,qbt); }else st[i].rchild=0; //无右子，其lchild域填0}//while}//结束DynaToST49.二叉树按完全二叉树格式输入，对非完全二叉树，要补上“虚结点”。
