线性
- 表 1-1 $$ 插入O(N) $$
非线性
- 树 1-n
  $$ 插入O(logN) $$
- 图 n-n
结构
#

一个树的基本组成是
- Root 入度为0
- Nodes 有限个元素集
  - node
    - degree 于结点相连的边
    - ~~indegree 入~~
    - ~~out~~degree （出）度
- Edges, branches

其它术语
#

Leaf 度=0
Internal node 无叶之node
Parent
Child
Siblings 同双亲之结点们
Path

Ancestors 前辈
Descendent 后代
Depth 深度（of 某个结点）从根到该结点的长度 k - 1
Level 层 同深度的一群结点处于同一层
Height 高度 深度最高者+1
Sub-tree 子树 根下面的连通结点们

树的描述
#

略（见上文）

括号式

Root (a b c(c1 c2 c3(c31 c32)) d)

二叉树
#

Def
#

~ 左子树右子树…

五种形态：

空树
只含根节点
右子树为空树
左子树为空树
左右子树均不为空树

已知一棵二叉树有三个结点，它可能……

R

l

l

R

l

r

R

r

r

R

r

l

R

l

r

满二叉树
#

对每一个结点，度要么为0，要么为2。

完全二叉树
#

对于一个高度为d的树：

所有层（除了d-1层）必须完全满
d-1层所有的结点左侧为满

性质
#

在二叉树的第i（i>=0）层上最多有$$2^i$$个结点
高度为k（k>=1）的二叉树上至多含有$$2^k-1$$个结点
- 至少k个
对于任何一个二叉树，若含有$$n_0$$个叶子，$$n_2$$个度为2的内部结点
- $$n_0$$=$$n_2$$+1
具有n个结点的完全二叉树，高度是$$log_2n + 1$$
- 对于一般二叉树，最小高度$$log_2n + 1$$，最高n
非空满二叉树叶子个数 = 内部结点数 + 1
一个非空二叉树中的空子树 = 结点数 + 1
- $$n_1+2n_0=n+1$$

Implemention
#

结点类
链式二叉树类

链
#

二叉结点结构 |left|data|right|

// Binary tree node abstract class
template <typename E> class BinNode {
public:
virtual ~BinNode() {} // Base destructor
// Return the node’s value
virtual E& element() = 0;
// Set the node’s value
virtual void setElement(const E&) = 0;
// Return the node’s left child
virtual BinNode* left() const = 0;
// Set the node’s left child
virtual void setLeft(BinNode*) = 0;
// Return the node’s right child
virtual BinNode* right() const = 0;
// Set the node’s right child
virtual void setRight(BinNode*) = 0;
// Return true if the node is a leaf, false otherwise
virtual bool isLeaf() = 0;
};

// Simple binary tree node implementation
template <typename Key, typename E>
class BSTNode : public BinNode<E> {
private:
Key k; // The node’s key
E it; // The node’s value
BSTNode* lc; // Pointer to left child
BSTNode* rc; // Pointer to right child
public:
// Two constructors -- with and without initial values
BSTNode() { lc = rc = NULL; }
BSTNode(Key K, E e, BSTNode* l =NULL, BSTNode* r =NULL)
{ k = K; it = e; lc = l; rc = r; }
~BSTNode() {} // Destructor
// Functions to set and return the value and key
E& element() { return it; }
void setElement(const E& e) { it = e; }
Key& key() { return k; }
void setKey(const Key& K) { k = K; }
// Functions to set and return the children
inline BSTNode* left() const { return lc; }
void setLeft(BinNode<E>* b) { lc = (BSTNode*)b; }
inline BSTNode* right() const { return rc; }
void setRight(BinNode<E>* b) { rc = (BSTNode*)b; }
// Return true if it is a leaf, false otherwise
bool isLeaf() { return (lc == NULL) && (rc == NULL); }
};

实际应用中不怎么用父指针

BT:

$$n_0 ？=n/2$$

可变结构

叶子 data；内部结点 ldata|data|rdata|

// Node implementation with simple inheritance
class VarBinNode { // Node abstract base class
public:
virtual ˜VarBinNode() {}
virtual bool isLeaf() = 0; // Subclasses must implement
};

class LeafNode : public VarBinNode { // Leaf node
private:
Operand var; // Operand value
public:
LeafNode(const Operand& val) { var = val; } // Constructor
bool isLeaf() { return true; } // Version for LeafNode
Operand value() { return var; } // Return node value
};

