树 Tree

在这里插入图片描述

根 Root：树顶部的顶点，记为r。
路径 Path：树中的路径是连接一个顶点到另一个顶点的顶点和边的序列，顶点y到顶点v的路径记为 $_y \ \underrightarrow{*}_T\ {_v}$ 。
深度 Depth：一个顶点v的深是路径 $_r \ \underrightarrow{*}_T\ {_v}$ 上边的数目。
层次 Level：从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推。
节点的度：节点子树个数。
父亲 Parent：如果在树上存在一个边 $(p, v)$ ，则顶点p是顶点v的父亲。
孩子 Child：如果在树上存在一个边 $(p, v)$ ，则顶点v是顶点p的父亲。
兄弟 Sibling：有相同父亲的顶点。
祖先 Ancestor：如果a在路径 $_a \ \underrightarrow{*}_T\ {_v}$ (包括v)上，则顶点a是v的祖先。
后代 Descendant：顶点a是顶点v的祖先，则v是a的后代，包括顶点自己。
真祖先 Proper Ancestor：和祖先的一样，但不包括自己，真祖先a到顶点v的路径记为： $_a \ \underrightarrow{+}_T\ {_v}$ 。
真后代 Proper descendant：和后代一样，但不包括自己。
子树 Subtree：顶点v是树中的一个顶点，有v和其后代组成的的树为T的子树，顶点v是该子树的根。
单体 Singlenton：只有一个顶点的树。
森林 Forest：森林就是一系列的树，这些树不互相连接。
叶结点 Leaf ：度为0的结点称为叶结点，也可以叫做终端结点；

二叉树 Binary Tree

二叉树：所有节点的度不超过2的树。
满二叉树：一种二叉树，叶子节点都在最下面一层，并且除了叶子节点外每个节点度都为2。
完全二叉树：一种二叉树，叶子节点只能位于最下面一层或次最下面一层，并且最下面一层都位于最左边的若干子树。
在这里插入图片描述
二叉树最常使用的存储是采用链式存储：

typedef int ElemType;
class TreeNode{
private:ElemType val;TreeNode* lchild;TreeNode* rchild;
public:TreeNode(ElemType x) : val(x), child(nullptr), rchild(nullptr) {}
}

在这里插入图片描述

先序遍历 Preorder Traversal

先序遍历：先访问根节点，然后访问左子树，最后访问右子树。ABDECFG。

递归版本

void PreOrder(TreeNode* root){if(root == nullptr) return;visit(root);PreOrder(root->lchild);PreOrder(root->rchild);
}

非递归版本

借助栈来完成。

沿着左孩子访问，并依次入栈，直到左孩子为空。
栈顶元素出栈，若其右孩子为空，继续步骤2，否则对右孩子执行步骤1。

void PreOrder1(TreeNode* root){if(root == nullptr) return;Stack<TreeNode*> s;TreeNode* p = root;while(p != nullptr || !s.empty()) {if (p != nullptr) {visit(p);s.push(p);p = p->lchild;} else {p = s.pop();p = p->rchild;}}
}

中序遍历 Inoreder Traversal

中序遍历：先访问左子树，然后访问根节点，最后访问右子树。DBEAFCG。

递归版本

void InOrder(TreeNode* root){if(root == nullptr) return;PreOrder(root->lchild);visit(root);PreOrder(root->rchild);
}

非递归版本

算法和先序遍历类似，只是访问根节点时机改变了。

沿着左孩子，依次入栈，直到左孩子为空。
栈顶元素出栈并访问，若其右孩子为空，继续步骤2，否则对右孩子执行步骤1。

void InOrder1(TreeNode* root){if(root == nullptr) return;Stack<TreeNode*> s;TreeNode* p = root;while(p != nullptr || !s.empty()) {if (p != nullptr) {s.push(p);p = p->lchild;} else {p = s.pop();visit(p);p = p->rchild;}}
}

后序遍历 Postorder Traversal

后序遍历：先访问左子树，然后访问右子树，最后访问根节点。DEBFGCA。

递归版本

void PostOrder(TreeNode* root){if(root == nullptr) return;PreOrder(root->lchild);PreOrder(root->rchild);visit(root);
}

非递归版本

也借助栈：

沿着左孩子，将其依次入栈，直到左孩子为空。
读取栈顶元素（但不出栈），若其有孩子为空且未被访问过，对右孩子执行步骤1，否则，栈定元素出栈并访问。

void PostOrder1(TreeNode* root){if(root == nullptr) return;TreeNode* p = root;TreeNode* visited = nullptr;Stack<TreeNode*> s;while (p != nullptr || !s.empty()) {if (p != nullptr) {s.push(p);p = p->lchild;} else {p = s.top();if (p->rchild != nullptr && p->rchild != visited) {s.push(p->rchild);p = p->rchild->lchild;} else {p = s.pop();visit(p);visited = p;p = nullptr;  }}}
}

层次遍历 Level Traversal

层次遍历：按照层，上一层遍历完，再遍历下一层，每一层先访问左边节点，再访问右边节点。ABCDEFG。

需要借助队列，先将根节点入队，然后出队并访问。若它有左孩子则左孩子根节点入队，若它有右孩子则右孩子根节点入队。
接着出队并访问，继续上述步骤，直到队列为空。

void LevelOrder1(TreeNode* root){if(root == nullptr) return;queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode* p = q.front();q.pop();visite(p);if (p->lchild != nullptr) {q.push(p->lchild);}if (p->rchild != nullptr) {q.push(p->rchild);}}
}