Morph MORPH
SIGN IN SIGN UP
huihut / interview UNCLAIMED

📚 C/C++ 技术面试基础知识总结，包括语言、程序库、数据结构、算法、系统、网络、链接装载库等知识及面试经验、招聘、内推等信息。This repository is a summary of the basic knowledge of recruiting job seekers and beginners in the direction of C/C++ technology, including language, program library, data structure, algorithm, system, network, link loading library, interview experience, recruitment, recommendation, etc.

0 0 40 C++
Normal View History Raw
改进数据结构代码
2019-06-04 23:18:46 +08:00
#include <stdio.h>
#include <stdlib.h>
更新数据结构代码
2018-02-16 23:58:28 +08:00
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define SUCCESS 1
#define UNSUCCESS 0
#define dataNum 5
int i = 0;
int dep = 0;
char data[dataNum] = { 'A', 'B', 'C', 'D', 'E' };
typedef int Status;
typedef char TElemType;
改进数据结构代码
2019-06-04 23:18:46 +08:00
// 二叉树结构
更新数据结构代码
2018-02-16 23:58:28 +08:00
typedef struct BiTNode
{
改进数据结构代码
2019-06-04 23:18:46 +08:00
TElemType data;
struct BiTNode *lchild, *rchild;
更新数据结构代码
2018-02-16 23:58:28 +08:00
}BiTNode, *BiTree;
改进数据结构代码
2019-06-04 23:18:46 +08:00
// 初始化一个空树
更新数据结构代码
2018-02-16 23:58:28 +08:00
void InitBiTree(BiTree &T)
{
改进数据结构代码
2019-06-04 23:18:46 +08:00
T = NULL;
更新数据结构代码
2018-02-16 23:58:28 +08:00
}
改进数据结构代码
2019-06-04 23:18:46 +08:00
// 构建二叉树
更新数据结构代码
2018-02-16 23:58:28 +08:00
BiTree MakeBiTree(TElemType e, BiTree L, BiTree R)
{
改进数据结构代码
2019-06-04 23:18:46 +08:00
BiTree t;
t = (BiTree)malloc(sizeof(BiTNode));
if (NULL == t) return NULL;
t->data = e;
t->lchild = L;
t->rchild = R;
return t;
更新数据结构代码
2018-02-16 23:58:28 +08:00
}
改进数据结构代码
2019-06-04 23:18:46 +08:00
// 访问结点
更新数据结构代码
2018-02-16 23:58:28 +08:00
Status visit(TElemType e)
{
改进数据结构代码
2019-06-04 23:18:46 +08:00
printf("%c", e);
return OK;
更新数据结构代码
2018-02-16 23:58:28 +08:00
}
改进数据结构代码
2019-06-04 23:18:46 +08:00
// 对二叉树T求叶子结点数目
int Leaves(BiTree T)
更新数据结构代码
2018-02-16 23:58:28 +08:00
{
改进数据结构代码
2019-06-04 23:18:46 +08:00
int l = 0, r = 0;
if (NULL == T) return 0;
if (NULL == T->lchild && NULL == T->rchild) return 1;
// 求左子树叶子数目
l = Leaves(T->lchild);
// 求右子树叶子数目
r = Leaves(T->rchild);
// 组合
return r + l;
更新数据结构代码
2018-02-16 23:58:28 +08:00
}
改进数据结构代码
2019-06-04 23:18:46 +08:00
// 层次遍历：dep是个全局变量,高度
int depTraverse(BiTree T)
更新数据结构代码
2018-02-16 23:58:28 +08:00
{
改进数据结构代码
2019-06-04 23:18:46 +08:00
if (NULL == T) return ERROR;
更新数据结构代码
2018-02-16 23:58:28 +08:00
改进数据结构代码
2019-06-04 23:18:46 +08:00
dep = (depTraverse(T->lchild) > depTraverse(T->rchild)) ? depTraverse(T->lchild) : depTraverse(T->rchild);
更新数据结构代码
2018-02-16 23:58:28 +08:00
改进数据结构代码
2019-06-04 23:18:46 +08:00
return dep + 1;
更新数据结构代码
2018-02-16 23:58:28 +08:00
}
改进数据结构代码
2019-06-04 23:18:46 +08:00
// 高度遍历：lev是局部变量，层次
void levTraverse(BiTree T, Status(*visit)(TElemType e), int lev)
更新数据结构代码
2018-02-16 23:58:28 +08:00
{
改进数据结构代码
2019-06-04 23:18:46 +08:00
if (NULL == T) return;
visit(T->data);
printf("的层次是%d\n", lev);
更新数据结构代码
2018-02-16 23:58:28 +08:00
改进数据结构代码
2019-06-04 23:18:46 +08:00
levTraverse(T->lchild, visit, ++lev);
levTraverse(T->rchild, visit, lev);
更新数据结构代码
2018-02-16 23:58:28 +08:00
}
改进数据结构代码
2019-06-04 23:18:46 +08:00
// num是个全局变量
void InOrderTraverse(BiTree T, Status(*visit)(TElemType e), int &num)
更新数据结构代码
2018-02-16 23:58:28 +08:00
{
改进数据结构代码
2019-06-04 23:18:46 +08:00
if (NULL == T) return;
visit(T->data);
if (NULL == T->lchild && NULL == T->rchild) { printf("是叶子结点"); num++; }
else printf("不是叶子结点");
printf("\n");
InOrderTraverse(T->lchild, visit, num);
InOrderTraverse(T->rchild, visit, num);
更新数据结构代码
2018-02-16 23:58:28 +08:00
}
改进数据结构代码
2019-06-04 23:18:46 +08:00
// 二叉树判空
更新数据结构代码
2018-02-16 23:58:28 +08:00
Status BiTreeEmpty(BiTree T)
{
改进数据结构代码
2019-06-04 23:18:46 +08:00
if (NULL == T) return TRUE;
return FALSE;
更新数据结构代码
2018-02-16 23:58:28 +08:00
}
改进数据结构代码
2019-06-04 23:18:46 +08:00
// 打断二叉树：置空二叉树的左右子树
更新数据结构代码
2018-02-16 23:58:28 +08:00
Status BreakBiTree(BiTree &T, BiTree &L, BiTree &R)
{
改进数据结构代码
2019-06-04 23:18:46 +08:00
if (NULL == T) return ERROR;
L = T->lchild;
R = T->rchild;
T->lchild = NULL;
T->rchild = NULL;
return OK;
更新数据结构代码
2018-02-16 23:58:28 +08:00
}
改进数据结构代码
2019-06-04 23:18:46 +08:00
// 替换左子树
更新数据结构代码
2018-02-16 23:58:28 +08:00
Status ReplaceLeft(BiTree &T, BiTree &LT)
{
改进数据结构代码
2019-06-04 23:18:46 +08:00
BiTree temp;
if (NULL == T) return ERROR;
temp = T->lchild;
T->lchild = LT;
LT = temp;
return OK;
更新数据结构代码
2018-02-16 23:58:28 +08:00
}
改进数据结构代码
2019-06-04 23:18:46 +08:00
// 替换右子树
更新数据结构代码
2018-02-16 23:58:28 +08:00
Status ReplaceRight(BiTree &T, BiTree &RT)
{
改进数据结构代码
2019-06-04 23:18:46 +08:00
BiTree temp;
if (NULL == T) return ERROR;
temp = T->rchild;
T->rchild = RT;
RT = temp;
return OK;
更新数据结构代码
2018-02-16 23:58:28 +08:00
}
改进数据结构代码
2019-06-04 23:18:46 +08:00
// 合并二叉树
更新数据结构代码
2018-02-16 23:58:28 +08:00
void UnionBiTree(BiTree &Ttemp)
{
改进数据结构代码
2019-06-04 23:18:46 +08:00
BiTree L = NULL, R = NULL;
L = MakeBiTree(data[i++], NULL, NULL);
R = MakeBiTree(data[i++], NULL, NULL);
ReplaceLeft(Ttemp, L);
ReplaceRight(Ttemp, R);
更新数据结构代码
2018-02-16 23:58:28 +08:00
}
int main()
{
改进数据结构代码
2019-06-04 23:18:46 +08:00
BiTree T = NULL, Ttemp = NULL;
更新数据结构代码
2018-02-16 23:58:28 +08:00
改进数据结构代码
2019-06-04 23:18:46 +08:00
InitBiTree(T);
if (TRUE == BiTreeEmpty(T)) printf("初始化T为空\n");
else printf("初始化T不为空\n");
更新数据结构代码
2018-02-16 23:58:28 +08:00
改进数据结构代码
2019-06-04 23:18:46 +08:00
T = MakeBiTree(data[i++], NULL, NULL);
更新数据结构代码
2018-02-16 23:58:28 +08:00
改进数据结构代码
2019-06-04 23:18:46 +08:00
Ttemp = T;
UnionBiTree(Ttemp);
更新数据结构代码
2018-02-16 23:58:28 +08:00
改进数据结构代码
2019-06-04 23:18:46 +08:00
Ttemp = T->lchild;
UnionBiTree(Ttemp);
更新数据结构代码
2018-02-16 23:58:28 +08:00
改进数据结构代码
2019-06-04 23:18:46 +08:00
Status(*visit1)(TElemType);
visit1 = visit;
int num = 0;
InOrderTraverse(T, visit1, num);
printf("叶子结点是 %d\n", num);
更新数据结构代码
2018-02-16 23:58:28 +08:00
改进数据结构代码
2019-06-04 23:18:46 +08:00
printf("叶子结点是 %d\n", Leaves(T));
更新数据结构代码
2018-02-16 23:58:28 +08:00
改进数据结构代码
2019-06-04 23:18:46 +08:00
int lev = 1;
levTraverse(T, visit1, lev);
更新数据结构代码
2018-02-16 23:58:28 +08:00
改进数据结构代码
2019-06-04 23:18:46 +08:00
printf("高度是 %d\n", depTraverse(T));
更新数据结构代码
2018-02-16 23:58:28 +08:00
改进数据结构代码
2019-06-04 23:18:46 +08:00
getchar();
return 0;
更新数据结构代码
2018-02-16 23:58:28 +08:00
}
Reference in New Issue Copy Permalink