树 c++

树 基础 定义：

n个结点的有限集合，以一种层次结构关系建立。

基本概念: 1.内部概念：

结点的度：一个结点含有子树个数
树的度：最大的结点度
结点层次：根为第一层，其子节点为第二层。。。

2.对于树中树：

树高度、深度：树中结点最大层次
子树：

3.对于结点：

结点概念
根结点（Root）：有且仅有一个的最顶端结点
分支结点/内部节点：结点度不为0的结点
叶节点/终端节点：最下端结点（结点度==0）
结点关系：
父结点：结点的子节点
子结点：某个结点子树的根节点，是该节点的子节点
兄弟结点：
堂兄弟结点：
结点祖先：
子孙结点：

4.其他：

森林：m棵互不相交的树，组成森林

树基础表示: 例程图示

所有例程采用如下图示：

坐标从左到右，从下到上排列。

1.父结点表示

除根结点外，树每个节点有且只有一个父结点。所以将结点结构体定义为“数据+父结点”，把每个结点连续的存储到结构体数组中，父结点域指下标，没有父节点时，值为-1。

#include 
#include 
using namespace std;
#define MaxN 1024
template 

class treenode {
	public:
		T data;
		int parent;
		treenode() {}
		treenode(T Data, int c): data(Data), parent(c) {
		}
		//没写析构
};
template 

class tree {
	public:
		treenode *nodes;
		int root ;
		int n ;
		tree(): root(0), n(0) {
			nodes = new treenode[MaxN];
		}
		tree(int N): root(0), n(N) {
			nodes = new treenode[N];
		}
		//没写析构
};

int main() {
	tree Tree(8);

	treenode N =  treenode('a', -1);
	Tree.nodes[0] = N;
	treenode N1 =  treenode('b', 0);
	Tree.nodes[1] = N1;
	treenode N2 =  treenode('c', 0);
	Tree.nodes[2] = N2;
	treenode N3 =  treenode('d', 1);
	Tree.nodes[3] = N3;
	treenode N4 =  treenode('e', 2);
	Tree.nodes[4] = N4;
	treenode N5 =  treenode('f', 2);
	Tree.nodes[5] = N5;
	treenode N6 =  treenode('g', 3);
	Tree.nodes[6] = N6;
	treenode N7 =  treenode('h', 3);
	Tree.nodes[7] = N7;

	for	(int i = 7; i >= 0; i--) {
		int j = i;
		cout << Tree.nodes[j].data;
		while (Tree.nodes[j].parent >= 0) {
			j = Tree.nodes[j].parent;
			cout << Tree.nodes[j].data;
		}
		cout << endl;
	}
	return 0 ;
};

2.子结点表示

父结点表示缺点：无法知道父结点的子节点有哪些
修改结点结构体为“数据+子结点数量+子节点位置数组”

#include 
#include 
using namespace std;
template 

class Node {
	public:
		T data;
		int childnodes_size;
		int *childnodes;
		Node(T d, int N): data(d), childnodes_size(N) {

		}
		Node(T d, int N, int *num) {
			data = d;
			childnodes_size = N;
			childnodes = new int[N];
			memcpy(childnodes, num, sizeof(childnodes));
		}
		Node() {
		}
		//没写析构
};
template 

class tree {
	public:
		int Treesize;
		Node *Tree;

		tree(int Tn) {
			Treesize = Tn;
			Tree = new Node[Tn];
		}
		//没写析构

};

int main() {
	tree ATree(8);
	int arr[2] = {1, 2};
	Node p = Node('a', 2, arr);
	ATree.Tree[0] = p;
	int arr1[1] = {3};
	Node p1 = Node('b', 1, arr1);
	ATree.Tree[1] = p1;
	int arr2[2] = {4, 5};
	Node p2 = Node('c', 2, arr2);
	ATree.Tree[2] = p2;
	int arr3[3] = {6, 7};
	Node p3 = Node('d', 3, arr3);
	ATree.Tree[3] = p3;
	Node p4 = Node('e', 0);
	ATree.Tree[4] = p4;
	Node p5 = Node('f', 0);
	ATree.Tree[5] = p5;
	Node p6 = Node('g', 0);
	ATree.Tree[6] = p6;
	Node p7 = Node('h', 0);
	ATree.Tree[7] = p7;
	//如何遍历显示，需修改，这里只显示最左边
	int i = 0;
	while (ATree.Tree[i].childnodes_size > 0) {
		cout << ATree.Tree[i].data ;
		i = ATree.Tree[i].childnodes[0];
	}
	cout << ATree.Tree[i].data ;
	cout << endl;

	return 1;

}

3.左儿子右兄弟

结点结构体保存“数据+第一个孩子结点+第一个右兄弟结点”

#include 
using namespace std;

template 
class Node {
	public:
		T data;
		int child;
		int brother;
		Node() {
		}
		Node(T d): data(d) {
		}
		Node(T d, int l, int r): data(d), child(l), brother(r) {
		}
};

template 
class Tree {
	public:
		Node *tree;
		int tsize;
		Tree(int ts): tsize(ts) {
			tree = new Node[ts];
		}
};

