转载请联系大神程序员k公众号。前言众所周知，包含父节点引用和其中一个节点的二叉树是已知的。如何在这个节点的中序遍历序列中找到下一个节点呢？本文将与大家分享该问题的解决方案和实现代码。欢迎有兴趣的开发者阅读本文。问题分析如前言所述，我们已知的条件如下：二叉树中要查找的节点包含父节点的引用我们要解决的问题：找出中序遍历序列中的下一个节点接下来我们用一个例子来推导下一个节点的规则，我们先画一个二叉搜索树，如下图：8/\613/\/\37915比如我们要找的是6的下一个节点，根据中序遍历的规则我们可以知道7的下一个节点是78的下一个节点是93的下一个节点是67的下一个节点是8通过上面的例子，我们可以分析如下信息：待查找节点有右子树，则它下一个节点是其右子树中最左边的子节点待查找节点在右子树中不存在：当前节点属于左父节点的子节点，那么它的下一个节点就是父节点本身当前节点所属到父节点节点的右子节点，那么就需要沿着父节点的指针向上遍历，直到找到一个节点是其父节点的左子节点。可以理解。在向二叉树中插入一个节点时，保存其父节点的引用，调用二叉树的查找节点方法，找到要查找的节点的信息。判断找到的节点是否有右子树。如果存在，遍历它的左子树到叶节点。它的回报。如果不存在，则遍历其父节点到根节点，直到找到与其父节点的左子节点相等的节点，并返回。实现代码接下来，我们将上面的思路转化为代码。本文代码中使用的二叉树的实现可以参考我的另一篇文章：TypeScript实现二叉搜索树来搜索要查找的节点。我们需要找到要查找的节点二叉树中的节点信息才能继续执行后面的步骤。搜索节点代码如下：root=undefined;}//搜索特定值search(key:T):boolean|Node{returnthis.searchNode(>this.root,key);}//搜索节点privatesearchNode(node:Node,key:T):boolean|Node{if(node==null){returnfalse;}if(this.compareFn(key,node.key)===Compare.LESS_THAN){//要查找的key在节点左侧returnthis.searchNode(>node.left,key);}elseif(this.compareFn(key,node.key)===Compare.BIGGER_THAN){//要搜索的key在节点右侧returnthis.searchNode(>node.right,key);}else{//节点有找到returnnode;}}}保存父节点这里引用的二叉树和我们实现的二叉树略有不同。插入节点时，需要保存父节点的引用。实现代码如下：exportdefaultclassBinarySearchTree{//插入方法insert(key:T):void{if(this.root==null){//如如果根节点不存在，直接新建节点this.root=newNode(key);}else{//在根节点中找到合适的位置插入子节点this.insertNode(this.root,key);}}//节点插入protectedinsertNode(node:Node,key:T):void{//新节点的key小于当前节点的key，则在左边插入新节点当前节点//新节点的key大于当前节点的key，将新节点插入到当前节点的右边if(this.compareFn(key,node.key)===Compare.LESS_THAN){if(node.left==null){//当前节点的左子树为null直接插入node.left=newNode(key,node);}else{//从当前节点向下递归（左子树),找到null位置插入this.insertNode(node.left,key);}}else{if(node.right==null){//当前节点右子树为null直接插入node.right=newNode(key,node);}else{//从当前节点开始向下递归（右子树）,找到null位置插入this.insertNode(node.right,key);}}}}/***二叉树辅助类：用于存放二叉树的每个节点*/exportclassNode{publicleft:Node|undefined;publicright:Node|undefined;publicparent:Node|undefined;constructor(publickey:K,parent?:Node){this.left=undefined;this.right=未定义；console.log(key,"parentof"parent",parent?.key);this.parent=parent;}toString():string{return`${this.key}`;}}我们来测试一下上面的代码，验证父节点引用是否成功：consttree=newBinarySearchTree();tree。插入（8）；树.插入（6）；树.插入（3）；树.插入（7）；树.插入（13）；树.插入（9）；树.插入（15）；节点引用这个问题折腾了很久，一直没有意识到。我终于问了我的朋友_Dreams😁求助。找到下一个节点接下来，我们就可以根据节点的规则来实现这个算法了。实现代码如下：exportclassTreeOperate{/***查找二叉树的下一个节点*规则：*1。输入一个包含父节点的节点引用的二叉树和其中一个节点*2。找到这个节点的中序遍历序列的下一个节点**例如：*8*/\*613*/\/\*37915**6下一个节点是7，8的下一个节点是9**通过分析，我们可以得到以下信息：*1。如果一个节点有右子树，那么它的下一个节点是它右子树中最左边的子节点*2。如果一个节点没有右子树：*(1)。当前节点属于父节点的左子节点，那么它的下一个节点就是它的父节点本身*(2)。当前节点属于父节点的右子节点，沿着父节点的指针向上遍历，直到找到一个节点是其父节点的左子节点**/findBinaryTreeNextNode(tree:BinarySearchTree,node:number):null|Node{//SearchNodeconstresult:Node|boolean=tree.search(node);if(result==null)throw"节点不存在";letcurrentNode=resultasNode;//右子树存在if(currentNode.right){currentNode=currentNode.right;//获取右子树的最左子节点while(currentNode.left){currentNode=currentNode.left;}returncurrentNode;}//右子树不存在while(currentNode.parent){//当前节点等于其父节点的左子节点，则条件成立if(currentNode===currentNode.parent.left){returncurrentNode.parent;}//条件不成立，继续获取其父节点举个例子：//构建一个二叉搜索树consttree=newBinarySearchTree();tree.insert(8);tree.insert(6);tree.insert(3);tree.insert(7);tree.insert(13);tree.insert(9);tree.insert(15);//寻找下一个节点constnextNode=treeOperate.findBinaryTreeNextNode(tree,7);console.log("7的下一个节点",nextNode.toString());代码地址文中完整代码如下：TreeOperate.tsBinarySearchTree.ts
