网站制度建设存在的问题,高端网站建设定制,项目网站建设,wordpress 留言本遍历二叉树的算法描述#xff08;递归定义#xff09;
先序遍历
若二叉树为空#xff0c;则空操作#xff1b;
否则
#xff08;1#xff09;访问根节点
#xff08;2#xff09;先序遍历左子树
#xff08;3#xff09;先序遍历右子树
中序遍历
若二叉树为空…遍历二叉树的算法描述递归定义
先序遍历
若二叉树为空则空操作
否则
1访问根节点
2先序遍历左子树
3先序遍历右子树
中序遍历
若二叉树为空则空操作
否则
1中序遍历左子树
2访问根节点
3中序遍历右子树
后序遍历
若二叉树为空则空操作
否则
1后序遍历左子树
2后序遍历右子树
3访问根节点
根据遍历序列确定二叉树
若二叉树中各结点的值均不同则二叉树的先序、中序、后序序列都是唯一的由二叉树的先序序列和中序序列或由后序序列和中序序列可以唯一确定一棵二叉树
由先序序列和中序序列确定二叉树
先序序列先访问的是根节点由此确定二叉树的根节点和左右子树然后重复此过程可递归的找到所有的左右子树和根节点
由后序序列和中序序列确定二叉树
后续遍历最后访问的是根节点其余同理
遍历算法实现
递归实现
先序遍历
Status PreOrderTraverse(BiTree T){if(tNULL)return OK;else{printf(%d, T-data);//访问根节点PreOrderTraverse(T-lchild);//递归遍历左子树PreOrderTraverse(T-rchild);//递归遍历右子树}
}中序遍历
Status InOrderTraverse(BiTree T){if(tNULL)return OK;else{InOrderTraverse(T-lchild);//递归遍历左子树printf(%d, T-data);//访问根节点InOrderTraverse(T-rchild);//递归遍历右子树}
}后序遍历
Status PostOrderTraverse(BiTree T){if(tNULL)return OK;else{PostOrderTraverse(T-lchild);//递归遍历左子树PostOrderTraverse(T-rchild);//递归遍历右子树printf(%d, T-data);//访问根节点}
}非递归实现
Status InOderTravese(BiTree T){BiTree p,q;InitStack(S);pT;while(p||!StackEmpty(S)){if(p){Push(S,p);pp-lchild;}else{Pop(S,q);printf(%c, q-data);pq-rchild;}}return OK;
}二叉树的层次遍历
对于一棵二叉树从根节点开始按从上到下从左到右的顺序访问每个结点
设计思路使用一个队列
1.将根节点进队
2.队不为空时出队结点p访问它
1.若它右左孩子将左孩子进队
2.若它有右孩子将右孩子进队
使用循环队列
typedef struct{BTNode data[MaxSize];int front,rear; //队头和队尾指针
}SqQueue;//循环队列void LevelOrder(BTNode *b){BTNode *p;SqQueue *qu;InitQueue(qu); //初始化队列enQueue(qu, b); //根节点进队while(!QueueEmpty(qu)){deQueue(qu, p); //出队结点pprintf(%c, p-data); //访问结点pif(p-lchild!NULL) //左孩子不为空则进队enQueue(qu, p-lchild);if(p-rchild!NULL) //右孩子不为空则进队enQueue(qu, p-rchild);}
}二叉树的建立
按先序遍历序列建立二叉树的二叉链表
// 构造二叉树前序遍历#表示空节点
Status CreateBiTree(BiTree T){cinch;if(ch#)TNULL;else{if(!(T(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T-datach; //生成根节点CreateBiTree(T-lchild); //构造左子树CreateBiTree(T-rchild); //构造右子树}return OK;
}复制二叉树
算法描述
如果是空树递归结束
否则申请新结点空间复制根节点
递归复制左子树
递归复制右子树
int Copy(BiTree T, BiTree NewT){if(TNULL){ //如果是空树返回0NewT NULL;return 0;}else{NewTnew BiTree;NewT-dataT-data;Copy(T-lchild, NewT-lchild);Copy(T-rchild, NewT-rchild);}
}计算二叉树的深度
算法思路
如果是空树则深度为0
否则递归计算左子树的深度m递归计算右子树的深度n二叉树深度为max(m,n)1
int Depth(BiTree T){if(TNULL)return 0;else{mDepth(T-lchild);nDepth(T-rchild);return mn?m1:n1;}
}计算二叉树结点总数
算法描述
如果是空树则结点个数为0
否则结点个数为左子树的结点个数右子树的结点个数再1
int NodeCount(BiTree T){if(TNULL)return 0;elsereturn NodeCount(T-lchild)NodeCount(T-rchild)1;
}计算叶子结点数
算法描述
如果是空树则叶子结点个数为0
否则叶子结点个数为左子树的叶子结点个数右子树的叶子结点个数
int LeafCount(BiTree T){if(TNULL)return 0;if(T-lchildNULLT-rchildNULL)return 1;elsereturn LeafCount(T-lchild)LeafCount(T-rchild);
}
