【数据结构与算法】2. 树[笔记]

Notes

1. 数据结构：树 的操作集 C/C++代码实现

1. 二分查找:

int Binary_Search(int *List, int num, int length)   // List：列表， num：差找目标数，length：数组长度
{
    if(length == 0)  return -1;
    int left=0, right=length-1, mid = length/2;
    int cnt=0;

    while(left <= right)
    {
        cnt++;
        cout << cnt << ' ';
        if(List[mid] == num)  return mid;
        // else if(mid == (left+right)/2)  return -1;   // 个人方法：判定未找到
        // mid = (left+right)/2;
        if(List[mid] > num)  left = left, right = mid - 1;
        else if(List[mid] < num)  left = mid + 1, right = right;
        mid = (left+right)/2;
    }
    return -1;
}

---

2. 二叉树 ( 链表结构 ) :

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
// 二叉树_链表结构实现

typedef struct TreeNode *BinTree;   // 二叉树
struct TreeNode{
    int Data;
    BinTree Left;
    BinTree Right;
};
stack <BinTree> Stack;

// 二叉树标准操作
BinTree CreateBinTree();               // 创建二叉树
BinTree Insert(int Data);              // 插入数据
void PreOrderTraversal(BinTree BT);    // 先序遍历，根-->左-->右
void InOrderTraversal(BinTree BT);     // 中序遍历，左-->根-->右
void PostOrderTraversal(BinTree BT);   // 后序遍历，左-->右-->梗
void LevelOrderTraversal(BinTree BT);  // 层次遍历，1st层-> 2st层。。。。
void FindLeaves(BinTree BT);           // 输出叶结点
int GetHeight(BinTree BT);             // 输出树高


BinTree Insert(int Data)
{
    BinTree BT = new struct TreeNode;
    BT->Data = Data;
    BT->Left = BT->Right = NULL;
    return BT;
}

BinTree CreateBinTree()
{
    BinTree BT = new struct TreeNode;
    BT->Data = 1;
    BT->Left = Insert(2);
    BT->Right = Insert(3);
    BT->Left->Left = Insert(4);
    BT->Left->Right = Insert(6);
    BT->Left->Right->Left = Insert(5);
    BT->Right->Left = Insert(7);
    BT->Right->Right = Insert(9);
    BT->Right->Left->Right = Insert(8);
    return BT;
}

void PreOrderTraversal(BinTree BT)
{
    if(BT)
    {
        cout << "PreOrderTraversal: " << BT->Data << endl;
        PreOrderTraversal(BT->Left);
        PreOrderTraversal(BT->Right);
    }
}

void InOrderTraversal(BinTree BT)
{
    if(BT)
    {
        InOrderTraversal(BT->Left);
        cout << "InOrderTraversal: " << BT->Data << endl;
        InOrderTraversal(BT->Right);
    }
}

void PostOrderTraversal(BinTree BT)
{
    if(BT)
    {
        PostOrderTraversal(BT->Left);
        PostOrderTraversal(BT->Right);
        cout << "PostOrderTraversal: " << BT->Data << endl;
    }
}

void LevelOrderTraversal(BinTree BT)
{
    queue <BinTree> BT_q;
    BinTree temp;
    BT_q.push(BT);
    while(!BT_q.empty())
    {
        temp = BT_q.front();
        cout << "LevelOrderTraversal: " << BT_q.front()->Data << endl;
        BT_q.pop();
        if(temp->Left)   BT_q.push(temp->Left);
        if(temp->Right)  BT_q.push(temp->Right);
    }
}

void FindLeaves(BinTree BT)
{
    if(BT)
    {
        if(!BT->Left && !BT->Right)  cout << "FindLeaves: " << BT->Data << endl;
        FindLeaves(BT->Left);
        FindLeaves(BT->Right);
    }
}

int GetHeight(BinTree BT)
{
    int heightLeft, heightRight;
    if(BT)
    {
        heightLeft = GetHeight(BT->Left);
        heightRight = GetHeight(BT->Right);
        return (heightLeft>heightRight?heightLeft:heightRight) + 1;
    }
    return 0;
}

// 测试程序
int main()
{
    BinTree BT = CreateBinTree();
    PreOrderTraversal(BT);
    InOrderTraversal(BT);
    PostOrderTraversal(BT);
    LevelOrderTraversal(BT);
    FindLeaves(BT);
    cout << "GetHeight: " << GetHeight(BT) << endl;
    return 0;
} 

---

3. 二叉搜索树 :

#include <iostream>
#include <algorithm>
using namespace std;
// 二叉搜索树

typedef struct TreeNode *BinTree;
struct TreeNode
{
    int Data;
    BinTree Left;
    BinTree Right;
};

// 二叉搜索树操作集
BinTree Find(int X, BinTree BST);       // 递归查找
BinTree IterFind(int X, BinTree BST);   // 非递归查找
BinTree FindMin(BinTree BST);           // 递归查找最小值
BinTree FindMax(BinTree BST);           // 非递归差找最大值
BinTree Insert(int X, BinTree BST);     // 递归插入
BinTree Delete(int X, BinTree BST);     // 递归删除
void InOrderTraversal(BinTree BT);      // 中序遍历


