目录

• 树
  • 二叉树
    • 操作集
      • 遍历
      • 例
      • 二叉查找树
      • 平衡二叉树AVL
    • 存储结构
      • 顺序结构
      • 链式结构
    • 满二叉树
    • 完全二叉树
  • 哈夫曼树
• 图
• 哈希

树

二叉树

操作集

//判空
//创建
//遍历
	//先序
	//中序
	//后序
	//层序

遍历

//先序
void PreOrderTraversal (BinTree BT) {
	if (BT) {
		printf("%d", BT->Data);
		PreOrderTraversal (BT->Left);
		PreOrderTraversal (BT->Right);
	}
}
//中序
void InOrderTraversal (BinTree BT) {
	if (BT) {
		InOrderTraversal (BT->Left);
		printf("%d", BT->Data);
		InOrderTraversal (BT->Right);
	}
}
//后序
void PostOrderTraversal (BinTree BT) {
	if (BT) {
		PostOrderTraversal (BT->Left);
		PostOrderTraversal (BT->Right);
		printf("%d", BT->Data);
}

//先序 非递归
void PreOrderTraversal(BinTree T) {
    Stack S = CreatStack(MaxSize);
    while (T || IsEmpty(S)) {
        while (T) {
            printf("%d", T->data);
            Push(S,T);
            T = T->Left;
        }
        if(!Empty(S)) {
            T = Pop(S);
            T = T->Right;
        }
    }    
//中序 非递归
void InOrderTraversal(BinTree T) {
    Stack S = CreatStack(MaxSize);
    while (T || IsEmpty(S)) {
        while (T) {
            Push(S,T);
            T = T->Left;
        }
        if(!Empty(S)) {
            T = Pop(S);
            printf("%d", T->data);
            T = T->Right;
        }
    }
}
//后序 非递归
void PostOrderTraversal(BinTree T) {
    Stack S = CreatStack(MaxSize);
    while (T || IsEmpty(S)) {
        while (T) {
            Push(S,T);
            T = T->Right;
        }
        if(!Empty(S)) {
            T = Pop(S);
            printf("%d", T->data);
            T = T->Left;
        }
    }
}
//层序
void LevelOrderTraversal(BinTree T) {
    Queue Q;
    if (!T) return;
    Q = CreatQueue(MaxSize);
    AddQ(Q, T);
    while(!IsEmpty(Q)) {
        T = DeleteQ(Q);
        printf("%d", T->Data);
        if (T->Left) AddQ(Q, T->Left);
        if (T->Right) AddQ(Q, T->Right); 
    }
}

例

//打印所有叶节点
void PintLeaf (BinTree BT) {
	if (BT) {
        if(BT->Left==NULL && BT->Right==NULL)
            printf("%d", BT->Data);
		InOrderTraversal (BT->Left);
		InOrderTraversal (BT->Right);
	}
}
//求二叉树高度
int PostOrderGetHeight(BinTree T) {
    int HL,HR,MaxH;
    if(T) {
        HL = PostOrderGetHeight(T->Left);
        HR = PostOrderGetHeight(T->Right);
        MaxH = (HL > HR) ? HL : HR;
        return (MaxH + 1);
    }
    return 0;
}
//由两种遍历序列确定二叉树
//必须要有中序

//判断两颗二叉树是否同构
int main() {
    建二叉树1
    建二叉树2
    判断是否同构并输出
    
    return 0;
}

#define MaxTree 10
#define ElementType char
#define Tree int
#define Null -1
struct TreeNode{
    ElementType Element;
    Tree Left;
    Tree Right;
}T1[MaxTree], T2[MaxTree];
int main() {
    Tree R1,R2;
    
    R1 = BuildTree(T1);
    R2 = BuildTree(T2);
    if(Isomorphic(R1,R2))
        printf("Yes\n");
    prinf("No\n");
    
    return 0;
}
Tree BuildTree() {
    ...
    int N=0;
    scanf("%d\n", &N);
    if(N) {
        for(int i=0; i++)check[i]=0;
        for(int i=0; i<N; i++) {
            scanf("%c %c %c\n", &T[i].Element, &cl, &cr);
            if(cl!='-') {
                T[i].Left=cl-'0';
                check[T[i].Left]=1;
            } else
                T[i].Left = Null;
            if(cr!='-') {
                T[i].Right=cr-'0';
                check[T[i].Right]=1;
            } else
                T[i].Right = Null;
        }
        for(int i=0; i<N; i++) {
            if(!check[i]) break;
            Root = i;
        }
        return Root;
    }
}

int Isomorphic(Tree R1, Tree R2) {
        if((R1==Null)&&(R2==Null))
            return 1;
        if(((R1==Null)&&(R2!Null)) || ((R1!=Null)&&(R2==Null)))
            return 0;
        if(T1[R1].Element!=T2[R2].Element)
            return 0;
        if((T1[R1].Left==Null)&&(T2[R2].Left==Null))
            return Isomorphic(T1[R1].Right,T2[R2].Right);
    	if(((T1[R1].Left!=Null)&&(T2[R2].Left!=Null))&&
            ((T1[T1[R1].Left].Element)==(T2[T2[R2].Left].Element)))
            	return (Isomorphic(T1[R1].Left, T2[R2].Right)&&
                        Isomorphic(T1[R1].Right, T2[R2].Right));
    	else
	            return (Isomorphic(T1[R1].Left, T2[R2].Right)&&
                        Isomorphic(T1[R1].Right, T2[R2].Left))
}

二叉查找树

Position Find(ElementType X, BinTree BST) {
    if(!BST) return NULL;
    if(X > BST->Data) 
        return Find(X, BST->Right);
    else if(X < BST->Data)
        return Find(X, BST->Left);
    return BST;
}
Position IterFind(ElementType X, BinTree BST) {
    while(BST) {
        if(X > BST->Data)
            BST = BST->Right;
        else if(X < BST->Data)
            BST = BST->Left;
        else
	        retrun BST;
    }
    return NULL;
}
//最小值
Position FindMin(BinTree BST) {
    if(!BST) return NULL;
    if(!BST->Left)//左子树为空则返回递归
        return BST;
    return FindMin(BST->Left);
}
Position FindMin(BinTree BST) {
    if(BST) 
        while(BST->Left) BST = BST->Left;
    return BST;
}
//最大值
Position FindMax(BinTree BST) {
    if(!BST) return NULL;
    if(!BST->Right)
        return BST;
    return FindMax(BST->Right);
}
//插入
BinTree Insert(BinTree BST, ElementType X) {
    if(!BST) {
        BST = malloc(sizeof(struct TreeNode));
        BST->Data = X;
        BST->Right = BST->Left = 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(ElementType X, BinTree BST) {
    Position Tmp; 
}

平衡二叉树AVL

//RR
//LL
//LR
//RL

存储结构

顺序结构

• 非根节点的父节点：[i/2]
• 节点i的左节点：2i
• 节点i的右节点：2i+1

链式结构

typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode {
    ElementType Data;
    BinTree Left;
    BinTree Right;
}

满二叉树

完全二叉树

• 树转二叉树

哈夫曼树

图

哈希