网站建设学习 服务器,西安今天刚刚发生的新闻,临清住房建设网站,最近时政新闻1 问题
比如我们搜索二叉树如下#xff0c;我们需要变成双向链表 2 分析
我们知道这个变成双向链接的时候是按照树的中序遍历打印的#xff0c;我们只需要在中序遍历打印的时候操作该节点#xff0c;我们可以用临时变量保存这个节点#xff0c;同时我们也需要单独增加一…1 问题
比如我们搜索二叉树如下我们需要变成双向链表 2 分析
我们知道这个变成双向链接的时候是按照树的中序遍历打印的我们只需要在中序遍历打印的时候操作该节点我们可以用临时变量保存这个节点同时我们也需要单独增加一个链表节点变量我们需要保证这个节点的左边指向是该链表节点然后该链表节点的右指向是这个节点然后我们再把这个节点赋值给这个链表节点就这样一直移动下去即可。 3 代码实现
我这里以下面的搜索二叉树进行操作的
42 61 3 5 7 #include stdio.h
#include stdlib.htypedef struct Tree
{int value;struct Tree* left;struct Tree* right;
} Tree;/** 把搜索二叉树转成双向链表我们按照中序遍历*/
void convertNode(Tree* node, Tree** lastNodeList)
{if (node NULL)return;Tree* pCurrent node;if (pCurrent-left ! NULL){convertNode(pCurrent-left, lastNodeList);}//这里就要进行我们每个节点的前后正确的指向了pCurrent-left *lastNodeList;if (*lastNodeList ! NULL){(*lastNodeList)-right pCurrent;}*lastNodeList pCurrent;if (pCurrent-right ! NULL){convertNode(pCurrent-right, lastNodeList);}
}/** 把翻转好的双向链表尾巴节点移动到链表头*/
Tree* convert(Tree* node, Tree* lastNodeList)
{if (node NULL || lastNodeList NULL){printf(node is NULL or lastNodeList is NULL\n);return NULL;}Tree* last NULL;convertNode(node, lastNodeList);//因为这个时候lastNodeList已经到了双向链表尾巴我们需要移动到链表头Tree* headNodeList lastNodeList;while (headNodeList ! NULL headNodeList-left ! NULL){headNodeList headNodeList - left;} return headNodeList;
}/** 双向链表从左到右打印*/
void printRightList(Tree* headNodeList)
{if (headNodeList NULL){printf(headNodeList is NULL\n);return;}printf(we will print list from left to right\n);Tree* pCurrent headNodeList;while (pCurrent ! NULL){printf(value is %d\n, pCurrent-value);pCurrent pCurrent-right;}
}/** 双向链表从右到左打印*/
void printLeftList(Tree* headNodeList)
{if (headNodeList NULL){printf(headNodeList is NULL\n);return;}printf(we will print list from right to left\n);Tree* pCurrent headNodeList;//先把链表头结点移动为链表的尾巴while (pCurrent-right ! NULL){//printf(value is %d\n, pCurrent-value);pCurrent pCurrent-right;}//pCurrent pCurrent-left;while (pCurrent ! NULL){printf(value is %d\n, pCurrent-value);pCurrent pCurrent-left;}
}int main(void)
{Tree *node1 , *node2 , *node3, *node4, *node5, *node6, *node7;node1 (Tree *)malloc(sizeof(Tree));node2 (Tree *)malloc(sizeof(Tree));node3 (Tree *)malloc(sizeof(Tree));node4 (Tree *)malloc(sizeof(Tree));node5 (Tree *)malloc(sizeof(Tree));node6 (Tree *)malloc(sizeof(Tree));node7 (Tree *)malloc(sizeof(Tree)); node1-value 4;node2-value 2;node3-value 6;node4-value 1;node5-value 3;node6-value 5;node7-value 7;node1-left node2;node1-right node3;node2-left node4;node2-right node5;node3-left node6;node3-right node7;node4-left NULL;node4-right NULL;node5-left NULL;node5-right NULL;node6-left NULL;node6-right NULL;node7-left NULL;node7-right NULL;Tree* list (Tree *)malloc(sizeof(Tree));if (!list){printf(malloc list fail\n);return -1;}Tree* firstNodeList NULL;//convertNode(node1, list);firstNodeList convert(node1, list);if (firstNodeList NULL){printf(firstNodeList is NULL\n);return -1;}printRightList(firstNodeList);printLeftList(firstNodeList);return 0;
} 4 运行结果
we will print list from left to right
value is 0
value is 1
value is 2
value is 3
value is 4
value is 5
value is 6
value is 7
we will print list from right to left
value is 7
value is 6
value is 5
value is 4
value is 3
value is 2
value is 1
value is 0