class IntlNode : public VarBinNode { // Internal node
private:
VarBinNode* left; // Left child
VarBinNode* right; // Right child
Operator opx; // Operator value
public:
IntlNode(const Operator& op, VarBinNode* l, VarBinNode* r)
{ opx = op; left = l; right = r; } // Constructor
bool isLeaf() { return false; } // Version for IntlNode
VarBinNode* leftchild() { return left; } // Left child
VarBinNode* rightchild() { return right; } // Right child
Operator value() { return opx; } // Value
};

// Node implementation with the composite design pattern
class VarBinNode { // Node abstract base class
public:
virtual ˜VarBinNode() {} // Generic destructor
virtual bool isLeaf() = 0;
virtual void traverse() = 0;
};
class LeafNode : public VarBinNode { // Leaf node
private:
Operand var; // Operand value
public:
LeafNode(const Operand& val) { var = val; } // Constructor
bool isLeaf() { return true; } // isLeaf for Leafnode
Operand value() { return var; } // Return node value
void traverse() { cout << "Leaf: " << value() << endl; }
};
class IntlNode : public VarBinNode { // Internal node
private:
VarBinNode* lc; // Left child
VarBinNode* rc; // Right child
Operator opx; // Operator value
public:
IntlNode(const Operator& op, VarBinNode* l, VarBinNode* r)
{ opx = op; lc = l; rc = r; } // Constructor
bool isLeaf() { return false; } // isLeaf for IntlNode
VarBinNode* left() { return lc; } // Left child
VarBinNode* right() { return rc; } // Right child
Operator value() { return opx; } // Value
void traverse() { // Traversal behavior for internal nodes
cout << "Internal: " << value() << endl;
if (left() != NULL) left()->traverse();
if (right() != NULL) right()->traverse();
}
};

二叉结点空间

nE + 2nP

2P/2P+E

P=E=2/3 空间占用率

可变ver

n/2 * 2P/(n/2 * E + N/2 * (E+2P))

P = E = 1/2 空间占用率

CBT 一维数组
#

完全二叉树only

按层存起

• Parent(r) = b(r − 1)/2c if r != 0.

• Left child(r) = 2r + 1 if 2r + 1 < n.

• Right child(r) = 2r + 2 if 2r + 2 < n.

• Left sibling(r) = r − 1 if r is even.

• Right sibling(r) = r + 1 if r is odd and r + 1 < n.

存储原则
#

能方便重构原始二叉树
1. 链式
2. 数组CBT
能翻遍找到各结点孩子
1. 链式
2. 数组CBT

遍历
#

深度优先 DFT

递归（栈）实现

前序 NLR

根 - 左 - 右

template <typename E>
void preorder(BinNode<E>* root) {
if (root == NULL) return; // Empty subtree, do nothing
visit(root); // Perform desired action 根
preorder(root->left());// 左
preorder(root->right());// 右
}

后序 LRN
- 左 - 右 - 根
- ```
递归调用 类似，换一下顺序
```
中序 LNR
- 左 - 根 - 右
- ```
类似 略
```

已知前序&中序可唯一恢复二叉树

已知后序&中序可唯一恢复二叉树

已知前序&后序不可唯一恢复二叉树

广度优先 BFT

通常使用队列实现

二叉搜索树
#

所有在左子树的元素都$$<$$根节点
所有在右子树的元素都$$\geq$$根节点
所有子树自身（递归地）仍然是二叉搜索树

遍历
#

前序
中序！对于二叉搜索树明显地可以得知，其遍历顺序就是元素递增顺序
后序

基本操作

search
insert
remove
deletemin
- 关于删除的基本操作
traversal/print
- in order

一个指针+一个整型变量就可以描述一棵搜索二叉树

*root 根节点
nodecount存放结点数

