第十章 树

自我测试

本篇文章的测试用例及调试方法见前言

图

树的相关术语

根节点: 位于树顶部的节点叫作根节点

内部节点: 至少有一个子节点的节点称为内部节点（7、5、9、15、13和20是内部节点）

外部节点(叶节点):没有子元素的节点称为外部节点或叶节点（3、6、8、10、12、14、18和25是叶节点）

子树:由节点和它的后代构成。例如，节点13、12和14构成了上图中树的一棵子树

深度:节点的深度取决于它的祖先节点的数量。比如，节点3有3个祖先节点（5、7和11），它的深度为3

高度:树的高度取决于所有节点深度的最大值。一棵树也可以被分解成层级。根节点在第0层，它的子节点在第1层，以此类推。上图中的树的高度为3（最大高度已在图中表示——第3层）

一个节点可以有祖先和后代。一个节点（除了根节点）的祖先包括父节点、祖父节点、曾祖父节点等。一个节点的后代包括子节点、孙子节点、曾孙节点等。例如，节点5的祖先有节点7和节点11，后代有节点3和节点6。

二叉树和二叉搜索树

二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。这些定义有助于我们写出更高效的向/从树中插入、查找和删除节点的算法。二叉树在计算机科学中的应用非常广泛。
二叉搜索树（BST）是二叉树的一种，但是它只允许你在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大（或者等于）的值。上图中就展现了一棵二叉搜索树。

图例

基础方法

insert(key): 向二叉搜索树插入一个新的键
search(key): 在树中搜索一个键.如果存在该节点,就返回true;不存在就返回false
inOrderTraverse():通过中序遍历的方式遍历所有节点
preOrderTraverse():通过先序遍历的方式遍历所有节点
postOrderTraverse():通过后序遍历的方式遍历所有的节点
min():返回树中最小的值/键
max():返回树中最大的值/键
remove(key):从树中移除某个键

基础了解

root:表示根节点,在链表中使用head

节点:这里的树节点会有三个属性
left:表示其左侧节点

​ key:存放当前节点数据

​ right: 表示其右侧节点

代码实现

