###### 友谊地久天长

2019-12-07 14:14 阅读 218

# 数据结构求问：想用层次遍历序列构造二叉树，但是下面的代码运行之后只能构造一层，具体应该怎么改？

5

• 点赞
• 写回答
• 关注问题
• 收藏
• 复制链接分享

#### 1条回答默认 最新

• 会灰翔的灰机 2019-12-09 17:06

可以参考这个AVL树的实现，遍历序列insert node即可

``````public class AvlNode<T> {

private T data;
private Integer height;
private AvlNode<T> left;
private AvlNode<T> right;
private AvlNode<T> parent;

public AvlNode(T data) {
this(data, null, null);
}

public AvlNode(T data, AvlNode left, AvlNode right) {
this.height = 0;
this.data = data;
this.left = left;
this.right = right;
}

public T getData() {
return data;
}

public void setData(T data) {
this.data = data;
}

public Integer getHeight() {
return height;
}

public void setHeight(Integer height) {
this.height = height;
}

public AvlNode<T> getLeft() {
return left;
}

public void setLeft(AvlNode<T> left) {
this.left = left;
}

public AvlNode<T> getRight() {
return right;
}

public void setRight(AvlNode<T> right) {
this.right = right;
}

public AvlNode<T> getParent() {
return parent;
}

public void setParent(AvlNode<T> parent) {
this.parent = parent;
}

@Override
public String toString() {
return "AvlNode{" + "height=" + height + ", data=" + data + '}';
}
}
import lombok.Data;
@Data
public class SimpleAvlTree {

public static AvlNode<Integer> insert(Integer data, AvlNode<Integer> node) {
if (node == null) {
return new AvlNode<Integer>(data);
}
int compareResult = compare(data, node.getData());
if (compareResult < 0) {
node.setLeft(insert(data, node.getLeft()));
if (height(node.getLeft()) - height(node.getRight()) == 2 ) {
if (compare(data, node.getLeft().getData()) < 0) {
node = rotateWithLeftChild(node);
} else {
node = doubleWithLeftChild(node);
}
}
} else if (compareResult > 0) {
node.setRight(insert(data, node.getRight()));
if (height(node.getRight()) - height(node.getLeft()) == 2 ) {
if (compare(data, node.getRight().getData()) > 0) {
node = rotateWithRightChild(node);
} else {
node = doubleWithRightChild(node);
}
}
}
node.setHeight(Math.max(height(node.getLeft()), height(node.getRight())) + 1);
return node;
}

/**
* 根据左子节点右旋
* @param k2 :
* @return org.gallant.tree.avl.AvlNode<java.lang.Integer> :
*/
public static AvlNode<Integer> rotateWithLeftChild(AvlNode<Integer> k2){
AvlNode<Integer> k1 = k2.getLeft();
k2.setLeft(k1.getRight());
k1.setRight(k2);
k2.setHeight(Math.max(height(k2.getLeft()), height(k2.getRight())) + 1);
k1.setHeight(Math.max(height(k1.getLeft()), k2.getHeight()) + 1);
return k1;
}
/**
* 根据右子节点左旋
* @param k2 :
* @return org.gallant.tree.avl.AvlNode<java.lang.Integer> :
*/
public static AvlNode<Integer> rotateWithRightChild(AvlNode<Integer> k2){
AvlNode<Integer> k1 = k2.getRight();
k2.setRight(k1.getLeft());
k1.setLeft(k2);
k2.setHeight(Math.max(height(k2.getRight()), height(k2.getLeft())) + 1);
k1.setHeight(Math.max(height(k1.getRight()), k2.getHeight()) + 1);
return k1;
}
/**
* 先左旋再右旋
* @param k3 :
* @return org.gallant.tree.avl.AvlNode<java.lang.Integer> :
*/
public static AvlNode<Integer> doubleWithLeftChild(AvlNode<Integer> k3){
k3 = rotateWithRightChild(k3.getLeft());
return rotateWithLeftChild(k3);
}
/**
* 先右旋再左旋
* @param k3 :
* @return org.gallant.tree.avl.AvlNode<java.lang.Integer> :
*/
public static AvlNode<Integer> doubleWithRightChild(AvlNode<Integer> k3){
k3 = rotateWithLeftChild(k3.getRight());
return rotateWithRightChild(k3);
}

/**
* 比较两个节点的大小
* @param data1 :
* @param data2 :
* @return java.lang.Integer :
*/
public static Integer compare(Integer data1, Integer data2) {
return data1 - data2;
}
/**
* 获取节点高度，如果为空则为-1
* @param node :
* @return java.lang.Integer :
*/
public static Integer height(AvlNode<Integer> node) {
return node == null ? -1 : node.getHeight();
}

public static AvlNode<Integer> test(){
AvlNode<Integer> node = SimpleAvlTree.insert(20, null);
node = SimpleAvlTree.insert(25, node);
node = SimpleAvlTree.insert(15, node);
node = SimpleAvlTree.insert(18, node);
node = SimpleAvlTree.insert(10, node);
node = SimpleAvlTree.insert(13, node);
return node;
}

public static AvlNode<Integer> test2(){
AvlNode<Integer> node = SimpleAvlTree.insert(20, null);
node = SimpleAvlTree.insert(25, node);
node = SimpleAvlTree.insert(15, node);
node = SimpleAvlTree.insert(18, node);
node = SimpleAvlTree.insert(16, node);
return node;
}

public static AvlNode<Integer> test3(){
AvlNode<Integer> node = SimpleAvlTree.insert(20, null);
node = SimpleAvlTree.insert(25, node);
node = SimpleAvlTree.insert(30, node);
return node;
}

public static void main(String[] args) {
AvlNode<Integer> node = test();
System.out.println(node);
fillParent(node);
print(node, 0, 25);
}

/**
* 打印目标节点的路径
* @param node :
* @param summary :
* @param aim :
*/
public static void print(AvlNode<Integer> node, Integer summary, Integer aim){
if (node == null) {
return;
}
summary += node.getData();
if (summary.equals(aim)) {
System.out.println(summary);
printPath(node);
return;
}
print(node.getLeft(), summary, aim);
print(node.getRight(), summary, aim);
}

/**
* 打印当前节点至root节点路径
* @param node :
*/
public static void printPath(AvlNode<Integer> node) {
if (node.getParent() != null) {
printPath(node.getParent());
}
System.out.print(node.getData()+",");
}

/**
* 填充指向父的指针
* @param node :
*/
public static void fillParent(AvlNode<Integer> node) {
if (node == null) {
return;
}
if (node.getLeft() != null) {
node.getLeft().setParent(node);
}
if (node.getRight() != null) {
node.getRight().setParent(node);
}
fillParent(node.getLeft());
fillParent(node.getRight());
}
}
``````
点赞 评论 复制链接分享