常州市城市建设局网站,二手网站模板,网站开发必须要做前端吗,公司办公网络建设方案考察点
树的遍历#xff0c;双向链表知识点
题目
分析 题目要求把一颗二叉搜索树转换成排序的双向链表#xff0c;二叉搜索树和双向链表一样都有2个指针#xff0c;唯一的区别就是对于树来说一个结点具有左子树右子树#xff0c;对于双向链表来说是直接前驱和直接后驱。…考察点
树的遍历双向链表知识点
题目
分析 题目要求把一颗二叉搜索树转换成排序的双向链表二叉搜索树和双向链表一样都有2个指针唯一的区别就是对于树来说一个结点具有左子树右子树对于双向链表来说是直接前驱和直接后驱。应该很自然的想到中序遍历一颗二叉搜索树就是一个有序序列结合中序遍历的特性当我们遍历到一个结点的时候该结点的左子树部分一定遍历好了但是右子树部分还没有开始所以这个时候我们能修改的一定是这个结点的左子树指针该指针一定指向左子树中值最大的那个结点而这个值最大的结点的右子树指针一定指向当前这个结点
public class Node{int val;Node leftChild;Node rightChild;public Node(int data) {this.val data;this.leftChild null;this.rightChild null;}
}
import java.util.Deque;
import java.util.Iterator;public class BinaryTree {Node root;Node preNode;public BinaryTree() {this.root null;}public void insertTree(int val) {if (this.root null) {Node root new Node(val);this.root root;} else {insertChildTree(this.root,val);}}public void insertChildTree(Node node,int val) {if (node ! null val node.val) {if (node.leftChild null) {node.leftChild new Node(val);} else {insertChildTree(node.leftChild,val);}}if (node ! null val node.val) {if (node.rightChild null) {node.rightChild new Node(val);} else {insertChildTree(node.rightChild,val);}}}public Node getRoot() {return this.root;}public void convert(Node root) {if (root null) {return;}convert(root.leftChild);root.leftChild preNode;if (preNode ! null) {preNode.rightChild root;}preNode root;convert(root.rightChild);}public void print() {Node firstHead null;while(preNode ! null) {System.out.print(preNode.val );firstHead preNode;preNode preNode.leftChild;}System.out.println();while(firstHead ! null) {System.out.print(firstHead.val );firstHead firstHead.rightChild;}System.out.println();}
}
public class TwentySeven {public static void main(String[] args) {BinaryTree binaryTree new BinaryTree();binaryTree.insertTree(10);binaryTree.insertTree(6);binaryTree.insertTree(14);binaryTree.insertTree(4);binaryTree.insertTree(8);binaryTree.insertTree(12);binaryTree.insertTree(16);binaryTree.convert(binaryTree.getRoot());binaryTree.print();}
}
