You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@echarts.apache.org by GitBox <gi...@apache.org> on 2019/10/27 03:48:01 UTC
[GitHub] [incubator-echarts] leaon4 opened a new issue #11493: 树图用setOption更新数据时，发现图有残留BUG
leaon4 opened a new issue #11493: 树图用setOption更新数据时，发现图有残留BUG
URL: https://github.com/apache/incubator-echarts/issues/11493
用echarts画二叉树图，在实现AVL树插入的时候发现的BUG
// index.html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>Tree</title>
<style>
html,
body {
margin: 0;
padding: 0;
}
.btn-container {
position: absolute;
top: 0;
left: 0;
width: 100%;
text-align: center;
}
</style>
<script src="assets/echarts.js"></script>
</head>
<body>
<div id="mychart" style="height: 100vh"></div>
<div class="btn-container">
<button class="btn" onclick="gen.next()">run</button>
<button class="btn" onclick="refresh()">refresh</button>
</div>
<script src="tree.js"></script>
</body>
</html>
// tree.ts
const container = document.getElementById('mychart') as HTMLDivElement;
const myChart = geta('echarts').init(container);
function geta(str: any): any {
return window![str];
}
const option: any = {
tooltip: {
trigger: 'item',
triggerOn: 'mousemove'
},
series: [
{
type: 'tree',
// data: [data],
data: [],
left: '2%',
right: '2%',
top: '8%',
bottom: '20%',
symbol: 'emptyCircle',
orient: 'vertical',
expandAndCollapse: true,
lineStyle: {
curveness: 0,
},
initialTreeDepth: -1,
// symbolSize:20,
label: {
normal: {
position: 'top',
align: 'middle',
fontSize: 19,
color: 'black'
}
},
leaves: {
label: {
normal: {
position: 'bottom',
align: 'middle'
}
}
},
animationDurationUpdate: 750
}
]
};
type ChartData = {
name: number | string;
children?: ChartData[];
};
type Item = {
num: number;
};
type TreeNode = {
item: Item;
left: TreeNode;
right: TreeNode;
height?: number;
} | null;
function itemCompare(item1: Item, item2: Item): number {
return item2.num - item1.num;
}
class BTree {
size: number;
root: TreeNode;
constructor() {
this.size = 0;
this.root = null;
}
protected createNode(item: Item): TreeNode {
return {
item,
left: null,
right: null
};
}
addItem(item: Item): void {
let newNode = this.createNode(item);
this.root = this._addItem(this.root, newNode);
this.size++;
}
protected _addItem(node: TreeNode, newNode: TreeNode): TreeNode {
if (!node) {
return newNode;
}
let dir: number = itemCompare(node.item, newNode!.item);
if (dir < 0) {
node.left = this._addItem(node.left, newNode);
} else if (dir > 0) {
node.right = this._addItem(node.right, newNode);
} else {
console.warn('same item');
this.size--;
}
return node;
}
private createChartData(node: TreeNode): ChartData {
if (!node) {
return { name: '' };
}
let data: ChartData = {
name: node.item.num,
children: []
}
data.children![0] = this.createChartData(node.left);
data.children![1] = this.createChartData(node.right);
if (data.children!.every(item => item.name === '')) {
data.children = [];
}
return data;
}
show(): void {
let data: ChartData = this.createChartData(this.root);
option.series[0].data = [data];
myChart.setOption(option);
}
}
class AVLTree extends BTree {
constructor() {
super();
}
addItem(item: Item): void {
let newNode = this.createNode(item);
newNode!.height = 0;
this.root = this._addItem(this.root, newNode);
this.size++;
}
protected createNode(item: Item): TreeNode {
let newNode = super.createNode(item);
newNode!.height = 0;
return newNode;
}
protected _addItem(node: TreeNode, newNode: TreeNode): TreeNode {
if (!node) {
return newNode;
}
let dir: number = itemCompare(node.item, newNode!.item);
if (dir < 0) {
node.left = this._addItem(node.left, newNode);
if (this.getNodeHeight(node.left) - this.getNodeHeight(node.right) == 2) {
if (itemCompare(node.left!.item, newNode!.item) < 0) {
console.log('left single rotation');
return this.singleRotate(node, -1);
}
console.log('left double rotation');
return this.doubleRotate(node, -1);
}
} else if (dir > 0) {
node.right = this._addItem(node.right, newNode);
if (this.getNodeHeight(node.left) - this.getNodeHeight(node.right) == -2) {
if (itemCompare(node.right!.item, newNode!.item) < 0) {
console.log('right double rotation')
return this.doubleRotate(node, 1);
}
console.log('right single rotation');
return this.singleRotate(node, 1);
}
} else {
console.warn('same item');
this.size--;
}
node.height = Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) + 1;
return node;
}
private getNodeHeight(node: TreeNode): number {
if (!node) {
return -1;
}
return node.height as number;
}
private singleRotate(parentNode: TreeNode, dir: number): TreeNode {
let childNode: TreeNode;
if (dir < 0) {
childNode = parentNode!.left;
parentNode!.left = childNode!.right;
childNode!.right = parentNode;
} else {
childNode = parentNode!.right;
parentNode!.right = childNode!.left;
childNode!.left = parentNode;
}
parentNode!.height = Math.max(this.getNodeHeight(parentNode!.left), this.getNodeHeight(parentNode!.right)) + 1;
childNode!.height = Math.max(this.getNodeHeight(childNode!.left), this.getNodeHeight(childNode!.right)) + 1;
return childNode;
}
private doubleRotate(parentNode: TreeNode, dir: number): TreeNode {
if (dir < 0) {
parentNode!.left = this.singleRotate(parentNode!.left, 1);
} else {
parentNode!.right = this.singleRotate(parentNode!.right, -1);
}
return this.singleRotate(parentNode, dir);
}
}
// 以下为驱动代码
function addItem(num: number) {
tree.addItem({ num });
tree.show();
}
const tree = new AVLTree();
function* main() {
let testcase = [3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9];
// let testcase = [1, 10, 2, 9, 3, 8, 4, 7, 5, 6];
for (let num of testcase) {
addItem(num);
yield;
}
}
let gen = main();
function refresh() {
myChart.clear();
myChart.setOption(option);
}
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@echarts.apache.org
For additional commands, e-mail: commits-help@echarts.apache.org