树,二叉树

树：（1：N）有且仅有一个根节点，且每一个节点由多棵子树组成，
        且子树之间互不相连

    节点的层：该节点有多少祖先(上面的树有三层)

    兄弟：同一层且同一父亲(就是共根节点的相邻节点)
    节点的度：节点的孩子数
    树的度：就是树的子节点中最大的度(上图树的度为 5 )
    叶子节点：度为0的节点(就是没有子节点的节点)

    二叉树：每个节点最多只能有2个子节点（左右孩子）
    形状：
        没有根节点：空树
        只有根节点：
        （2个节点：）只有一个左孩子 

   满二叉树：每一个节点的度为2，且叶子节点在同一层
       层为N的满二叉树的节点数为：2^n-1  (就是除了最后一层没有子节点,其他层都是有两个子节点的)

   完全二叉树：(就是满二叉树时 , 从右往左依次连续减去N 个节点 )
    遍历：前，中，后的规则
        前：先访问该树的根节点，再遍历左子树，再遍历右子树
        中：先遍历左子树，再访问根节点，再遍历右子树
        后：先遍历左子树，再遍历右子树，最后访问根节点

  

   将 普通树转为 二叉树 , 首先画出树 .

   把树转换为二叉树 .

   树的先序遍历 , 首先访问 

    P(根节点)

    L(左节点)

    R(右节点)

    如下图 : 首先访问节点 1 的根节点 , 访问了打勾 , 再访问节点 2 的根节点 , 访问了打勾 , 再重复访问 4 节点 , 然后访问 4 节点的 L 的 , 访问了打勾 , 再访问 R , 访问了打勾 , 再返回到 2 节点 , 因为 2 节点的 L 访问完了 , 打勾 , 再访问 2节点的右节点 .

   树的中序遍历 , 首先访问

   L(左节点)

   P(中节点)

   R(右节点)

   树的后序遍历 , 首先

   L(左节点)

   R(右节点)

   P(根节点)

 

郝斌老师的树的构造与遍历.

#include<iostream>
using namespace std;

//前置声明
class tree;
//节点:
class node
{
public:
	friend class tree;
	node(char);
protected:
	char data;//数据域
	node* lchild;//指向左孩子
	node* rchild;//指向右孩子
};

node::node(char d)
{
	this->data=d;
	this->lchild=NULL;
	this->rchild=NULL;
}

//树
class tree
{
public:
	tree();
	bool createTree(char*&,node*&);
	node* &getRoot();
	//遍历 先序 中序 后序
	//前序:
	void preOrder(node*);
	void inOrder(node*);
	void postOrder(node*);
	node* find(node*,char);
	bool alter(char,node*,char);
	node* match(char,node*);
protected:
	node* root;//根节点
};

tree::tree():root(NULL)
{
}

//前序遍历:每次只打印当前节点信息,
void tree::preOrder(node* ploc)
{
	if(ploc==NULL)
		return;
	//只打印ploc节点的信息
	cout<<ploc->data<<" ";
	//左子树的节点
	preOrder(ploc->lchild);
	preOrder(ploc->rchild);
}

//先序构造
bool tree::createTree(char* &d,node* &ploc)
{
	if('\0'==*d)
		return true;
//1.分配节点空间
	if('#'==*d)
		ploc=NULL;
	else
	{
		ploc=new node(*d);
		if(NULL==ploc)
			return false;
//2.修改指向域
	createTree(++d,ploc->lchild);
	createTree(++d,ploc->rchild);
	return true;
	}
}

void tree::postOrder(node* ploc)
{
	if(ploc==NULL)
		return;
	postOrder(ploc->lchild);
	postOrder(ploc->rchild);
	cout<<ploc->data<<" ";
}

void tree::inOrder(node* ploc)
{
	if(NULL==ploc)
		return;
	inOrder(ploc->lchild);
	cout<<ploc->data<<" ";
	inOrder(ploc->rchild);
}

node* &tree::getRoot()
{
	return this->root;
}

node* tree::find(node* ploc,char key)
{
	node* result=NULL;
	if(NULL==ploc)
		return NULL;
	if(ploc->data==key)
		return ploc;
	//左子树
	if(NULL!=(result=find(ploc->lchild,key)))
		return result;
	//右子树
	if(NULL!=(result=find(ploc->rchild,key)))
		return result;
}

node* tree::match(char key,node* ploc)
{
	node* result=NULL;
	if(NULL==ploc)
		return NULL;
	if(key==ploc->data)
		return ploc;
	result=match(key,ploc->lchild);
	if(result!=NULL)
		return result;
	return match(key,ploc->rchild);
}

int main()
{
	char* buf="a#bc##d##";
//实例化
	tree t;//构造器
	t.createTree(buf,t.getRoot());
	t.preOrder(t.getRoot());
	cout<<endl;
	t.inOrder(t.getRoot());
	cout<<endl;
	t.postOrder(t.getRoot());
	cout<<endl;
	
	if(NULL!=t.find(t.getRoot(),'a'))
		cout<<"查找成功"<<endl;
	else
		cout<<"查找失败"<<endl;

	if(NULL!=t.match('c',t.getRoot()))
		cout<<"查找成功"<<endl;
	else
		cout<<"查找失败"<<endl;
	
	//t.alter('c',t.getRoot(),'Y');
	//t.preOrder(t.getRoot());
	//cout<<endl;
}

 

   树的简单练习 :