网站建设实训实训心得,公众号编辑器哪个好,圣辉友联刘金鹏做网站,中国建设银行 官方网站文章目录一、二叉树的深度优先遍历0.建立一棵树1. 前序遍历2.中序遍历3. 后序遍历二、二叉树的广度优先遍历层序遍历三、有关二叉树练习一、二叉树的深度优先遍历
学习二叉树结构#xff0c;最简单的方式就是遍历。
所谓二叉树遍历(Traversal)是按照某种特定的规则#xff…
文章目录一、二叉树的深度优先遍历0.建立一棵树1. 前序遍历2.中序遍历3. 后序遍历二、二叉树的广度优先遍历层序遍历三、有关二叉树练习一、二叉树的深度优先遍历
学习二叉树结构最简单的方式就是遍历。
所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉 树中的节点进行相应的操作并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。
遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。
按照规则二叉树的遍历有前序/中序/后序的递归结构遍历
0.建立一棵树
typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;}BTNode;int main()
{BTNode* A (BTNode*)malloc(sizeof(BTNode));A-data A;A-left NULL;A-right NULL;BTNode* B (BTNode*)malloc(sizeof(BTNode));B-data B;B-left NULL;B-right NULL;BTNode* C (BTNode*)malloc(sizeof(BTNode));C-data C;C-left NULL;C-right NULL;BTNode* D (BTNode*)malloc(sizeof(BTNode));D-data D;D-left NULL;D-right NULL;BTNode* E (BTNode*)malloc(sizeof(BTNode));E-data E;E-left NULL;E-right NULL;A-left B;A-right C;B-left D;B-right E;return 0;
}结果如下
1. 前序遍历
访问根结点的操作发生在遍历其左右子树之前。
先访问根节点再到左子节点然后到右子节点。 根-左-右
//后序遍历
void PrevOrder(BTNode* root)
{if (root NULL){return;}printf(%c , root-data);PrevOrder(root-left);PrevOrder(root-right);
}2.中序遍历
中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。
先访问左子树再访问根再到右子树 左–根–右 由于NULL不打印出来故结果为 D-B-E-A-C
代码如下
//中序遍历
void InOrder(BTNode* root)
{if (root NULL){return;}InOrder(root-left);printf(%c , root-data);InOrder(root-right);
}代码分析
3. 后序遍历
后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
先访问左子节点再访问右子节点最后访问根。 左–右–根
分析结果如下 打印结果为 D E B C A
代码如下
//后续遍历
void PostOrder(BTNode* root)
{if (!root){return;}PostOrder(root-left);PostOrder(root-right);printf(%c , root-data);
}代码分析如下
二叉树的前序中序后序遍历结果如下
二、二叉树的广度优先遍历
层序遍历
层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1
层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第2层上的节点接着是第三层的节点
以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。
层序遍历就是一层一层地访问先访问第一层 再访问第二层。 核心思想是上一层出去带下一层进来
实现的过程不使用递归实现使用队列实现 借助队列先进先出的特点 队列源代码
typedef struct BinaryTreeNode* QDataType;typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq)
{assert(pq);pq-head NULL;pq-tail NULL;pq-size 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* del cur;cur cur-next;free(del);//del NULL;}pq-head pq-tail NULL;pq-size 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;if (pq-tail NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;
}void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* del pq-head;pq-head pq-head-next;free(del);}pq-size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-head NULL pq-tail NULL;
}
实现层序遍历过程中二叉树借助队列源代码 //借助队列的先进先出来实现层级递进
void LevelOrder(BTNode* root)
{//核心思路上一层出的时候带下一层Queue q;QueueInit(q);if (root){QueuePush(q, root);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%c , front-data);//访问下一层if (front-left){QueuePush(q, front-left);}if (front-right){QueuePush(q, front-right);}}printf(\n);QueueDestroy(q);
}三、有关二叉树练习
1.某完全二叉树按层次输出同一层从左到右的序列为 ABCDEFGH 。
该完全二叉树的前序序列为
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA解析 已知该树为完全二叉树第一层只有一个节点第二层有2个节点第三层有4个节点… 容易知道该完全二叉树的高度是4还原可得 根据前序序列遍历先根再左子节点再右子节点选A 2.二叉树的先序遍历和中序遍历如下先序遍历EFHIGJK;中序遍历HFIEJKG.则二叉树根结点为
A E
B F
C G
D H解析由二叉树的前序遍历可知根节点为E。 此时已经得出答案但我想还原这棵树 由中序遍历可知E是根节点那么E左边的所有节点为HFI右边的所有节点为JKG 由前序遍历可知E到F说明F是E的左子节点由中序遍历H到F说名H是F的左子节点。到这里可以还原二叉树的左半部分了右半部分同理。 3.设一课二叉树的中序遍历序列badce后序遍历序列bdeca
则二叉树前序遍历序列为____。
A adbce
B decab
C debac
D abcde解析 由二叉树的后序遍历可知根节点为a。 由中序序列可知a的左子节点只有b右子节点右dce 又由后序遍历往前推可知c是a的右子节点 到这里已经可以推出整棵树了 所以该树的前序序列为abcde选D 4.某二叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF
则按层次输出同一层从左到右的序列为
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF解析 由二叉树的后序遍历可知根节点为F由中序遍历可知根节点F无右子节点。 F的左节点有ABCDE 又因为前序和中序都相同那么只有一种情况 所以答案选A
