第五章 树和二叉树

树是n个节点的有限集，或为空树，或为非空树，对于非空树有：

（1）有且仅有一个称之为根节点

（2）除了根节点其他节点可以分为互不相交的有限集，其中每个有限集本身又是一棵树，并称之为根的子树。

#include<iostream>
#include<stack>
using namespace std;
typedef struct TNode{
	ElemType data;
	struct TNode* lchild, * rchild;
}TNode,*T;
Status InitTree(T& tree) {
	tree = new TNode;
	if (!tree)
		return ERROR;
	tree->lchild = NULL;
	tree->rchild = NULL;
	return OK;
}
void CreateTree(T &tree) {
	ElemType data;
	cin >> data;
	if (data == -1)
		tree = NULL;
	else {
		tree = new TNode;
		tree->data = data;
		CreateTree(tree->lchild);
		CreateTree(tree->rchild);
	}
}
void InOrderTraverse(T tree) {
	if (tree) {
		InOrderTraverse(tree->lchild);
		cout << tree->data;
		InOrderTraverse(tree->rchild);
	}
}
void InOrderTraverseByStack(T tree) {
	stack<T>* stx = new stack<T>;
	while (!stx->empty() || tree) {
		if (tree) {
			stx->push(tree);
			tree = tree->lchild;
		}
		else {
			tree = stx->top();
			stx->pop();
			cout << tree->data;
			tree = tree->rchild;
		}
	}
}
void Copy(T tree, T& newTree) {
	if (tree) {
		newTree = new TNode;
		newTree->data = tree->data;
		Copy(tree->lchild, newTree->lchild);
		Copy(tree->rchild, newTree->rchild);
	}
	else {
		newTree = NULL;
	}
}
int Depth(T tree) {
	if (tree) {
		int depthLc = Depth(tree->lchild);
		int depthRc = Depth(tree->rchild);
		return 1 + (depthLc > depthRc ? depthLc:depthRc);
	}
	return 0;
}
int NodeCount(T tree) {
	if (tree) {
		return 1 + NodeCount(tree->lchild) + NodeCount(tree->rchild);
	}
	return 0;
}
int main(void) {
	//输入测试数据:1 2 3 -1 4 -1 -1 5 -1 -1 6 -1 7 -1 -1
	T tree;
	T p;
	InitTree(tree);
	CreateTree(tree);
	InOrderTraverse(tree);
	cout << endl;
	InOrderTraverseByStack(tree);
	cout << endl;
	Copy(tree, p);
	InOrderTraverse(p);
	cout << endl;
	cout << Depth(tree) << endl;
	cout << NodeCount(tree) << endl;
	return 0;
}

线索二叉树是用来保存递归遍历动态过程中才存在有关前驱和后继相关信息的手段。

#include<iostream>
using namespace std;
typedef struct TNode {
	ElemType data;
	struct TNode* lchild, * rchild;
	int lTag, rTag;
}TNode,*T;
T pre = NULL;
Status InitTree(T &tree) {
	tree = new TNode;
	if (!tree)
		return ERROR;
	tree->lchild = NULL;
	tree->rchild = NULL;
	return OK;
}
void CreateTree(T& tree) {
	ElemType data;
	cin >> data;
	if (data == -1)
		tree = NULL;
	else {
		tree = new TNode;
		tree->data = data;
		CreateTree(tree->lchild);
		CreateTree(tree->rchild);
	}
}
void InOrderTraverse(T tree) {
	if (tree) {
		InOrderTraverse(tree->lchild);
		cout << tree->data;
		InOrderTraverse(tree->rchild);
	}
}
void InitThreading(T tree) {
	if (tree) {
		InitThreading(tree->lchild);
		if (tree->lchild) {
			tree->lTag = 0;
		}
		else {
			tree->lchild = pre;
			tree->lTag = 1;
		}
		if (pre) {
			if (pre->rchild) {
				pre->rTag = 0;
			}
			else {
				pre->rchild = tree;
				pre->rTag = 1;
			}
		}
		pre = tree;
		InitThreading(tree->rchild);
	}
}
void TraverseThreading(T tree) {
	while (tree&&(!(tree->rTag == 1) || tree->rchild)) {
		while (tree->lTag == 0 && tree->lchild)tree = tree->lchild;
		cout << tree->data;
		while (tree->rTag == 1 && tree->rchild) {
			tree = tree->rchild;
			cout << tree->data;
		}
		tree = tree->rchild;
	}
}
int main(void) {
	T tree;
	//输入测试数据:1 2 3 -1 4 -1 -1 5 -1 -1 6 -1 7 -1 -1
	CreateTree(tree);
	InOrderTraverse(tree);
	cout << endl;
	InitThreading(tree);
	TraverseThreading(tree);
	return 0;
}

