数据结构 - 树基本知识

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

#define MAXTSIZE 100
#define OK 1
#define OVERFLOW -1
typedef char TElemType;
typedef int Status;

// 二叉树顺序存储
typedef TElemType SqBiTree[MAXTSIZE];
SqBiTree bt;


// 二叉树链式存储
typedef struct BiNode {
	TElemType data;
	// 左右孩子指针
	struct BiNode* lchild, * rchild;
}BiNode, * BiTree;

void visit(BiTree T) {
	cout << T->data << endl;
}

// 先序遍历 根左右
Status PreOrderTraverse(BiTree T) {
	if (T == NULL) return OK;
	else {
		visit(T);//访问根节点
		PreOrderTraverse(T->lchild);//递归遍历左子树
		PreOrderTraverse(T->rchild);//递归遍历右子树
	}
}

// 中序遍历 左根右
Status InOrderTraverse(BiTree T) {
	if (T == NULL) return OK;
	else {
		InOrderTraverse(T->lchild);
		visit(T);
		InOrderTraverse(T->rchild);
	}
}

// 后序遍历 左右根
Status PostOrderTraverse(BiTree T) {
	if (T == NULL) return OK;
	else {
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		visit(T);
	}
}

// 非递归中序遍历二叉树
Status InOrderTraverseStack(BiTree T) {
	BiTree p, q; stack s; p = T;
	while (p || !s.empty()) {
		if (p) { s.push(p); p = p->lchild;  }
		else {
			q = s.top();
			cout << p->data << endl;
			p = q->rchild;
		}
	}
	return OK;
}

// 层次遍历二叉树
void LevelOrder(BiTree b) {
	BiNode* p; queue qu;
	qu.push(b);
	while (!qu.empty()) {
		p = qu.front();
		cout << p->data << endl;
		qu.pop();
		if (p->lchild) qu.push(p->lchild);
		if (p->rchild) qu.push(p->rchild);
	}
	qu.pop();
}

// 建立二叉树
Status CreateBiTree(BiTree T) {
	char ch;
	cin >> ch;
	if (ch == '#') T = NULL;
	else {
		if (!(T = new BiNode)) return OVERFLOW;
		T->data = ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
	return OK;
}

// 复制二叉树
int Copy(BiTree T, BiTree &NewT) {
	if (T == NULL) return 0;
	else {
		NewT = new BiNode;
		NewT->data = T->data;
		Copy(T->lchild, NewT->lchild);
		Copy(T->rchild, NewT->rchild);
	}
}

// 二叉树深度
int m = 0, n = 0;
int deep(BiTree T) {
	if (T == NULL) return 0;
	else {
		m = deep(T->lchild);
		n = deep(T->rchild);
		if (m > n) return m + 1;
		else return n + 1;
	}
}

// 计算二叉树结点总数
int NodeCount(BiTree T) {
	if (T == NULL) return 0;
	else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}

// 计算二叉树叶子结点数
int LeadCount(BiTree T) {
	if (T == NULL) return 0;
	if (T->lchild == NULL && T->rchild == NULL) return 1;
	else return LeadCount(T->lchild) + LeadCount(T->rchild);
}

// 线索二叉树
typedef struct BiThrNode {
	int data;
	// 为0时指向左右孩子，为1时指向前驱后继结点
	int ltag, rtag;
	struct BiThrNode* lchild, * rchild;
}BithrNode, * BiThrTree;

// 树的存储结构

// 双亲表示法，找双亲容易找孩子难
typedef struct RTNode {
	TElemType data;
	int parent; // 双亲的位置
}PTNode;

#define MAX_TREE_SIZE 100
typedef struct {
	PTNode nodes[MAX_TREE_SIZE];
	int r, n; // 根结点的位置和结点个数
};

// 孩子链表表示法
typedef struct CTNode {
	int child;
	struct CTNode* next;
}*ChildPtr;

typedef struct {
	TElemType data;
	ChildPtr firstchild;// 孩子链表头指针
}CTBox;

typedef struct {
	CTBox nodes[MAX_TREE_SIZE];
	int n, r; // 结点数和根结点的位置
}CTree;

// 孩子兄弟表示法
typedef struct CSNode {
	TElemType data;
	struct CSNode* firstchild, * nextsibling;
}CSNode, *CSTree;



int main() {
	
 	return 0;
}
数据结构 - 树基本知识

C/C++/C#相关栏目本月热门文章
