blocks|key|2857263|text|假设您有一个由3个节点组成的简单树|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2857264|B+<---+A+--->+C|code-block|syntax|javascript|2857265|沿着左边和右边走，获取每个节点的指针，然后有|2857266|B+->+C
B+<-+C|2857267|由于您的树是二进制的，它将由三个节点“子树”组成，这些节点“子树”可以递归地使用此策略。|2857268|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Q|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|S|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

assuming you have a simple tree of 3 nodes 

<pre><code>B &lt;--- A ---&gt; C
</code></pre>

walk down the left and right sides, get the pointers for each node, then have 

<pre><code>B -&gt; C
B &lt;- C
</code></pre>

Since your tree is binary, it will be composed of 3 node "subtrees" that can recursively use this strategy.

blocks|key|3695524|text|其思想是创建一个方法，将包含子树(子节点)的树节点转换为循环。如果一个节点已经转换了子节点(例如，递归调用返回后)，则通过将最大节点的大指针(下一步)指向最小节点，将最小节点的小指针指向最大节点，从而创建一个新的循环。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3695525|可能不完整，但它将接近于这一点：|3695526|tree_node+{
++++small
++++large
}

convert(node){
++++//base+case+1,+if+leaf+node
++++if+node.small+==+null+&&+node.large+==+null
++++++++return+(self,+self)

++++//recursively+convert+children
++++if+node.small+!=null
++++++++smallest,+larger+=+convert(node.small)
++++else
++++++++smallest+=+larger+=+self

++++if+node.large+!=null
++++++++smaller,+largest+=+convert(node.large)
++++else
++++++++smaller+=+largest+=+self

++++//wrap+the+ends+of+the+chain
++++largest.large+=+smallest
++++smallest.small+=+largest
++++//wrap+the+mid+part
++++smaller.small+=+larger
++++larger.large+=+small

++++//return+pointers+to+the+absolute+smallest+and+largest+of+this+subtree
++++return+(smallest,+largest)
}

//actually+doing+it+
convert(tree.root)|code-block|syntax|javascript|3695527|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

The idea is to create a method that converts a tree node containing subtrees (children nodes) into a loop. And given a node that has converted children (e.g. after recursive calls came back), you create a new loop by pointing the large pointer (next) of the largest node to the smallest node, and the small pointer of the smallest node to the largest node.

May not be complete, but it will be close to this:

<pre><code>tree_node {
 small
 large
}

convert(node){
 //base case 1, if leaf node
 if node.small == null &amp;&amp; node.large == null
 return (self, self)

 //recursively convert children
 if node.small !=null
 smallest, larger = convert(node.small)
 else
 smallest = larger = self

 if node.large !=null
 smaller, largest = convert(node.large)
 else
 smaller = largest = self

 //wrap the ends of the chain
 largest.large = smallest
 smallest.small = largest
 //wrap the mid part
 smaller.small = larger
 larger.large = small

 //return pointers to the absolute smallest and largest of this subtree
 return (smallest, largest)
}

//actually doing it 
convert(tree.root)
</code></pre>

blocks|key|237408|text|递归编程的关键是想象您已经有了解决方案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|237409|因此，您已经有了一个函数recLink(Tree+t)，它接收到指向树的指针，将该树转换为一个双链接的循环列表，并返回指向列表头部(最左边)节点的指针：|offset|length|style|CODE|237410|recLink(+n={Node:+left,+elt,+right})+=++//+pattern+match+tree+to+a+full+node
++rt+:=+recLink(+right);++++++++++++++++//+already
++lt+:=+recLink(+left);+++++++++++++++++//+++have+it
++n.right+:=+rt;+++++++n.left+:=+lt.left;++++++++//+middle+node
++lt.left.right+:=+n;++rt.left.right+:=+lt;++++++//+right+edges
++lt.left+:=+rt.left;++rt.left+:=+n;++++++
++return+lt;|code-block|syntax|javascript|237411|完成边缘箱(空子枝等)。:)|237412|entityMap^0|0|C|F|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|R|8|@$D|S|E|T|F|G]]|9|@]|A|$]]|$1|H|3|I|5|J|7|U|8|@]|9|@]|A|$K|L]]|$1|M|3|N|5|6|7|V|8|@]|9|@]|A|$]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

The key to recursive programming is to imagine you already have the solution.

So, you already have a function <code>recLink(Tree t)</code> which receives a pointer to a tree, turns that tree into a doubly-linked circular list and returns a pointer to the list's head (leftmost) node:

<pre><code>recLink( n={Node: left, elt, right}) = // pattern match tree to a full node
 rt := recLink( right); // already
 lt := recLink( left); // have it
 n.right := rt; n.left := lt.left; // middle node
 lt.left.right := n; rt.left.right := lt; // right edges
 lt.left := rt.left; rt.left := n; 
 return lt;
</code></pre>

Finish up with the edge cases (empty child branches etc.). :)

I faced an interesting problem called as the Great Tree-List Problem. The Problem is as follows :

In the ordered binary tree, each node contains a single data element and "small" and "large" pointers to sub-trees .All the nodes in the "small" sub-tree are less than or equal to the data in the parent node. All the nodes in the "large" sub-tree are greater than the parent node. And a circular doubly linked list consist of previous and next pointers.

The problem is to take an ordered binary tree and rearrange the internal pointers to make a circular doubly linked list out of it. The "small" pointer should play the role of "previous" and the "large" pointer should play the role of "next". The list should be arranged so that the nodes are in increasing order. I have to write a recursive function &amp; Return the head pointer to the new list.

The operation should be done in O(n) time.

I understand that recursion will go down the tree, but how to recursively change the small and large sub-trees into lists, also i have to append those lists together with the parent node.

How should i approach the problem?.. I just need a direction to solve the problem!.

The Great Tree list recursion program

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我遇到了一个有趣的问题叫做“伟大的树列表问题”。问题如下：在有序二叉树中，每个节点包含一个数据元素，以及指向子树的“小”和“大”指针.All“小”子树中的节点小于或等于父节点中的数据。“大”子树中的所有节点都大于父节点。循环双链接列表由前一个和下一个指针组成。问题是取一棵有序的二叉树，并重新排列内部指针，从而形成一个循...

问大树列表递归程序
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问大树列表递归程序EN