enum Compare {     LESS_THAN = -1,     BIGGER_THAN = 1,     EQUALS = 0 }  class TreeNode<T> {     key: T;     left: TreeNode<T> | undefined;     right: TreeNode<T> | undefined;      constructor(key: T) {         this.key = key;         this.left = undefined;         this.right = undefined;     } }  function defaultCompareFn<T>(parent: TreeNode<T>, child: TreeNode<T>) {     if (parent === child) {         return Compare.EQUALS     }     return parent > child ? Compare.BIGGER_THAN : Compare.LESS_THAN; }  export class BinarySearchTree<T> {     root: TreeNode<T> | undefined;     compareFn: Function;     count: number;      constructor(compareFn: Function = defaultCompareFn) {         this.root = undefined;         this.count = 0;         this.compareFn = compareFn;     }      //向二叉搜索树插入一个新的键     insert(key: T) {         // 当root没有值的时候         if (this.root == null) {             this.root = new TreeNode<T>(key);         } else {             // 当root有值时,判断当前key比root大(right)还是小(left)             return this.insertTreeNode(this.root, key);         }     }      //节点插入     insertTreeNode(cNode: TreeNode<T>, key: T) {         // 新值小于node         if (this.compareFn(cNode.key, key) === Compare.BIGGER_THAN) {             // left节点为null             if (cNode.left == null) {                 cNode.left = new TreeNode<T>(key);             } else {                 //left节点不为null就继续在左节点插入                 this.insertTreeNode(cNode.left, key)             }         }         // 新值大于node  right节点为null         else {             if (cNode.right == null) {                 cNode.right = new TreeNode<T>(key);             } else {                 // 新值没有插入又没有跳过就是插入right                 this.insertTreeNode(cNode.right, key);             }         }      }      // 搜索节点值     search(key: T) {         this.searchTreeNode(this.root, key);     }      // 搜索某个节点     searchTreeNode(node: TreeNode<T> | null, key: T): Boolean {         //如果node没有值,则返回false,表示没有找到         if (node == null) {             return false;         }         switch (this.compareFn(node.key, key)) {             //父节点等于子节点             case Compare.EQUALS:                 return true;                 break;             // 父节点小于当前数据 所以要在right节点上找             case Compare.LESS_THAN:                 return this.searchTreeNode(node.right, key)                 break;             // 父节点大于当前数据 所以应该在左节点上找             default:                 return this.searchTreeNode(node.left, key)                 break;         }     }       //通过中序遍历的方式遍历所有节点     inOrderTraverse(callBack: Function) {         this.inOrderTraverseNode(this.root, callBack);     }      inOrderTraverseNode(node: TreeNode<T> | null, callBack: Function) {         if (node == null) {             return;         }         this.inOrderTraverseNode(node.left, callBack);         callBack(node.key);         this.inOrderTraverseNode(node.right, callBack);     }      //通过先序遍历的方式遍历所有节点     preOrderTraverse(callBack: Function) {         this.preOrderTraverseNode(this.root, callBack);     }      preOrderTraverseNode(node: TreeNode<T> | null, callBack: Function) {         if (node == null) {             return;         }         callBack(node.key);         this.inOrderTraverseNode(node.left, callBack);         this.inOrderTraverseNode(node.right, callBack);     }      //通过后序遍历的方式遍历所有的节点     postOrderTraverse(callBack: Function) {         this.postOrderTraverseNode(this.root, callBack);     }      postOrderTraverseNode(node: TreeNode<T> | null, callBack: Function) {         if (node == null) {             return;         }         this.inOrderTraverseNode(node.left, callBack);         this.inOrderTraverseNode(node.right, callBack);         callBack(node.key);     }      //返回树中最小的值/键     min(): TreeNode<T> {         if (this.root == null) {             return undefined;         }         if (this.root.left == null) {             return this.root;         }         return this.minNode(this.root);     }      minNode(node: TreeNode<T> | null): TreeNode<T> {         if (node) {             if (node.left == null) {                 return node;             } else {                 return this.minNode(node.left);             }         }         return undefined;     }      //返回树中最大的值/键     max(): TreeNode<T> {         if (this.root == null) {             return undefined;         }         if (this.root.right == null) {             return this.root;         }         return this.maxNode(this.root);     }      maxNode(node: TreeNode<T> | null): TreeNode<T> {         if (node) {             if (node.right == null) {                 return node;             } else {                 return this.maxNode(node.right);             }         } else {             return undefined;         }     }      getRoot() {         return this.root;     }      //移除一个节点     remove(key: T) {         this.root = this.removeNode(this.root, key);     }      removeNode(node: TreeNode<T>, key: T): TreeNode<T> {         //判断这个树上是否有节点         if (node == undefined) {             return undefined;         }         //树上是有节点的,这个时候就要判断当前节点是否与删除的元素相同         switch (this.compareFn(node.key, key)) {             //父节点等于子节点             case Compare.EQUALS:                 node = this.removeCurrentNode(node);                 return node;                 break;             // 父节点小于当前数据 所以要在right节点上找             case Compare.LESS_THAN:                 node.right = this.removeNode(node.right, key)                 return node                 break;             // 父节点大于当前数据 所以应该在左节点上找             default:                 node.left = this.removeNode(node.left, key)                 return node                 break;         }     }      removeCurrentNode(node: TreeNode<T>): TreeNode<T> {         //分成三种情况         //一:叶结点(没有左右子节点),那么我们直接将该节点赋值为undefined         if (node.left == null && node.right == null) {             node = undefined;             return node;         }         //二:只有一个左节点或一个右节点         //左节点不存在,将父节点的右节点指针指向移除节点的右节点         if (node.left == null) {             node = node.right;             return node;         } else if(node.right == null){             node = node.left;             return node;         }          //三:有两个节点的元素         const aux = this.minNode(node.right);         node.key = aux.key;         node.right = this.removeNode(node.right,aux.key);         return node;     } }  

辅助分析:

递归遍历部分图解分析(这里只分析了左半部分):

从下向上看"调用栈"

从下向上看"调用栈"

从上向下看"调用栈"

书中代码

export enum Compare {   LESS_THAN = -1,   BIGGER_THAN = 1,   EQUALS = 0 }  type ICompareFunction<T> = (a: T, b: T) => number; function defaultCompare<T>(a: T, b: T): number {   if (a === b) {     return Compare.EQUALS;   }   return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN; }  class Node<K> {   left: Node<K>;   right: Node<K>;    constructor(public key: K) {}    toString() {     return `${this.key}`;   } }  export default class BinarySearchTree<T> {   protected root: Node<T>;    constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {}    insert(key: T) {     // special case: first key     if (this.root == null) {       this.root = new Node(key);     } else {       this.insertNode(this.root, key);     }   }    protected insertNode(node: Node<T>, key: T) {     if (this.compareFn(key, node.key) === Compare.LESS_THAN) {       if (node.left == null) {         node.left = new Node(key);       } else {         this.insertNode(node.left, key);       }     } else if (node.right == null) {       node.right = new Node(key);     } else {       this.insertNode(node.right, key);     }   }    getRoot() {     return this.root;   }    search(key: T) {     return this.searchNode(this.root, key);   }    private searchNode(node: Node<T>, key: T): boolean {     if (node == null) {       return false;     }      if (this.compareFn(key, node.key) === Compare.LESS_THAN) {       return this.searchNode(node.left, key);     } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {       return this.searchNode(node.right, key);     }     // key is equal to node.item     return true;   }    inOrderTraverse(callback: Function) {     this.inOrderTraverseNode(this.root, callback);   }    private inOrderTraverseNode(node: Node<T>, callback: Function) {     if (node != null) {       this.inOrderTraverseNode(node.left, callback);       callback(node.key);       this.inOrderTraverseNode(node.right, callback);     }   }    preOrderTraverse(callback: Function) {     this.preOrderTraverseNode(this.root, callback);   }    private preOrderTraverseNode(node: Node<T>, callback: Function) {     if (node != null) {       callback(node.key);       this.preOrderTraverseNode(node.left, callback);       this.preOrderTraverseNode(node.right, callback);     }   }    postOrderTraverse(callback: Function) {     this.postOrderTraverseNode(this.root, callback);   }    private postOrderTraverseNode(node: Node<T>, callback: Function) {     if (node != null) {       this.postOrderTraverseNode(node.left, callback);       this.postOrderTraverseNode(node.right, callback);       callback(node.key);     }   }    min() {     return this.minNode(this.root);   }    protected minNode(node: Node<T>) {     let current = node;     while (current != null && current.left != null) {       current = current.left;     }     return current;   }    max() {     return this.maxNode(this.root);   }    protected maxNode(node: Node<T>) {     let current = node;     while (current != null && current.right != null) {       current = current.right;     }     return current;   }    remove(key: T) {     this.root = this.removeNode(this.root, key);   }    protected removeNode(node: Node<T>, key: T) {     if (node == null) {       return null;     }      if (this.compareFn(key, node.key) === Compare.LESS_THAN) {       node.left = this.removeNode(node.left, key);       return node;     } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {       node.right = this.removeNode(node.right, key);       return node;     } else {       // key is equal to node.item        // handle 3 special conditions       // 1 - a leaf node       // 2 - a node with only 1 child       // 3 - a node with 2 children        // case 1       if (node.left == null && node.right == null) {         node = null;         return node;       }        // case 2       if (node.left == null) {         node = node.right;         return node;       } else if (node.right == null) {         node = node.left;         return node;       }        // case 3       const aux = this.minNode(node.right);       node.key = aux.key;       node.right = this.removeNode(node.right, aux.key);       return node;     }   } }