[Typescript学习]二叉树的Typescript实现

痛定思痛。 2022-02-28 11:56 257阅读 0赞

# \[typescript学习\]二叉树的Typescript实现 #

### 目录 ###

*  \[typescript学习\]二叉树的Typescript实现
 *   *  前言
     *  二叉树节点类
     *   *  二叉树类
     *  构建一个二叉树
     *  测试
     *  参考

## 前言 ##

> 为了做个rpg小游戏，学习了`typescript`。人物到NPC移动打算用A\*寻路算法。学习算法的时候，顺便复习了一下数据结构。

要实现的二叉树：  
![要实现的二叉树][20190325181745675.png]

## 二叉树节点类 ##

class BiNode { 
    	data:any //节点内容
    	key:number //key值
    	isVisted:boolean //是否访问过
    	leftChild:BiNode //左孩子
    	rightChild:BiNode // 右孩子
    	constructor(key:number,data:any) { 
    		this.key = key;
    		this.data = data;
    	}
    };

### 二叉树类 ###

class BiTree { 
    	root:BiNode;
    
    	constructor(key:number, data:any) { 
    		this.root = new BiNode(key,data)
    	}
      //获取二叉树节点个数
    	private _size(subTree:BiNode):number{ 
    		if(subTree == null){ 
    			return 0;
    		}else{ 
    			return 1 + this._size(subTree.leftChild) + this._size(subTree.rightChild);
    		}
    	}
      public size():number{ 
    		return this._size(this.root)
    	}
    	//获取二叉树层级数
    	private _height(subTree:BiNode):number { 
    		if(subTree == null){ 
    			return 0;
    		}else{                    
    			let i = this._height(subTree.leftChild);
    			let j = this._height(subTree.rightChild);
    			return (i < j)?(j + 1):(i + 1);
    		}
    	}
    	public  height():number{ 
    		return this._height(this.root);
    	}
    
    	public visted(node:BiNode){ 
    		node.isVisted = true;
    	}
    	// 二叉树先序遍历
    	private _preOrder(node:BiNode):string{ 
    		if(node != null){ 
    			let str = '';
    			this.visted(node);
    			str += node.data;
    			str += this._preOrder(node.leftChild);
    			str += this._preOrder(node.rightChild);
    			return str;
    		}else{ 
    			return '';
    		}
    	}
    
    	public preOrder():string{ 
    		return this._preOrder(this.root);
    	}
    
    	//二叉树中序遍历
    	private _inOrder(node:BiNode):string{ 
    		if(node != null){ 
    			let str = '';
    			this.visted(node);
    			str += this._inOrder(node.leftChild);
    			str += node.data;
    			str += this._inOrder(node.rightChild);
    			return str;
    		}else{ 
    			return '';
    		}
    	}
    	public inOrder():string{ 
    		return this._inOrder(this.root);
    	}
    	//二叉树后序遍历
    	private _postOrder(node:BiNode):string{ 
    		if(node != null){ 
    			let str = '';
    			this.visted(node);
    			str += this._postOrder(node.leftChild);
    			str += this._postOrder(node.rightChild);
    			str += node.data;
    			return str;
    		}else{ 
    			return '';
    		}
    	}
    	public postOrder():string{ 
    		return this._postOrder(this.root);
    	}
    };

## 构建一个二叉树 ##

/* * A * B C * D E F */
    function createBiTree (root:BiNode){ 
    	let arr = ['B','C','D','E','F'];
    	let nodeArr = new Array<BiNode>();
    	arr.forEach((value,index) =>{ 
    		let node = new BiNode(index + 2, value);
    		nodeArr.push(node);
    	})
    	root.leftChild = nodeArr[0];
    	root.rightChild = nodeArr[1];
    	nodeArr[0].leftChild = nodeArr[2];
    	nodeArr[0].rightChild = nodeArr[3];
    	nodeArr[1].leftChild = nodeArr[4];
    	nodeArr[1].rightChild = nodeArr[5];
    }

## 测试 ##

let tree = new BiTree(1,'[A]');
    createBiTree(tree.root);
    
    console.log('size:',tree.size());
    console.log('height:',tree.height());
    console.log('先序遍历:',tree.preOrder());
    console.log('中序遍历:',tree.inOrder());
    console.log('后序遍历:',tree.postOrder());

输出：

size: 6
    height: 3
    先序遍历: [A]BDECF
    中序遍历: DBE[A]FC
    后序遍历: DEBFC[A]

## 参考 ##

1.  [【数据结构】二叉树的原理及实现学习总结][Link 1]
2.  [TypeScript Handbook（中文版）][TypeScript Handbook]

[20190325181745675.png]: /images/20220228/214e33404f744165abd8bc06d1ff7665.png
[Link 1]: https://blog.csdn.net/jianyuerensheng/article/details/51240068
[TypeScript Handbook]: https://zhongsp.gitbooks.io/typescript-handbook/content/doc/handbook/Generics.html