前言
本文是題主準(zhǔn)備面試時(shí)記錄下的筆記整理而來(lái)，稍顯粗陋，還請(qǐng)各位擼友勿噴哈米罚！
Topic
-
目錄
-
目標(biāo)
- 熟練使用常用數(shù)據(jù)結(jié)構(gòu)的基本操作
- 加深對(duì)常用算法與技巧的理解
- 面試
-
參考
- 《程序員面試金典》
- 《劍指offer》
- Leetcode
- 《結(jié)構(gòu)之法 --July》
二叉樹(shù)篇
BTree ADT
-
構(gòu)建二叉樹(shù)
- TreeNode<T>* createBTree(const string &s, int &i, int method);
- 遞歸構(gòu)建
- 判斷傳入字符串參數(shù)是否為空
- 遇“#”返回NULL
- 遇其他字符髓窜，new一個(gè)二叉樹(shù)結(jié)點(diǎn)
a. data域是該字符
b. 左孩子遞歸調(diào)用該函數(shù)，所傳標(biāo)志變量i加1
c. 右孩子同b
- 根據(jù)先序遍歷序列構(gòu)建二叉樹(shù)（非遞歸）
- 判空
- 向左深搜構(gòu)造据某，并將結(jié)點(diǎn)入棧
- 重復(fù)執(zhí)行B直至最左葉子節(jié)點(diǎn)的左指針
- 逐一訪問(wèn)棧頂結(jié)點(diǎn)橡娄，向右深搜構(gòu)造
- 執(zhí)行D時(shí)，檢測(cè)是否有左結(jié)點(diǎn)癣籽，有則執(zhí)行C
- 根據(jù)后序遍歷序列構(gòu)建二叉樹(shù)（非遞歸）
- 同先序類似挽唉，順序顛倒一下就可以了
-
銷毀二叉樹(shù)
- void delBTree(TreeNode<T>* &p);
-
先序遍歷
- void PreOrder(TreeNode<T>* p, int method);
- 迭代策略一：
- 向左深搜直至BTree的最左葉子節(jié)點(diǎn)的l_child指針
- 搜的同時(shí)，訪問(wèn)每一結(jié)點(diǎn)筷狼，并將結(jié)點(diǎn)入棧
- 逐一獲取棧中結(jié)點(diǎn)的右孩子瓶籽，重復(fù)A，B
- 每獲取一個(gè)棧中結(jié)點(diǎn)埂材，就將該結(jié)點(diǎn)彈出塑顺，直至棧空
- 迭代策略二：
- 將根節(jié)點(diǎn)入棧
- 訪問(wèn)棧頂結(jié)點(diǎn)楞遏，并彈出棧頂結(jié)點(diǎn)
- 將該棧頂結(jié)點(diǎn)的右孩子入棧,如果有的話
- 將該棧頂結(jié)點(diǎn)的左孩子入棧,如果有的話
- 重復(fù)BCD,直至棽缦荆空
-
中序遍歷
- void InOrder(TreeNode<T>* p, int method);
- 迭代策略：
- 向左深搜直至BTree的最左葉子節(jié)點(diǎn)的l_child指針
- 搜的同時(shí)，將結(jié)點(diǎn)入棧
- 逐一訪問(wèn)棧頂結(jié)點(diǎn)寡喝，并將棧頂結(jié)點(diǎn)的右孩子入棧
- 重復(fù)ABC糙俗，直至棧空
-
后序遍歷
void PostOrder(TreeNode<T>* p, int method);
-
策略一：
- 向左深搜直至BTree的最左葉子節(jié)點(diǎn)的l_child指針
- 搜的同時(shí)预鬓，將結(jié)點(diǎn)入棧
- 向右深搜棧頂元素的右孩子巧骚，直至最右葉子節(jié)點(diǎn)，
- 每搜一個(gè)節(jié)點(diǎn)時(shí)格二，先重復(fù)AB
- 將棧中元素逐個(gè)彈出劈彪，并訪問(wèn)之
- 執(zhí)行D時(shí)，需注意將p指針置空
-
策略二：雙棧法
- 構(gòu)建兩個(gè)棧s1,s2
- 將根節(jié)點(diǎn)入棧s1
- 彈出s1的棧頂元素顶猜，并將該元素入棧s2
- 將該元素的左孩子入棧沧奴，如果有的話
- 將該元素的右孩子入棧，如果有的話
- 重復(fù)CDE,直至棧s1空
- 通過(guò)棧頂指針逐一遍歷棧s2的元素
-
層次遍歷
- void LayerOrder(TreeNode<T> *p);
-
查找值為et_value的二叉樹(shù)結(jié)點(diǎn)
- TreeNode<T>* findNode(TreeNode<T> *p, T et_value);
-
獲得二叉樹(shù)的深度
- int getBTDepth(TreeNode<T> *p);
BST ADT
- 構(gòu)建二叉排序樹(shù)
- TreeNode<T>* createBST(int v[], int start, int end);
- 插入新結(jié)點(diǎn)
- void insertNode(T &et_value, TreeNode<T>* &p);
- 刪除指定結(jié)點(diǎn)
- void removeNode(T et_value, TreeNode<T>* &p);
- 查找最大值
- TreeNode<T>* findMax(TreeNode<T> *p);
- 查找最小值
- TreeNode<T>* findMin(TreeNode<T> *p);
- 查找二叉樹(shù)是否包含指定值的結(jié)點(diǎn)
- bool contains(T et_value, TreeNode<T> *p);
代碼示例：
/*******************************************************************************
@ Title: 實(shí)現(xiàn)二叉樹(shù)基本操作
@ Description:
1.C++實(shí)現(xiàn)二叉樹(shù)模板類（遞歸）
2.C++實(shí)現(xiàn)二叉樹(shù)模板類（非遞歸）
3.C++實(shí)現(xiàn)二叉排序樹(shù)模板類（遞歸）
4.C++實(shí)現(xiàn)二叉排序樹(shù)模板類（非遞歸）
@ Conclusion:
1.構(gòu)建二叉樹(shù)（遞歸）：
A.判斷傳入字符串參數(shù)是否為空
B.遇“#”返回NULL
C.遇其他字符长窄，new一個(gè)二叉樹(shù)結(jié)點(diǎn)
a.data域是該字符
b.左孩子遞歸調(diào)用該函數(shù)滔吠，所傳標(biāo)志變量i加1
c.右孩子同b
2.先序遍歷（非遞歸）：
策略一：
A.向左深搜直至BTree的最左葉子節(jié)點(diǎn)的l_child指針
B.搜的同時(shí)纲菌，訪問(wèn)每一結(jié)點(diǎn)，并將結(jié)點(diǎn)入棧
C.逐一獲取棧中結(jié)點(diǎn)的右孩子疮绷，重復(fù)A翰舌，B
D.每獲取一個(gè)棧中結(jié)點(diǎn)，就將該結(jié)點(diǎn)彈出冬骚，直至椧渭空
策略二：
A.將根節(jié)點(diǎn)入棧
B.訪問(wèn)棧頂結(jié)點(diǎn)，并彈出棧頂結(jié)點(diǎn)
C.將該棧頂結(jié)點(diǎn)的右孩子入棧,如果有的話
D.將該棧頂結(jié)點(diǎn)的左孩子入棧,如果有的話
E.重復(fù)BCD,直至椫欢常空
3.中序遍歷（非遞歸）
策略一：
A.向左深搜直至BTree的最左葉子節(jié)點(diǎn)的l_child指針
B.搜的同時(shí)庇麦，將結(jié)點(diǎn)入棧
C.逐一訪問(wèn)棧頂結(jié)點(diǎn)，并將棧頂結(jié)點(diǎn)的右孩子入棧
D.重復(fù)ABC属愤，直至椗鳎空
4.后序遍歷（非遞歸）
策略一：
A.向左深搜直至BTree的最左葉子節(jié)點(diǎn)的l_child指針
B.搜的同時(shí)，將結(jié)點(diǎn)入棧
C.向右深搜棧頂元素的右孩子住诸，直至最右葉子節(jié)點(diǎn)驾胆，
*、每搜一個(gè)節(jié)點(diǎn)時(shí)贱呐，先重復(fù)AB
D.將棧中元素逐個(gè)彈出丧诺，并訪問(wèn)之
E.執(zhí)行D時(shí)，需注意將p指針置空
策略二：雙棧法
A.構(gòu)建兩個(gè)棧s1,s2
B.將根節(jié)點(diǎn)入棧s1
C.彈出s1的棧頂元素奄薇，并將該元素入棧s2
D.將該元素的左孩子入棧驳阎，如果有的話
E.將該元素的右孩子入棧，如果有的話
F.重復(fù)CDE,直至棧s1空
G.通過(guò)棧頂指針逐一遍歷棧s2的元素
5.根據(jù)先序遍歷序列構(gòu)建二叉樹(shù)（非遞歸）：
策略：
A.判空
B.向左深搜構(gòu)造馁蒂，并將結(jié)點(diǎn)入棧
C.重復(fù)執(zhí)行B直至最左葉子節(jié)點(diǎn)的左指針
D.逐一訪問(wèn)棧頂結(jié)點(diǎn)呵晚，向右深搜構(gòu)造
E.執(zhí)行D時(shí)，檢測(cè)是否有左結(jié)點(diǎn)沫屡，有則執(zhí)行C
6.根據(jù)后序遍歷序列構(gòu)建二叉樹(shù)（非遞歸）：
策略：
A.同5類似饵隙，順序顛倒一下就可以了
7.求二叉樹(shù)深度（非遞歸實(shí)現(xiàn)）
8.前中后Morris遍歷測(cè)試
9.測(cè)試BST相關(guān)操作 + 創(chuàng)建二叉排序樹(shù)（遞歸 & 非遞歸）
10.二叉樹(shù)findnode（非遞歸實(shí)現(xiàn)）
11.BST insertNode非遞歸 & removeNode非遞歸
@ Author: rh_Jameson
@ Date: 2014/12/22
**********************************************************************************/
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <iostream>
#include <string>
//#include <deque>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
//二叉樹(shù)類聲明
template<typename T>class BinaryTree;
//二叉樹(shù)結(jié)點(diǎn)類
template<typename T>
class TreeNode{
private:
TreeNode<T> *l_child,*r_child;
T data;
public:
TreeNode(){l_child = NULL;r_child = NULL;}
TreeNode(T value,TreeNode<T> *left = NULL,TreeNode<T> *right = NULL){
data = value;
l_child = left;
r_child = right;
}
friend class BinaryTree<T>; // 將二叉樹(shù)類聲明為友元類，方便訪問(wèn)該類私有變量
};
//二叉樹(shù)類
template<typename T>
class BinaryTree{
public:
/* 二叉樹(shù)常用操作 */
// 構(gòu)造函數(shù)
BinaryTree(const string &s, int method);
// 拷貝構(gòu)造函數(shù)
//BinaryTree(BinaryTree<T> &tree);
// 析構(gòu)函數(shù)
~BinaryTree();
// 外部刪除二叉樹(shù)函數(shù)
bool pubForDelBTree();
// 外部訪問(wèn)先序遍歷
void pubForPreOrder(int method);
// 外部訪問(wèn)中序遍歷
void pubForInOrder(int method);
// 外部訪問(wèn)后序遍歷
void pubForPostOrder(int method);
// 外部訪問(wèn)層次遍歷
void pubForLayerOrder();
// 外部查找值為et_value的二叉樹(shù)結(jié)點(diǎn)
void pubForFindNode(T et_value);
// 獲得二叉樹(shù)的根
TreeNode<T>* getRoot();
// 外部獲得二叉樹(shù)的深度
int pubForGetBTDepth();
/* 二叉排序樹(shù)常用操作 */
// 二叉排序樹(shù)構(gòu)造函數(shù)
//BinaryTree(vector<T> v);
BinaryTree(int v[]);
// 外部插入新結(jié)點(diǎn)
void pubForInsertNode(T &et_value);
// 外部刪除指定結(jié)點(diǎn)
void pubForRemoveNode(T et_value);
// 外部查找最大值
void pubForFindMax();
// 外部查找最小值
void pubForFindMin();
// 外部查找二叉樹(shù)是否包含指定值的結(jié)點(diǎn)
bool pubForContains(T et_value);
private:
TreeNode<T> *root; //二叉樹(shù)的根指針
/* 二叉樹(shù)常用操作 */
//構(gòu)建二叉樹(shù)
TreeNode<T>* createBTree(const string &s, int &i, int method);
//銷毀二叉樹(shù)
void delBTree(TreeNode<T>* &p);
//內(nèi)部先序遍歷
void PreOrder(TreeNode<T>* p, int method);
//內(nèi)部中序遍歷
void InOrder(TreeNode<T>* p, int method);
//內(nèi)部后序遍歷
void PostOrder(TreeNode<T>* p, int method);
//內(nèi)部層次遍歷
void LayerOrder(TreeNode<T> *p);
//內(nèi)部查找值為et_value的二叉樹(shù)結(jié)點(diǎn)
TreeNode<T>* findNode(TreeNode<T> *p, T et_value);
//內(nèi)部獲得二叉樹(shù)的深度
int getBTDepth(TreeNode<T> *p);
/* 二叉排序樹(shù)常用操作 */
// 構(gòu)建二叉排序樹(shù)
TreeNode<T>* createBST(int v[], int start, int end);
//TreeNode<T>* createBST(int v[], int start, int end);
// 插入新結(jié)點(diǎn)
void insertNode(T &et_value, TreeNode<T>* &p);
// 刪除指定結(jié)點(diǎn)
void removeNode(T et_value, TreeNode<T>* &p);
// 查找最大值
TreeNode<T>* findMax(TreeNode<T> *p);
// 查找最小值
TreeNode<T>* findMin(TreeNode<T> *p);
// 查找二叉樹(shù)是否包含指定值的結(jié)點(diǎn)
bool contains(T et_value, TreeNode<T> *p);
};
// 構(gòu)造函數(shù)
template <typename T>
BinaryTree<T>::BinaryTree(const string &s, int method){
root = NULL;
int i = 0;
root = createBTree(s, i, method);
}
//構(gòu)建二叉樹(shù)
template <typename T>
TreeNode<T>* BinaryTree<T>::createBTree(const string &s, int &i,int method){
switch(method){
case 1: //遞歸構(gòu)建
{
TreeNode<T>* BTree;
if(s.empty() ){
return NULL;
}
if(s[i] == '#'){
return NULL;
}
else{
BTree = new TreeNode<T>();
BTree->data = s[i];
BTree->l_child = createBTree(s,++i, method);
BTree->r_child = createBTree(s,++i, method);
return BTree;
}
}
case 2: //根據(jù)先序遍歷序列構(gòu)建（非遞歸）
{
if(s.empty()){
return NULL;
}
TreeNode<T> *BTNode = new TreeNode<T>, *head = BTNode;
BTNode->data = s[i++];
stack<TreeNode<T>* > SForBTree;
while(BTNode || !SForBTree.empty() ){
if(s[i] == '\0'){
break;
}
if(BTNode){ //向左深搜
SForBTree.push(BTNode);
if(s[i] == '#'){ //遇#置NULL
BTNode->l_child = NULL;
}
else{ //遇其他符號(hào)則新建結(jié)點(diǎn)
BTNode->l_child = new TreeNode<T>();
BTNode->l_child->data = s[i];
}
BTNode = BTNode->l_child;
}
else{ //反過(guò)來(lái)沮脖，向右深搜
BTNode = SForBTree.top();
SForBTree.pop();
if(s[i] == '#'){
BTNode->r_child = NULL;
}
else{
BTNode->r_child = new TreeNode<T>();
BTNode->r_child->data = s[i];
}
BTNode = BTNode->r_child;
}
i++;
}
return head;
}
case 3: //根據(jù)后序遍歷序列構(gòu)建二叉樹(shù)
{
if(s.empty()){
return NULL;
}
int cur = s.size() - 1;
stack<TreeNode<T>* > SForBTree;
TreeNode<T> *node = new TreeNode<T>(), *head = node;
node->data = s[cur--];
while(node || !SForBTree.empty()){
if(cur < 0){
break;
}
if(node){ //向右深搜
SForBTree.push(node);
if(s[cur] == '#'){ //遇#置NULL
node->r_child = NULL;
}
else{ //其他符號(hào)新建一個(gè)結(jié)點(diǎn)
node->r_child = new TreeNode<T>();
node->r_child->data = s[cur];
}
node = node->r_child;
}
else{ //反過(guò)來(lái)金矛，向左深搜
node = SForBTree.top();
SForBTree.pop();
if(s[cur] == '#'){
node->l_child = NULL;
}
else{
node->l_child = new TreeNode<T>();
node->l_child->data = s[cur];
}
node = node->l_child;
}
--cur;
}
return head;
}
}
}
//根據(jù)前序遍歷序列和中序遍歷序列構(gòu)建二叉樹(shù)
//失敗，模板類惹的禍勺届，只允許TreeNode<char>,待另寫一個(gè)cpp實(shí)現(xiàn)
/*template<typename T>
TreeNode<T>* createBTreeByPreAndInOrder(string &PreOrder, string &InOrder){
if(PreOrder.empty() || InOrder.empty()) return NULL;
TreeNode<T> *tmp;
if(PreOrder.size()){
tmp = new TreeNode<T>();
tmp->data = PreOrder[0];
int idx = InOrder.find(PreOrder[0]);
string PreLeft = PreOrder.substr(1, idx);
string PreRight = PreOrder.substr(idx + 1);
string InLeft = InOrder.substr(0, idx);
string InRight = InOrder.substr(idx + 1);
tmp->l_child = createBTreeByPreAndInOrder(PreLeft, InLeft);
tmp->r_child = createBTreeByPreAndInOrder(PreRight,InRight);
}
return tmp;
}*/
//// 拷貝構(gòu)造函數(shù)
//template <typename T>
//BinaryTree<T>::BinaryTree(BinaryTree<T> &tree){
//
//}
//析構(gòu)函數(shù)
template <typename T>
BinaryTree<T>::~BinaryTree(){
delBTree(root);
}
//外部銷毀二叉樹(shù)
template <class T>
bool BinaryTree<T>::pubForDelBTree(){
delBTree(root);
if(root){
return false;
}
return true;
}
//內(nèi)部銷毀二叉樹(shù)
template<typename T>
void BinaryTree<T>::delBTree(TreeNode<T>* &p){
/* 遞歸銷毀
if(p != NULL){
delBTree(p->l_child);
delBTree(p->r_child);
delete(p);
p = NULL;
}*/
//待實(shí)現(xiàn)：自上而下層次遍歷銷毀
//
//非遞歸實(shí)現(xiàn)(自下而上后續(xù)遍歷銷毀)
stack<TreeNode<T>* > SForBTree;
TreeNode<T> *pre;
while(p || !SForBTree.empty() ){
if(p){
SForBTree.push(p);
p = p->l_child;
}
else{
p = SForBTree.top();
if(p->r_child && p->r_child != pre ){ //有右子樹(shù)且右子樹(shù)未被訪問(wèn)過(guò)
p = p->r_child;
}
else{
pre = p;
SForBTree.pop();
delete p;
p = NULL; //!!!須置空驶俊，否則陷入死循環(huán)
//反復(fù)出棧 / 入棧
}
}
}
}
//外部訪問(wèn)先序遍歷
template<typename T>
void BinaryTree<T>::pubForPreOrder(int method){
if(!root){
cout << "空二叉樹(shù)！" << endl;
}
PreOrder(root, method);
}
//內(nèi)部訪問(wèn)先序遍歷
template<typename T>
void BinaryTree<T>::PreOrder(TreeNode<T>* p, int method){
switch(method){
case 1: //遞歸形式
if(p != NULL){
cout << p->data << "\t";
PreOrder(p->l_child, method);
PreOrder(p->r_child, method);
}
break;
case 2: //棧的實(shí)現(xiàn)形式
{
stack<TreeNode<T>* > SForBTree;
while(p != NULL || !SForBTree.empty() ){
if(p != NULL){
cout << p->data << "\t";
SForBTree.push(p);
p = p->l_child;
}
else{
p = SForBTree.top();
SForBTree.pop();
p = p->r_child;
}
}
break;
}
case 3: //棧實(shí)現(xiàn)形式二
{
stack<TreeNode<T>* > SForBTree;
if(p != NULL)
SForBTree.push(p);
while( !SForBTree.empty() ){
p = SForBTree.top();
cout << p->data << "\t";
SForBTree.pop();
if(p->r_child){
SForBTree.push(p->r_child);
}
if(p->l_child){
SForBTree.push(p->l_child);
}
}
break;
}
case 4: //Morris遍歷
{
TreeNode<T> *cur = p, *pre;
while(cur){
if(!cur->l_child){ //左孩子為空時(shí)免姿，輸出當(dāng)前結(jié)點(diǎn)饼酿，cur指向其右孩子
cout << cur->data << "\t";
cur = cur->r_child;
}
else{ //左孩子不為空時(shí)
pre = cur->l_child;
//找該結(jié)點(diǎn)的中序遍歷序列的前驅(qū)結(jié)點(diǎn)
while(pre->r_child != NULL && pre->r_child != cur){
pre = pre->r_child;
}
//前驅(qū)結(jié)點(diǎn)的右孩子指向當(dāng)前結(jié)點(diǎn)，并輸出當(dāng)前節(jié)點(diǎn)胚膊，cur指向其左孩子
if(pre->r_child == NULL){
pre->r_child = cur;
cout << cur->data << "\t"; //與中序遍歷唯一的不同嗜湃！
cur = cur->l_child;
}
//將前驅(qū)結(jié)點(diǎn)右孩子指向當(dāng)前結(jié)點(diǎn)的連接斷開(kāi)奈应，cur指向其右孩子
else{
pre->r_child = NULL;
cur = cur->r_child;
}
}
}
break;
}
}
}
//外部訪問(wèn)中序遍歷
template<typename T>
void BinaryTree<T>::pubForInOrder(int method){
if(!root){
cout << "空二叉樹(shù)" << endl;
}
InOrder(root, method);
}
//內(nèi)部訪問(wèn)中序遍歷
template<typename T>
void BinaryTree<T>::InOrder(TreeNode<T>* p, int method){
switch(method){
case 1: //遞歸形式
{ if(p != NULL){
InOrder(p->l_child, method);
cout << p->data << "\t";
InOrder(p->r_child, method);
}
break;
}
case 2: //棧的實(shí)現(xiàn)形式
{
stack<TreeNode<T>* > SForBTree;
while(p != NULL || !SForBTree.empty() ){
if(p != NULL){
SForBTree.push(p);
p = p->l_child;
}
else{
p = SForBTree.top();
cout << p->data << "\t";
SForBTree.pop();
p = p->r_child;
}
}
break;
}
case 3: //morris遍歷
{
TreeNode<T> *cur = p, *pre;
while(cur){
if(cur->l_child == NULL){
cout << cur->data << "\t";
cur = cur->r_child;
}
else{
pre = cur->l_child;
while(pre->r_child != NULL && pre->r_child != cur){
pre = pre->r_child;
}
if(pre->r_child == NULL){
pre->r_child = cur;
cur = cur->l_child;
}
else{
pre->r_child = NULL;
cout << cur->data << "\t"; //與前序遍歷代碼的不同澜掩！
cur = cur->r_child;
}
}
}
break;
}
}
}
//外部訪問(wèn)后序遍歷
template<typename T>
void BinaryTree<T>::pubForPostOrder(int method){
if(!root){
cout << "空二叉樹(shù)购披！" << endl;
}
PostOrder(root, method);
}
//內(nèi)部訪問(wèn)后序遍歷
template<typename T>
void BinaryTree<T>::PostOrder(TreeNode<T> *p, int method){
switch(method){
case 1: //遞歸形式實(shí)現(xiàn)
if(p != NULL){
PostOrder(p->l_child, method);
PostOrder(p->r_child, method);
cout << p->data << "\t";
}
break;
case 2: //棧形式實(shí)現(xiàn)，該代碼應(yīng)該可以轉(zhuǎn)作非遞歸銷毀二叉樹(shù)
{
stack<TreeNode<T>* > SForBTree;
TreeNode<T> *pre;
while(p || !SForBTree.empty() ){
if(p){
SForBTree.push(p);
p = p->l_child;
}
else{
p = SForBTree.top();
if(p->r_child && p->r_child != pre ){ //有右子樹(shù)且右子樹(shù)未被訪問(wèn)過(guò)
p = p->r_child;
}
else{
cout << p->data << "\t";
pre = p;
SForBTree.pop();
p = NULL; //!!!須置空肩榕，否則陷入死循環(huán)
//反復(fù)出棧 / 入棧
}
}
}
break;
}
case 3: //雙棧形式實(shí)現(xiàn)
{
stack<TreeNode<T>* > s1, s2;
if(p != NULL) s1.push(p);
while(!s1.empty()){
p = s1.top();
s1.pop();
s2.push(p);
if(p->l_child){
s1.push(p->l_child);
}
if(p->r_child){
s1.push(p->r_child);
}
}
while(!s2.empty()){
p = s2.top();
cout << p->data << "\t";
s2.pop();
}
break;
}
case 4: //morris遍歷
{
TreeNode<T> *cur = p, *pre;
while(cur != NULL){
if(cur->l_child == NULL){
cur = cur->r_child;
}
else{
pre = cur->l_child;
while(pre->r_child != NULL && pre->r_child != cur){
pre = pre->r_child;
}
if(pre->r_child == NULL){
pre->r_child = cur;
cur = cur->l_child;
}
else{
//printReverse(cur->l_child, pre);
pre->r_child = NULL;
cur = cur->r_child;
}
}
}
break;
}
}
}
/*Morris 后續(xù)遍歷相關(guān)函數(shù)
* template<typename T>
void reverse(TreeNode<T> *from, TreeNode<T> *to){
if(from = to){
return;
}
TreeNode<T> =
}
template<typename T>
void printReverse(TreeNode<T> *from, TreeNode<T> *to){
TreeNode<T> *p = to;
reverse(from, to);
while(true){
cout << p->data << "\t";
if(p == from){
break;
}
p = p->r_child;
}
reverse(to, from);
}*/
//外部查找值為et_value的二叉樹(shù)結(jié)點(diǎn)
template<typename T>
void BinaryTree<T>::pubForFindNode(T et_value){
TreeNode<T> *res = findNode(root, et_value);
if(res == NULL){
cout << "找不到相應(yīng)結(jié)點(diǎn)" << endl;
}
else{
cout << "找到該結(jié)點(diǎn)刚陡，該結(jié)點(diǎn)值為:" << res->data << endl;
}
}
//查找值為et_value的二叉樹(shù)結(jié)點(diǎn)
template<typename T>
TreeNode<T>* BinaryTree<T>::findNode(TreeNode<T> *p, T et_value){
//遞歸實(shí)現(xiàn)
/* if(p == NULL){
return NULL;
}
if(p->data == et_value){
return p;
}
TreeNode<T> *tmp = findNode(p->l_child, et_value);
if(tmp != NULL){
return tmp;
}
else{
return findNode(p->r_child, et_value);
}
*/
//非遞歸實(shí)現(xiàn)
stack<TreeNode<T>*> s;
while(p != NULL || !s.empty()){
if(p != NULL){
s.push(p);
p = p->l_child;
}
else{
p = s.top();
s.pop();
if(p->data == et_value) break;
p = p->r_child;
}
}
return p;
}
//外部獲得二叉樹(shù)的深度
template<typename T>
int BinaryTree<T>::pubForGetBTDepth(){
return getBTDepth(root);
}
//獲得二叉樹(shù)的深度
template<typename T>
int BinaryTree<T>::getBTDepth(TreeNode<T> *p){
/* 遞歸實(shí)現(xiàn)1
int depth = 0;
if(p != NULL){
int l_child_depth = getBTDepth(p->l_child);
int r_child_depth = getBTDepth(p->r_child);
depth = (l_child_depth >= r_child_depth) ? (l_child_depth + 1) : (r_child_depth + 1);
//depth = 1 + (l_child_depth >= r_child_depth ? l_child_depth : r_child_depth);
}
return depth;
*/
/* 遞歸實(shí)現(xiàn)2
if(p == NULL) return 0;
return 1 + max(getBTDepth(p->l_child), getBTDepth(p->r_child));
*/
//非遞歸實(shí)現(xiàn)
/* int depth = 0, maxDepth = 0;
stack<TreeNode<T>*> *s = new stack<TreeNode<T>*>();
while(p != NULL || !s->empty()){
if(p != NULL){
s->push(p);
++depth;
p = p->l_child;
}
else{
p = s->top();
s->pop();
p = p->r_child;
if(p == NULL){
if(depth > maxDepth){
maxDepth = depth;
}
depth--;
}
}
}
return maxDepth - 1;
*/
/* 雙棧形式
if (p == NULL) return 0;
stack<TreeNode<T> *> gray;
stack<int> depth;
int maxDepth = 0;
gray.push(p);
depth.push(1);
while (!gray.empty()) {
TreeNode<T> *tmp = gray.top();
int num = depth.top();
gray.pop();
depth.pop();
if (tmp->l_child == NULL && tmp->r_child == NULL) {
maxDepth = num > maxDepth ? num : maxDepth;
}
else {
if (tmp->l_child != NULL) {
gray.push(tmp->l_child);
depth.push(num + 1);
}
if (tmp->r_child != NULL) {
gray.push(tmp->r_child);
depth.push(num + 1);
}
}
}
return maxDepth;
*/
/* 隊(duì)列層次遍歷實(shí)現(xiàn)
int height = 0,rowCount = 1;
if(root == NULL){
return 0;
}
queue<TreeNode<T>*> queue;
queue.push(p);
while(!queue.empty()){
TreeNode<T> *node = queue.front();
queue.pop();
//一層的元素個(gè)數(shù)減1，一層遍歷完高度加1
rowCount --;
if(node->l_child){
queue.push(node->l_child);
}
if(node->r_child){
queue.push(node->r_child);
}
//一層遍歷完
if(rowCount == 0){
//高度加1
height++;
//下一層元素個(gè)數(shù)
rowCount = queue.size();
}
}
return height;
*/
/* 層次遍歷樹(shù)的層數(shù),NULL為每一層節(jié)點(diǎn)的分割標(biāo)志 */
if(p == NULL)return 0;
int res = 0;
queue<TreeNode<T>*> Q;
Q.push(p);
Q.push(NULL);
while(Q.empty() == false)
{
TreeNode<T> *p = Q.front();
Q.pop();
if(p != NULL)
{
if(p->l_child)Q.push(p->l_child);
if(p->r_child)Q.push(p->r_child);
}
else
{
res++;
if(Q.empty() == false)Q.push(NULL);
}
}
return res;
}
//外部訪問(wèn)層次遍歷
template<typename T>
void BinaryTree<T>::pubForLayerOrder(){
LayerOrder(root);
}
//內(nèi)部層次遍歷
template<typename T>
void BinaryTree<T>::LayerOrder(TreeNode<T> *p){
if(p == NULL){
cout << "空樹(shù)株汉！" << endl;
return;
}
queue<TreeNode<T> *> queueTreeNode;
queueTreeNode.push(p);
while(queueTreeNode.size() ){
TreeNode<T> *tmp = queueTreeNode.front();
queueTreeNode.pop();
cout << tmp->data << "\t";
if(tmp->l_child != NULL){
queueTreeNode.push(tmp->l_child);
}
if(tmp->r_child != NULL){
queueTreeNode.push(tmp->r_child);
}
}
/*deque雙向隊(duì)列版
deque<TreeNode<T> *> dequeTreeNode;
dequeTreeNode.push_back(p);
while(dequeTreeNode.size() ){
TreeNode<T> *tmp = dequeTreeNode.front();
dequeTreeNode.pop_front();
cout << tmp->data << "\t";
if(tmp->l_child != NULL){
dequeTreeNode.push_back(tmp->l_child);
}
if(tmp->r_child != NULL){
dequeTreeNode.push_back(tmp->r_child);
}
}*/
}
//獲得二叉樹(shù)的根
template<typename T>
TreeNode<T>* BinaryTree<T>::getRoot(){
return root;
}
/* 二叉排序樹(shù)常用操作 */
// 二叉排序樹(shù)構(gòu)造函數(shù)
template<typename T>
BinaryTree<T>::BinaryTree(int v[]){
//vector<int> vv(v, v + sizeof(v)/sizeof(v[0]));
/*vector<int> vv(v, v + 10);
if(!vv.size()){
cout << "生成失敗筐乳，原因：空數(shù)組" << "\t";
return;
}
sort(vv.begin(), vv.end());
*/
sort(v, v + 9);
/*if(sizeof(v) / sizeof(int)){
cout << "生成失敗，原因：空數(shù)組" << "\t";
return;
}*/
root = createBST(v, 0, 9 - 1);
}
// 構(gòu)建二叉排序樹(shù)
template<typename T>
TreeNode<T>* BinaryTree<T>::createBST(int sorted_Vec[],int start,int end){
//遞歸實(shí)現(xiàn)
if(end < start){
return NULL;
}
int mid = (start + end) / 2;
TreeNode<T> *node = new TreeNode<T>();
node->data = sorted_Vec[mid];
node->l_child = createBST(sorted_Vec, start, mid - 1);
node->r_child = createBST(sorted_Vec, mid + 1, end);
return node;
//非遞歸實(shí)現(xiàn)
/*失敗乔妈，每個(gè)結(jié)點(diǎn)的start和end都需記住蝙云，該模板無(wú)相應(yīng)屬性
* 為避免大量修改代碼，放棄實(shí)現(xiàn)～～
* mid = (start + end) / 2;
stack<TreeNode<T>* > s = new stack<TreeNode<T>* >();
stack<int> mid_s = new stack<int>();
TreeNode<T> *node = new TreeNode<T>();
mid_s.push(end);
while(mid >= 0 || !s.empty()){
if(mid >= 0){
node = new TreeNode<T>();
node->data = sorted_Vec[mid];
mid_s.push(mid);
s.push(node);
node = node->l_child;
mid = (0 + mid - 1) / 2;
}
else{
mid = mid_s.top();
node = s.top();
mid_s.pop();
s.pop();
}
}
*/
}
// 外部插入新結(jié)點(diǎn)
template<typename T>
void BinaryTree<T>::pubForInsertNode(T &et_value){
insertNode(et_value, root);
}
// 插入新結(jié)點(diǎn)
template<typename T>
void BinaryTree<T>::insertNode(T &et_value, TreeNode<T>* &p){
//遞歸實(shí)現(xiàn)
/* if(p == NULL){
p = new TreeNode<T>();
p->data = et_value;
}
else if(et_value < p->data){
insertNode(et_value, p->l_child);
}
else if(et_value > p->data){
insertNode(et_value, p->r_child);
}
else //相等（重復(fù)）則不做任何操作
;
*/
//非遞歸實(shí)現(xiàn)
TreeNode<T> *cur = p, *parent = NULL, *newNode = new TreeNode<T>();
newNode->data = et_value;
if(p == NULL){ //二叉樹(shù)為空的情況
p = newNode;
return;
}
while(true){
if(cur == NULL){
if(et_value < parent->data) //插入到葉子節(jié)點(diǎn)的左孩子
parent->l_child = newNode;
else
parent->r_child = newNode;
return;
}
parent = cur;
if(et_value < cur->data)
cur = cur->l_child;
else if(et_value > cur->data)
cur = cur->r_child;
else
return; //重復(fù)路召，不插入勃刨，直接退出
}
}
// 外部刪除指定結(jié)點(diǎn)
template<typename T>
void BinaryTree<T>::pubForRemoveNode(T et_value){
removeNode(et_value, root);
}
// 刪除指定結(jié)點(diǎn)
template<typename T>
void BinaryTree<T>::removeNode(T et_value, TreeNode<T> * &p){
//遞歸實(shí)現(xiàn)
/* if(p == NULL){
return; //該值未找到，停止
}
if(et_value < p->data){
removeNode(et_value, p->l_child);
}
else if(et_value > p->data){
removeNode(et_value, p->r_child);
}
else if(p->l_child != NULL && p->r_child != NULL){ //待刪結(jié)點(diǎn)有兩個(gè)孩子的情況
p->data = findMin(p->r_child)->data; //需琢磨另一種寫法
removeNode(p->data, p->r_child);
}
else{ //無(wú)孩子或有一個(gè)孩子情況
TreeNode<T> *tmp = p;
p = (p->l_child != NULL) ? p->l_child : p->r_child;
delete tmp;
}
*/
//非遞歸實(shí)現(xiàn)
/* TreeNode<T> *cur = p, *pre, *tmp, *child;
if(p->data == et_value && !p->l_child && !p->r_child){ //只有一個(gè)節(jié)點(diǎn)的情況
p = NULL;
return;
}
while(true){
if(cur == NULL) break;
if(et_value < cur->data){
pre = cur;
cur = cur->l_child;
}else if(et_value > cur->data){
pre = cur;
cur = cur->r_child;
}else if(cur->l_child != NULL && cur->r_child != NULL){ //待刪結(jié)點(diǎn)有兩個(gè)孩子的情況
tmp = findMin(cur->r_child);
cur->data = tmp->data;
child = tmp->r_child; //暫存其右孩子
pre = cur->r_child;
while(pre->l_child != tmp) //找倒數(shù)第二小的結(jié)點(diǎn)
pre = pre->l_child;
pre->l_child = child;
delete tmp;
break;
}
else{ //無(wú)孩子或有一個(gè)孩子情況
tmp = cur;
cur = (cur->l_child != NULL) ? cur->l_child : cur->r_child;
(pre->l_child == tmp) ? pre->l_child = cur : pre->r_child = cur;
delete tmp;
break;
}
}
*/
//非遞歸實(shí)現(xiàn)
TreeNode<T> *cur = p, *pre, *tmp, *child;
if(p->data == et_value && !p->l_child && !p->r_child){ //只有一個(gè)節(jié)點(diǎn)的情況
p = NULL;
return;
}
while(true){
if(cur == NULL) break; //找不到或BST為空
if(et_value < cur->data){
pre = cur;
cur = cur->l_child;
}
else if(et_value > cur->data){
pre = cur;
cur = cur->r_child;
}
else{
if(cur->l_child != NULL && cur->r_child != NULL){ //待刪結(jié)點(diǎn)有兩個(gè)孩子的情況
tmp = findMin(cur->r_child);
cur->data = tmp->data;
child = tmp->r_child; //暫存其右孩子
pre = cur->r_child;
while(pre->l_child != tmp) pre = pre->l_child; //找倒數(shù)第二小的結(jié)點(diǎn)
pre->l_child = child;
}
else{ //無(wú)孩子或有一個(gè)孩子情況
tmp = cur;
cur = (cur->l_child != NULL) ? cur->l_child : cur->r_child;
(pre->l_child == tmp) ? pre->l_child = cur : pre->r_child = cur;
}
delete tmp;
break;
}
}
}
// 外部查找最大值
template<typename T>
void BinaryTree<T>::pubForFindMax(){
cout << "該二叉樹(shù)的最大值為：" << findMax(root)->data << endl;
}
// 查找最大值
template<typename T>
TreeNode<T>* BinaryTree<T>::findMax(TreeNode<T> *p){
/* 遞歸實(shí)現(xiàn) */
/* if(p == NULL){
return NULL;
}
if(p->r_child == NULL){
return p;
}
return findMax(p->r_child);
*/
/* 非遞歸實(shí)現(xiàn) */
/* while(p != NULL){
if(p->r_child == NULL){
return p;
}
p = p->r_child;
}
return NULL;
*/
/* 非遞歸實(shí)現(xiàn)2 */
if(p != NULL){
while(p->r_child != NULL){
p = p->r_child;
}
}
return p;
}
// 外部查找最小值
template<typename T>
void BinaryTree<T>::pubForFindMin(){
cout << "該二叉樹(shù)的最小值為：" << findMin(root)->data << endl;
}
// 查找最小值
template<typename T>
TreeNode<T>* BinaryTree<T>::findMin(TreeNode<T> *p){
/* 遞歸實(shí)現(xiàn) */
/* if(p == NULL){
return NULL;
}
//if(p->l_child == NULL || *((unsigned int *)p->l_child) == 0xFEEEFEEE ){
if(p->l_child == NULL){
p->l_child = NULL;
return p;
}
return findMin(p->l_child);
*/
/* 非遞歸實(shí)現(xiàn)
while(p != NULL){
if(p->l_child == NULL){
return p;
}
p = p->l_child;
}
return NULL;
*/
/* 非遞歸實(shí)現(xiàn)2 */
if(p != NULL){
while(p->l_child != NULL){
p = p->l_child;
}
}
return p;
}
// 外部查找二叉樹(shù)是否包含指定值的結(jié)點(diǎn)
template<typename T>
bool BinaryTree<T>::pubForContains(T et_value){
return contains(et_value, root);
}
// 查找二叉樹(shù)是否包含指定值的結(jié)點(diǎn)
template<typename T>
bool BinaryTree<T>::contains(T et_value, TreeNode<T> *p){
//遞歸實(shí)現(xiàn)
/* if(p == NULL){
return false;
}
if(et_value < p->data){
contains(et_value, p->l_child);
}
else if(et_value > p->data){
contains(et_value, p->r_child);
}
else{
return true;
}
*/
//非遞歸實(shí)現(xiàn)
while(p != NULL){
if(et_value < p->data)
p = p->l_child;
else if(et_value > p->data)
p = p->r_child;
else
return true;
}
return false;
}
#endif