int main() {
	Tree aTree = Tree(8);
	aTree.tree[0] = Node('a', 1, -1);
	aTree.tree[1] = Node('b', 3, 2);
	aTree.tree[2] = Node('c', 4, -1);
	aTree.tree[3] = Node('d', 6, -1);
	aTree.tree[4] = Node('e', -1, 5);
	aTree.tree[5] = Node('f', -1, -1);
	aTree.tree[6] = Node('g', -1, 7);
	aTree.tree[7] = Node('h', -1, -1);
	int i = 0;
	while (aTree.tree[i].child > 0) {
		cout << aTree.tree[i].data;
		i = aTree.tree[i].child;
	}
	cout << aTree.tree[i].data << endl;
	return 1;
}

树分类 二叉树 概念

树中不存在度大于2的结点。子树有顺序，分为左子树和右子树。

分类 1.斜树

结点只有左子树/只有右子树，类似链表或线性表。

2.满二叉树

所有根结点和内部结点都存在左右子树，非叶结点度为2，叶节点都在同一层。对于深度相同的二叉树，满二叉树具有最多节点数：2^h-1，结点总数为奇数。

3.完全二叉树

二叉树所有节点顺序按满二叉树顺序排列，为完全二叉树。此时叶子结点只能在最后两层，最下层位置在左连续，倒数第二层在右连续。某结点的度为1则该结点没有右子树。相同结点数二叉树，完全二叉树深度最小。

4.二叉排序树/二叉搜索树/二叉查找树（Binary Sort Tree）（没看）

1.若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2.若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
3.它的左、右子树也分别为二叉排序树

5.平衡二叉树（Balanced Binary Tree， AVL树）（没看）

它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。（注：平衡二叉树应该是一棵二叉排序树）

性质

性质1

第i层至多2^(i-1)个结点（左右都满的情况）；

性质2

深度为h的二叉树至多2^h-1个结点（满二叉树情况）；

性质3

对于任意树，如果其叶节点个数为m，度为2结点树为n，m=n+1;

推导：
设：结点数为0（叶节点）数：m，结点数为1数：l，结点数为2数：n，总结点数为sum，总边数为sum-1
对于边数有：

sum-1 = 2*n+l

对于结点数有

sum = m+n+l

联立：

m = n+1

性质4
拥有那个结点的完全二叉树深度为[log(n)]+1,[ ]向下取整，log以2为底。

存储 1.顺序表(程序待补)

对于完全二叉树和非完全二叉树：
顺序表按按满二叉树存储编号，下标从1起，对于下标index，其子结点为2index和2index+1。对于结点c_index，其父结点为[c_index/2]。
(chengxudaibu)

2.链表

对于稀疏二叉树，可采用链表存储。结点结构体保存“数据+左孩子+右孩子”

遍历

遍历指从根结点出发，按照某种顺序依次访问二叉树中所有结点，每个节点访问且只访问一次。
分为前序遍历、中序遍历、后序遍历和层序遍历。
例图：

1.前序遍历

从根节点开始，从左向右遍历，对于例图：
a->b->d->g->h->c->e->f

2.中序遍历

从左子树最左叶节点开始遍历
g->d->h->b->a->e->c->f

3.后序遍历

先递归后遍历左子树，再递归后遍历右子树，最后访问根节点
g->h->d->b->e->f->c->a

4.层序遍历（广度优先搜索，待补）

从第一层开始，从左到右遍历
a->b->c->d->e->f->g->h

例程：

#include 
using namespace std;

template 
class Node {
	public:
		T data;
		Node *lchild;
		Node *rchild;
		Node() {
		}
		Node(T d): data(d), lchild(NULL), rchild(NULL) {
		}
		Node(T d, Node *l, Node *r): data(d), lchild(l), rchild(r) {
		}
};

template 
class BiTree {
	public:
		Node *root;

		BiTree(Node *r): root(r) {
		};
		~BiTree() {
			release(root);
		}
		void PreOrder() {    //前序排列
			preorder(root);
			cout << endl;
		}
		void InOrder() {   //中序排列
			inorder(root);
			cout << endl;

		}
		void PostOrder() {   //后序排列
			postorder(root);
			cout << endl;
		}
	private:
		void release(Node *r) {
			if (r != NULL) {
				release(r->lchild);
				release(r->rchild);
				delete r;
			}
		}
		void preorder(Node *r) {

			if (r != NULL) {
				cout << r->data ;
				preorder(r->lchild);
				preorder(r->rchild);
			}
		}
		void inorder(Node *r) {
			if (r != NULL) {
				inorder(r->lchild);
				cout << r->data;
				inorder(r->rchild);
			}
		}
		void postorder(Node *r) {
			if (r != NULL) {
				postorder(r->lchild);
				postorder(r->rchild);
				cout << r->data;
			}
		}



};

int main() {
	//gouzaoshu
	Node *p8 = new Node('h');
	Node *p7 = new Node('g');
	Node *p6 = new Node('f');
	Node *p5 = new Node('e');
	Node *p4 = new Node('d', p7, p8);
	Node *p3 = new Node('c', p5, p6);
	Node *p2 = new Node('b', p4, NULL);
	Node *p1 = new Node('a', p2, p3);
	BiTree Atree = BiTree(p1);
	cout << "前序排列：" << endl;
	Atree.PreOrder();
	cout << "中序排列：" << endl;
	Atree.InOrder();
	cout << "后序排列：" << endl;
	Atree.PostOrder();
	return 1;
}

常用算法

1.递归
2.遍历
使用栈/队列实现递归
2.DFS/BFS