哈夫曼树是带权路径最短树，可以用于压缩算法，文件的编码和译码。

#define CODESIZE 10
#define MAX 65535
#include<iostream>
#include<iomanip>
using namespace std;

typedef struct huffmanNode {
	char sign;
	int weight;
	struct huffmanNode* lchild, * rchild, * parents;
	char* huffmancode;
}HNode,*HT;
void CreateHuffmanTree(HT*& ht,int n,char *signs,int *weights) {
	ht = new HT[n];
	for (int i = 0; i < n; i++) {
		ht[i] = new HNode;
		ht[i]->lchild = ht[i]->rchild = NULL;
		ht[i]->parents = NULL;
		ht[i]->weight = weights[i];
		ht[i]->sign = signs[i];
		ht[i]->huffmancode = NULL;
	}
	for (int k = 0; k < n - 1; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n-i-1; j++) {
				if (ht[j]->weight > ht[j + 1]->weight) {
					HT temp = ht[j];
					ht[j] = ht[j+1];
					ht[j+1] = temp;
				}
			}
		}
		//for (int i = 0; i < n; i++) {
		//	cout << ht[i]->weight << " ";
		//}
		//cout << endl;
		HT root = new HNode;
		root->parents = NULL;
		root->lchild = new HNode;
		root->rchild = new HNode;
		root->lchild->huffmancode = NULL;
		root->rchild->huffmancode = NULL;
		root->huffmancode = NULL;
		root->lchild->weight = ht[0]->weight;
		root->rchild->weight = ht[1]->weight;
		root->lchild->sign = ht[0]->sign;
		root->rchild->sign = ht[1]->sign;
		root->lchild->lchild = ht[0]->lchild;
		root->lchild->rchild = ht[0]->rchild;
		root->rchild->lchild = ht[1]->lchild;
		root->rchild->rchild = ht[1]->rchild;
		root->lchild->parents = root;
		root->rchild->parents = root;
		if(root->lchild->lchild)
			root->lchild->lchild->parents = root->lchild;
		if(root->lchild->rchild)
			root->lchild->rchild->parents = root->lchild;
		if(root->rchild->lchild)
			root->rchild->lchild->parents = root->rchild;
		if(root->rchild->rchild)
			root->rchild->rchild->parents = root->rchild;
		root->weight = root->lchild->weight + root->rchild->weight;
		root->sign = '#';
		ht[0] = root;
		ht[1]->weight = MAX;
		//for (int i = 0; i < n; i++) {
		//	cout << ht[i]->weight << " ";
		//}
		//cout << endl;
	}
}
void InOrderTraverse(HT ht) {
	if (ht) {
		cout << ht->sign << " " <<setw(6)<< ht->weight<<" ";
		if (ht->huffmancode) {
			cout << "code:";
			for (int i = 0; ht->huffmancode[i]; i++) {
				cout << ht->huffmancode[i];
			}
			cout << endl;
		}
		else cout << endl;
		InOrderTraverse(ht->lchild);
		InOrderTraverse(ht->rchild);
	}
}
void HuffmanCodeDriver(HT ht) {
	if (ht) {
		ht->huffmancode = new char[CODESIZE];
		for (int i = 0; i < CODESIZE; i++)ht->huffmancode[i] = '\0';
		if (ht->parents) {
			if (ht->parents->lchild == ht) {
				for (int i = 0; i < CODESIZE; i++) {
					ht->huffmancode[i] = ht->parents->huffmancode[i];
					if (ht->huffmancode[i] == '\0') {
						ht->huffmancode[i] = '0';
						break;
					}
				}
			}
			else {
				for (int i = 0; i < CODESIZE; i++) {
					ht->huffmancode[i] = ht->parents->huffmancode[i];
					if (ht->huffmancode[i] == '\0') {
						ht->huffmancode[i] = '1';
						break;
					}
				}
			}
		}
		HuffmanCodeDriver(ht->lchild);
		HuffmanCodeDriver(ht->rchild);
	}
}
int main(void) {
	char ch[] = { 'a','b','c','d','e','f','g' };
	int weight[] = { 5,2,3,3,8,9,1 };
	HT *ht;
	CreateHuffmanTree(ht, 7, ch, weight);
	HuffmanCodeDriver(ht[0]);
	InOrderTraverse(ht[0]);
	return 0;
}