首页天道酬勤二叉树中序遍历最后一个节点,中序遍历一棵二叉树的节点就可得到

二叉树中序遍历最后一个节点,中序遍历一棵二叉树的节点就可得到

admin 07-13 16:04 270次浏览
程序要求 建立二叉树的二叉链表存储结构,实现二叉树的前序、中序、后序递归遍历计算二叉树中叶子结点的数目计算二叉树的深度求二叉树结点个数 算法分析

遍历二叉树
先序遍历二叉树:
若二叉树为空,则空操作;否则
(1)访问根结点;(2)先序遍历左子树;(3)先序遍历右子树。
中序遍历二叉树:
若二叉树为空,则空操作;否则
(1)中序遍历左子树;(2)访问根结点;(3)中序遍历右子树。
后序遍历二叉树:
若二叉树为空,则空操作;否则
(1)后序遍历左子树;(2)后序遍历右子树;(3)访问根结点。
统计二叉树中叶子结点的个数
在遍历算法中增添一个“计数”的参数,遍历二叉树,在遍历过程中查找叶子结点。若是叶子,则计数参数+1。
求二叉树的深度
(1)二叉树的深度应为其左、右子树深度的最大值+1。
(2)先分别求得左、右子树的深度
(3)求得左、右子树的深度,取其最大值,然后加+1 ,即为二叉树的深度。
求二叉树的节点个数
(1)二叉树的深度应为其左、右子树节点个数的和+1。
(2)若二叉树为空,节点个数为零
(3)求得二叉树左、右子树的节点个数,二叉树的节点个数为左右子树节点个数之和+1。

程序代码 #include <stdio.h>#include <malloc.h>typedef int Status ;typedef char TElemType;#define ERROR 0#define OK 1typedef struct BiTNode {//定义二叉链表 TElemType data; struct BiTNode *lchild,*rchild; //左右孩子指针}BiTNode,*BiTree;Status CreateBiTree(BiTree &T)//按照先序顺序(根——左——右),生成一个二叉树,参数为根节点T的引用{ char ch;scanf("%c",&ch);//if(ch==' ')T=NULL;if(ch=='#')T=NULL;//若输入的ch为’#’,则认为该节点为空,此处不使用’space’的原因为空格不易识别 else { T=(BiTree)malloc(sizeof(BiTNode));//为节点申请新的存储空间 T->data=ch;//将输入的ch赋给T的数据域 CreateBiTree(T->lchild);//生成左子树 CreateBiTree(T->rchild);//生成右子树,顺序符合先序顺序,左子树和右子树分别都是二叉树,进行递归调用, } return OK;}Status Visit(TElemType e)//Visit函数,简单的遍历函数,输出节点数据域的值,参数为e{ printf("%c ",e); return OK;}Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e)) // 先序遍历二叉树,参数为根节点的指针T以及Visit函数{ if (T){//根——左——右 if (Visit(T->data)) if (PreOrderTraverse(T->lchild,Visit))//遍历左子树 if (PreOrderTraverse(T->rchild,Visit))//遍历右子树 return OK; return ERROR; }else return OK;}//PreOrderTraverseStatus InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))//中序遍历二叉树{ if (T){// 左——根——右 if (InOrderTraverse(T->lchild,Visit))//遍历左子树 if (Visit(T->data)) if (InOrderTraverse(T->rchild,Visit))//遍历右子树 return OK; return ERROR; }else return OK;}//InOrderTraverseStatus PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e)) //后序遍历二叉树{ if (T){//左——右——根 if (PostOrderTraverse(T->lchild,Visit))//遍历左子树 if (PostOrderTraverse(T->rchild,Visit))//遍历右子树 if (Visit(T->data)) return OK; return ERROR; }else return OK; printf("\n");}//PostOrderTraversevoid Countleaf(BiTree T, int &count)//求叶子节点的个数,参数为根节点的指针T以及计数变量count,无返回值{ if (T){ if((T->lchild==NULL)&&(T->rchild==NULL))++count;//冷酷的溪流节点左子树与右子树都为空,那么该节点为叶子节点,计数变量count加1 Countleaf( T->lchild,count); Countleaf( T->rchild,count); }}//Countleafint BiTreeDepth(BiTree T) // 返回二叉树的深度, 参数为树根的指针T,返回值为二叉树的深度depthval{ int depthval,depthLeft,depthRight;//定义三个整型变量,分别为二叉树的深度、左子树的深度以及右子树的深度 if (!T)depthval = 0;//若二叉树为空,则深度为0 else { depthLeft=BiTreeDepth(T->lchild);//求左子树的深度 depthRight=BiTreeDepth(T->rchild);//求右子树的深度,左右子树分别又都是二叉树,进行递归调用//if(depthLeft>depthRight) // depthval=1+depthLeft; //else // depthval=1+depthRight; depthval=1+(depthLeft>depthRight?depthLeft:depthRight);//二叉树的深度为左子树的深度和右子树的深度中较大的那个再加1. } return depthval;}int BiTreeSize(BiTree T){ if(T==NULL) return 0; else return 1+BiTreeSize(T->lchild)+BiTreeSize(T->rchild);}int main(){ int c=0,depth,size; BiTNode *T; printf("Please input a bitree:('#'--NULL):\n"); CreateBiTree(T);//生成二叉树 printf("PreOrderTraverse:\n"); PreOrderTraverse(T,Visit);printf("\n");//先序遍历 printf("InOrderTraverse:\n"); InOrderTraverse(T,Visit);printf("\n");//中序遍历 printf("PostOrderTraverse:\n"); PostOrderTraverse(T,Visit);printf("\n");//后序遍历 Countleaf(T,c);//求叶子节点个数 printf("The num of the leafnode:%d",c); depth=BiTreeDepth(T);printf("\n");//求二叉树深度 printf("The Depth of the BiTree:%d",depth); size=BiTreeSize(T);printf("\n");//求二叉树结点个数 printf("The Size of the BiTree:%d",size);printf("\n"); return 0;} 运行结果


SpringCloudAlibaba使用Sentinel实现接口限流软件 app开发(打扑克外国人直播软件app开发)如何自己创建一个app(如何自己创建一个appstore的账号)使用react创建上下文时找不到命名空间'ctx'错误-Typescript【Flink实时计算 UFlink】UFlink开发注意事项JS词法环境和执行上下文怎么使用GridView实现桌面图标显示
二叉树的题目,二叉树 面试题 Java中分页数据导出,MySQL 分页查询
相关内容