BinTree Find(int X, BinTree BST)
{
    if(BST)
        if(X > BST->Data)  return Find(X, BST->Right);
        else if(X < BST->Data)  return Find(X, BST->Left);
        else   return BST;
    return NULL;
}

BinTree IterFind(int X, BinTree BST)
{
    while(BST)
        if(X > BST->Data)  BST = BST->Right;
        else if(X < BST->Data)  BST = BST->Left;
        else  return BST;
    
    return NULL;
}

BinTree FindMin(BinTree BST)
{
    if(!BST)  return NULL;
    else if(BST->Left)  return FindMin(BST->Left);
    else return BST;
}

BinTree FindMax(BinTree BST)
{
    if(!BST)  return NULL;
    while(BST->Right)  BST = BST->Right;
    return BST;
} 

BinTree Insert(int X, BinTree BST)
{
    if(!BST)
    {
        BST = new struct TreeNode;
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }
    else
    {
        if(X < BST->Data)  BST->Left = Insert(X, BST->Left);
        else if(X > BST->Data)  BST->Right = Insert(X, BST->Right);
    }
    return BST;
}

BinTree Delete(int X, BinTree BST)
{
    BinTree Tmp;
    if(!BST)  cout << "Fall To Find: X in BinTree: BST !!!" << endl;
    else if(X < BST->Data)  BST->Left = Delete(X, BST->Left);
    else if(X > BST->Data)  BST->Right = Delete(X, BST->Right);
    else
    {
        if(BST->Left && BST->Right)  
        {
            Tmp = FindMin(BST->Right);
            BST->Data = Tmp->Data;
            BST->Right = Delete(Tmp->Data, BST->Right);
        }
        else
        {
            Tmp = BST;
            if(!BST->Left)  BST = BST->Left;
            else if(!BST->Right)  BST = BST->Right;
            delete Tmp;
        }
    }
    
    return BST;
}

void InOrderTraversal(BinTree BT)
{
    if(BT)
    {
        InOrderTraversal(BT->Left);
        cout << BT->Data;
        InOrderTraversal(BT->Right);
    }
}

---

4. 堆 :

#include <iostream>
#include <algorithm>
using namespace std;

#define MaxData 10000;

typedef struct HeapStruct *MaxHeap;
struct HeapStruct
{
    int *Data;      // 数组
    int Size;       // 存储当前Size大小
    int Capacity;   // Heap的最大容积
};

MaxHeap CreateHeap(int MaxSize);        // 创建堆
bool IsFull(MaxHeap H);                 // 判定堆是否为满
bool Insert(MaxHeap H, int item);       // 插入一个item
bool IsEmpty(MaxHeap H);                // 判定堆是否为空
int DeleteMax(MaxHeap H);               // 删除堆中最大值
void LevelOrderTraversal(MaxHeap H);    // 层序遍历  

MaxHeap CreateHeap(int MaxSize)
{
    MaxHeap Heap = new struct HeapStruct;
    Heap->Data = new int[MaxSize+1];
    Heap->Data[0] = MaxData;            // 建立哨兵
    Heap->Capacity = MaxSize;
    Heap->Size = 0;
    return Heap;
}

bool IsFull(MaxHeap H)
{
    return (H->Size == H->Capacity);
}

bool IsEmpty(MaxHeap H)
{
    return (!H->Size);
}

bool Insert(MaxHeap H, int item)
{
    if(IsFull(H))
    {
        cout << "This Heap is full !!!" << endl;
        return false;
    }
    int i;
    for(i = ++H->Size; H->Data[i/2] < item; i /= 2)  H->Data[i] = H->Data[i/2];
    H->Data[i] = item;
    return true;
}

int DeleteMax(MaxHeap H)
{
    int parent, child;
    int MaxItem = H->Data[1];
    int LastItem = H->Data[H->Size--];
    if(IsEmpty(H))
    {
        cout << "This Heap is Empty !!!" << endl;
        return -1;
    }
    for(parent = 1; parent*2 <= H->Size; parent = child)
    {
        child = parent*2;
        if(child!=H->Size && H->Data[child] < H->Data[child+1])  child++;
        if(H->Data[child] <= LastItem)  break;
        else  H->Data[parent] = H->Data[child];
    }
    H->Data[parent] = LastItem;
    return MaxItem;
}

void LevelOrderTraversal(MaxHeap H)
{
	for(int i = 1;i<=H->Size;i++)  cout << H->Data[i] << ' ';
	cout << endl;
} 

int main()
{
	MaxHeap H;
	int MaxSize = 100;
	H = CreateHeap(MaxSize);
	Insert(H,55);
	Insert(H,66);
	Insert(H,44);
	Insert(H,33);
	Insert(H,11);
	Insert(H,22);
	Insert(H,88);
	Insert(H,99);
	/*
		 99
		/  \
	   88  66
	  / \  / \
	 55 11 22 44
	/ 
   33	  
	*/
	LevelOrderTraversal(H);
	DeleteMax(H);
	LevelOrderTraversal(H);
	DeleteMax(H);
	LevelOrderTraversal(H);
	DeleteMax(H);
	LevelOrderTraversal(H);
	DeleteMax(H);
	LevelOrderTraversal(H);
	return 0;
}