// Binary Search Tree implementation for the Dictionary ADT
template <typename Key, typename E>
class BST : public Dictionary<Key,E> {
private:
BSTNode<Key,E>* root; // Root of the BST
int nodecount; // Number of nodes in the BST
// Private "helper" functions
void clearhelp(BSTNode<Key, E>*);
BSTNode<Key,E>* inserthelp(BSTNode<Key, E>*,
const Key&, const E&);
BSTNode<Key,E>* deletemin(BSTNode<Key, E>*);
BSTNode<Key,E>* getmin(BSTNode<Key, E>*);
BSTNode<Key,E>* removehelp(BSTNode<Key, E>*, const Key&);
E findhelp(BSTNode<Key, E>*, const Key&) const;
void printhelp(BSTNode<Key, E>*, int) const;
public:
BST() { root = NULL; nodecount = 0; } // Constructor
~BST() { clearhelp(root); } // Destructor
void clear() // Reinitialize tree
{ clearhelp(root); root = NULL; nodecount = 0; }
// Insert a record into the tree.
// k Key value of the record.
// e The record to insert.
void insert(const Key& k, const E& e) {
root = inserthelp(root, k, e);
nodecount++;
}
// Remove a record from the tree.
// k Key value of record to remove.
// Return: The record removed, or NULL if there is none.
E remove(const Key& k) {
E temp = findhelp(root, k); // First find it
if (temp != NULL) {
root = removehelp(root, k);
nodecount--;
}
return temp;
}
// Remove and return the root node from the dictionary.
// Return: The record removed, null if tree is empty.
E removeAny() { // Delete min value
if (root != NULL) {
E temp = root->element();
root = removehelp(root, root->key());
nodecount--;
return temp;
}
else return NULL;
}
// Return Record with key value k, NULL if none exist.
// k: The key value to find. */
// Return some record matching "k".
// Return true if such exists, false otherwise. If
// multiple records match "k", return an arbitrary one.
E find(const Key& k) const { return findhelp(root, k); }
// Return the number of records in the dictionary.
int size() { return nodecount; }
void print() const { // Print the contents of the BST
if (root == NULL) cout << "The BST is empty.\n";
else printhelp(root, 0);
}
};

几个helper function：

find del

$$O(d)$$

template <typename Key, typename E>
E BST<Key, E>::findhelp(BSTNode<Key, E>* root,
const Key& k) const {
    if (root == NULL) return NULL; // Empty tree
    if (k < root->key())
    return findhelp(root->left(), k); // Check left
    else if (k > root->key())
    return findhelp(root->right(), k); // Check right
    else return root->element(); // Found it
}

template <typename Key, typename E>
BSTNode<Key, E>* BST<Key, E>::inserthelp(
BSTNode<Key, E>* root, const Key& k, const E& it) {
    if (root == NULL) // Empty tree: create node
    return new BSTNode<Key, E>(k, it, NULL, NULL);
    if (k < root->key())
    root->setLeft(inserthelp(root->left(), k, it));
    else root->setRight(inserthelp(root->right(), k, it));
    return root; // Return tree with node inserted
}

template <typename Key, typename E>
BSTNode<Key, E>* BST<Key, E>::
deletemin(BSTNode<Key, E>* rt) {
    if (rt->left() == NULL) // Found min
    return rt->right();
    else { // Continue left
    rt->setLeft(deletemin(rt->left()));
    return rt;
    }
}

template <typename Key, typename E>
BSTNode<Key, E>* BST<Key, E>::
getmin(BSTNode<Key, E>* rt) {
    if (rt->left() == NULL)
    return rt;
    else return getmin(rt->left());
}

// 重点 三种情况 需要处理原子树的剩下部分
// Remove a node with key value k
// Return: The tree with the node removed
template <typename Key, typename E>
BSTNode<Key, E>* BST<Key, E>::
removehelp(BSTNode<Key, E>* rt, const Key& k) {
    if (rt == NULL) return NULL; // k is not in tree
    else if (k < rt->key())
    rt->setLeft(removehelp(rt->left(), k));
    else if (k > rt->key())
    rt->setRight(removehelp(rt->right(), k));
    else { // Found: remove it
    BSTNode<Key, E>* temp = rt;
    if (rt->left() == NULL) { // Only a right child
    rt = rt->right(); // so point to right
    delete temp;
    }
    else if (rt->right() == NULL) { // Only a left child
    rt = rt->left(); // so point to left
    delete temp;
    }
    else { // Both children are non-empty
        // 用右子树最小值代替待删除结点
        // 因为定义左必须小于根
        // 删除该结点
    BSTNode<Key, E>* temp = getmin(rt->right());
    rt->setElement(temp->element());
    rt->setKey(temp->key());
    rt->setRight(deletemin(rt->right()));
    delete temp;
    }
    }
    return rt;
}

template <typename Key, typename E>
void BST<Key, E>::
clearhelp(BSTNode<Key, E>* root) {
    if (root == NULL) return;
    clearhelp(root->left());
    clearhelp(root->right());
    delete root;
}

template <typename Key, typename E>
void BST<Key, E>::
printhelp(BSTNode<Key, E>* root, int level) const {
    if (root == NULL) return; // Empty tree
    printhelp(root->left(), level+1); // Do left subtree
    for (int i=0; i<level; i++) // Indent to level
    cout << " ";
    cout << root->key() << "\n"; // Print node value
    printhelp(root->right(), level+1); // Do right subtree
}