---答题基础知识储备---
二元树(二叉树):在计算机科学中,二叉树指的是每个节点最多只能有两个子树的树结构,二叉树的两个子树有左右之分,次序不能颠倒,通常两个子树分别被称为左子树和右子树;
遍历二叉树:遍历是对树的一种最基本运算,所谓遍历二叉树,就是按照某一顺序,走完二叉树的所有节点,使每个节点都会被访问一次,且只被访问一次。由于二叉树非线性结构,遍历性质上其实就是将二叉树转化为线性序列来表示。
设L、D、R分别表示遍历左子树、访问根节点、遍历右子树,则对一棵二叉树的遍历有三种情况:DLR(先根次序遍历,先序遍历)、LDR(中根次序遍历,中序遍历)、LRD(后根次序遍历,后序遍历)。
另外的,还有层次遍历:即按照上下层次来进行访问,由上至下,由左至右,先访问根节点,然后访问子节点,然后访问子节点的子节点...越往下,层次越低,两个子节点层次相等;通常使用队列来实现。
层次遍历队列实现原理:1.初始化,将第一个节点压入队列;2.弹出当前队列第一个元素;3.判断这个元素的左右子节点,如果存在则由左到右压入;4.继续2的步骤,直到队列中没有元素。
二元查找树:一种为了“查找”的诞生的二叉树,在二元查找树的每一个单位二叉树中,左子节点 < 根节点 < 右子节点;主要用于快速查找,结果大于根节点->右子节点,结果小于根节点->左子节点,直到找到合适的值为止。
------
题目:
输入一棵二元查找树,将该二元查找树转化为一个排序的双向链表;要求不能创建新的节点,只调整指针的指向。
示例输入:
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表输出:
4=6=8=10=12=14=16
首先,我们定义的二元查找树节点的数据结构如下:
1 2 3 4 5 6 | struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; |
答题分析:
本题要求是将输入的树结构转化为链表结构,所以可以使用遍历来实现;同时,本题要求对输入树元素进行排序,根据二元查找树的特性(左>根>右),应当使用中序遍历来实现。
解答:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | BSTreeNode *pHead = NULL; BSTreeNode *pListIndex=NULL; //中序遍历二元树 void ergodicBSTree(BSTreeNode * pCurrent){ if (pCurrent == NULL){ return ;} //左子树不为空 if (pCurrent->m_pLeft!=NULL){ ergodicBSTree(pCurrent->m_pLeft); } //将节点加入链表 convertToDoubleList(pCurrent); //右子树不为空 if (pCurrent->m_pRight!=NULL){ ergodicBSTree(pCurrent->m_pRigth); } } //将二叉树转化成List void converToDoubleList(BSTreeNode * pCurrent){ // 当前链表元素的左指针指向前一个元素 pCurrent->m_pLeft = pListIndex; if (pListIndex!=NULL){ // 如果不是第一个元素 前一个元素的右指针指向当前元素 pListIndex->m_pRight=pCurrent; } else { //头指针 pHead = pCurrent; } // 将pListIndex赋值为当前指针 pListIndex = pCurrent; cout<<pCurrent->m_nValue<<endl; }
|
友情提示:垃圾评论一律封号...