---

5. 哈夫曼树 :

#include <iostream>
#include <algorithm>
using namespace std;

#define MaxSize 1000
#define MinData -1000

int w1[11] = {13,1,45,7,20,4,19,13,40,33,38};

typedef struct TreeNode *HuffmanTree;
typedef struct HeapStruct *MinHeap;
struct HeapStruct
{
    HuffmanTree *Data;
    int Size;
    int Capacity;
};
struct TreeNode
{
    int Weight;
    HuffmanTree Left;
    HuffmanTree Right;
};

MinHeap CreateHeap();                           // 初始化堆
HuffmanTree Create();                           // 初始化哈夫曼树
void sort(MinHeap H, int i);                    // 调整子最小堆
void adjust(MinHeap H);                         // 调整最小堆
void BuildMinHeap(MinHeap H);                   // 建堆
HuffmanTree Delete(MinHeap H);                  // 删除最小堆元素
void Insert(MinHeap H, HuffmanTree Huff);       // 插入最小堆元素
void PreOrderTraversal(HuffmanTree Huff);       // 先序遍历
HuffmanTree Huffman(MinHeap H);                 // 哈夫曼树的构建

MinHeap CreateHeap()
{
	MinHeap H = new struct HeapStruct;
    H->Data = new struct TreeNode*[MaxSize+1];
    H->Capacity = MaxSize;
    H->Size = 0;

    // 哨兵
    HuffmanTree Huff = Create();
    Huff->Weight = MinData;
    H->Data[0] = Huff;
    return H;
}

HuffmanTree Create()
{
    HuffmanTree Huff = new struct TreeNode;
    Huff->Weight = 0;
    Huff->Left = Huff->Right = NULL;
    return Huff;
}

void sort(MinHeap H, int i)
{
    int parent, child;
    int tmp = H->Data[i]->Weight;
    for(parent = i; parent*2 <= H->Size; parent = child)
    {
        child = 2*parent;
        if(child!=H->Size && H->Data[child+1]->Weight < H->Data[child]->Weight)  child++;
        if(H->Data[child]->Weight >= tmp)  break;
        else  H->Data[parent] = H->Data[child];
    }
    H->Data[parent]->Weight = tmp;
}

void adjust(MinHeap H)
{
    for(int i=H->Size/2; i>0; i--)  sort(H, i);
}

void BuildMinHeap(MinHeap H)
{
    HuffmanTree Huff;
    for(int i=0; i<sizeof(w1)/sizeof(int); i++)
    {
        Huff = Create();
        Huff->Weight = w1[i];
        H->Data[++H->Size] = Huff;
    }
    adjust(H);
}

HuffmanTree Delete(MinHeap H)
{
    int parent, child;
    HuffmanTree T = H->Data[1];
    HuffmanTree tmp = H->Data[H->Size--];
    for(parent = 1; parent*2 <= H->Size; parent = child)
    {
        child = 2*parent;
        if(child!=H->Size && H->Data[child+1]->Weight < H->Data[child]->Weight)  child++;
        if(H->Data[child]->Weight >= tmp->Weight)  break;
        else  H->Data[parent] = H->Data[child];
    }
    H->Data[parent] = tmp;
    return T;
}

void Insert(MinHeap H, HuffmanTree Huff)
{
    int Weight = Huff->Weight;
    int i = ++H->Size;
    for(; H->Data[i/2]->Weight > Weight; i/=2)  H->Data[i] = H->Data[i/2];
    H->Data[i] = Huff;
}

void PreOrderTraversal(HuffmanTree Huff)
{
	if(Huff)
    {
		cout << Huff->Weight << " ";
		PreOrderTraversal(Huff->Left);
		PreOrderTraversal(Huff->Right);
	}
    // cout << endl;
}

HuffmanTree Huffman(MinHeap H)
{
    int i;
    HuffmanTree T;
    BuildMinHeap(H);
    for(i = 1; i<H->Size; i++)
    {
        T = new struct TreeNode;
        T->Left = Delete(H);
        T->Right = Delete(H);
        T->Weight = T->Left->Weight + T->Right->Weight;
        Insert(H, T);
    }
    T = Delete(H);
    return T;
}

---

6. 并查集 :

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define MaxSize 1000
typedef struct{
    int Data;
    int Parent;
}SetType;

int Find(SetType *s, int x1);                                 // 查
void Union(SetType *s, int x1, int x2);     // 并

int Find(SetType *s, int x1)
{
    int i;
    for(i=0; i<MaxSize && s[i].Data != x1; i++);
    if(MaxSize <= i)  return false;
    for(; s[i].Parent>=0; i = s[i].Parent);
    return i;
}

void Union(SetType *s, int x1, int x2)
{
    int root1 = Find(s, x1), root2 = Find(s, x2);
    if(root1 != root2)  s[root1].Parent = root2;
}