数据结构之——树

Created in November 14, 2015

2015   ·   datastructure

一.简介 （资料来自维基百科）

screenshot

译：在计算机科学中，树形结构是被广泛使用的抽象数据结构或数据实现此ADT模拟的分层树结构，它是具有根值，和孩子的子树的父节点，表示一组连接的节点。

百度解释：

树状图是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树

树的图示：

 <p align="center"> screenshot </p>

二.专业词汇

 <p align="center"> screenshot </p>

可以不必像以上描述的这么复杂，其实就只关注，节点，度，根节点，叶子节点，孩子节点，父节点就可以了。

三.树的抽象数据类型

template <class Type> class Tree {
public:
    Tree ( );	 //树的构造函数		   
    ~Tree ( );   //析构函数
    position Root ( );  //跟的位置
    BuildRoot ( const Type& value ); //创建根
    position FirstChild ( position p ); //第一个孩子的位置
    position NextSibling ( position p, position v );  //旁边的兄弟节点
    position Parent ( position p );//父节点
    Type Retrieve ( position p );
    position InsertChild ( const position p,const Type &value );//插入节点
    position DeleteChild ( position p, int i );//删除节点
    void DeleteSubTree ( position t );//删除子树
    int IsEmpty ( );//判断是否为空
};

四.二叉树

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。

一个父节点只有左右两个孩子

screenshot

一个倒二叉树族谱（图片来自维基百科）

screenshot

由图可知，二叉树是相对稳定的树形结构。

五.二叉树的一些属性

screenshot

译:二叉树的性质

1.高度为h（h由0开始）的满二叉树，至少有n=2h+1个节点，最多有2^(h+1)-1个节点

2.一棵完整的二叉树，叶子节点的个数l = (n+1)/2,因为非叶子节点n-l = 2^log(l) -1=l-1。所以一棵完整的二叉树的叶子节点数十(n+1)/2的。叶子节点也称为度为0的节点，没有子节点。

3.一棵完整的平衡二叉树中，树的高度h=log（n+1） ，由第一个性质可以推得

4.在一棵完整的二叉树中，l=2^h 因此 n = 2^(h+1)-1(由性质2可得)

5.在一棵完整的二叉树中，没有孩子的节点最多有（n+1），其中只有一个节点是从最底层到最左边。

6.度数为0的节点 N0 = N2 +1

六.二叉树的ADT

#ifndef _BINTREE_H__
#define _BINTREE_H__
#include <fstream>

using namespace std;

class BinTreeNode{   //树节点的ADT
   public:
     BinTreeNode(int item,BinTreeNode<int>*left=NULL,BinTreeNode<int>right=NULL):data(item),leftChild(left),rightChild(right){}
     ~BinTreeNode();
     int & GetData()const{return data;}   //
     BinTreeNode<int>*GetLeft()const{return leftChild;}   //返回左右孩子节点
     BinTreeNode<int>*GetRight()const{return rightChild;}
     void SetData(const int & item){data = item;}      //得到左右孩子节点的数据
     void SetLeft(const int & item){leftChild = item;}
     void SetRight(const int & item){rightChild = item;}
   private:  
     BinTreeNode<int>*leftChild;
     BinTreeNode<int>*rightChild;
     int data;
};

class BinTree{
   friend class BinTreeNode; //将树节点的类作为树的友元
   public:
     BinTree(int value):RefValue(value),root(NULL){}
     virtual~BinTree(destroy(root);); //运用类里面的一个接口
     virtual int IsEmpty(return root == NULL?NULL 1:0;)
     virtual BinTreeNode<int>*Parent(BinTreeNode<int>*current){root == NULL || root == current? NULL : Parent(root,current);}//这一句待会再分析一下
     virtual BinTreeNode<int>*LeftChild(BinTreeNode<int>*current){return root!= NULL?current->leftChild:NULL}
     virtual BinTreeNode<int>*RightChild(BinTreeNode<int>*current){return root!=NULL?current->leftChild:NULL}
     int insert(const BinTreeNode<int>* &current)
     int find(const BinTreeNode<int>* current)const
     friend istream &operator >> (istream & in, BinTree<int> &Tree )//重载输入操作    //重载需要复习
     friend ostream &operator << ( ostream&out, BinTree<int> &Tree )//重载输出操作

     void Travese(BinTreeNode<int>*current,ostream & out)const 
     virtual BinTreeNode<int>* GetRoot(){return root;}
   private:
     BinTreeNode<int>*Parent( //有待分析
           BinTreeNode <int> *start,
           BinTreeNode <int> *current);
     void destroy(BinTreeNode<int>* current)
     BinTreeNode<int>* root;
     int RefValue;
};

七.简单的二叉树基本算法

#ifndef _BINTREE_H__
#define _BINTREE_H__
using namespace std;

class BinTree{
private:
	struct tree_node  //it can name the struct on the head without name it in the tail
	{
		tree_node* left;
		tree_node* right;
		int data;
	};
	tree_node* root;
public:
	BinTree()
	{
		root = NULL; //Don't forget The constructor!It's Gonna kill the code
	}
	void Insert(int);
	//int nodes();
	bool IsEmpty(){ return root == NULL; }
	void print_Preorder();
	void Preorder(tree_node *);
	bool Search(int);
	void Remove(int);
};

void BinTree::Insert(int d){
	tree_node * t = new tree_node;
	tree_node * parent = NULL;
	t->data = d;
	t->left = NULL;
	t->right = NULL;

	if (IsEmpty()){
		root = t;
	}
	
	else{
		tree_node * curr;
		curr = root;
		while (curr){
			parent = curr;   //notice the importance of parents! curr is an temp..when it reach null,but parent is still it's parent 
			if (t->data > curr->data) curr = curr->right;
			else curr = curr->left;
		}
		if (parent->data > t->data)
			parent->left = t;
		else
			parent->right = t;
	}
}

void BinTree::print_Preorder()
{
	Preorder(root);
}

void BinTree::Preorder(tree_node* p)//avoid inputing tree_node*p in main ,so i add an print_inorder!
{
	if (p != NULL)
	{
		
		cout << " " << p->data << " ";
		if (p->left) Preorder(p->left);
		if (p->right) Preorder(p->right);
	}
	else return;
}

bool BinTree::Search(int d)
{
	bool found = false;
	if (IsEmpty())
	{
		cout << " This Tree is empty! " << endl;
		return false;
	}
	tree_node* curr;
	tree_node* parent;
	curr = root;
	parent = (tree_node*)NULL;
	while (curr != NULL)
	{
		if (curr->data == d)
		{
			found = true;
			break;
		}
		else
		{
			parent = curr;//notice the importance of parents! curr is an temp..when it reach null,but parent is still it's parent .
			if (d>curr->data) curr = curr->right;//Also it can help to understand
			else curr = curr->left;
		}
	}
	if (!found)
	{
		cout << " Data not found! " << endl;
	}
	else
	{
		cout << " Data found! " << endl;
	}

	return found;
}

void BinTree::Remove(int d)
{
	bool found = false;
	if (IsEmpty())
	{
		cout << " This Tree is empty! " << endl;
		return;
	}
	tree_node* curr;
	tree_node* parent;
	curr = root;
	parent = NULL;
	while (curr != NULL)
	{
		if (curr->data == d)
		{
			found = true;
			break;
		}
		else
		{
			parent = curr;
			if (d>curr->data) curr = curr->right;//l
			else curr = curr->left;
		}
	}
	if (!found)
	{
		cout << " Data not found! " << endl;
		return;
	}

	// Node with single child
	if ((curr->left == NULL && curr->right != NULL) || (curr->left != NULL
		&& curr->right == NULL))
	{
		if (curr->left == NULL && curr->right != NULL)
		{
			if (parent->left == curr)
			{
				parent->left = curr->right;
				delete curr;
			}
			else
			{
				parent->right = curr->right;
				delete curr;
			}
		}
		else // left child present, no right child
		{
			if (parent->left == curr)
			{
				parent->left = curr->left;
				delete curr;
			}
			else
			{
				parent->right = curr->left;
				delete curr;
			}
		}
		return;
	}

	//We're looking at a leaf node
	if (curr->left == NULL && curr->right == NULL)
	{
		if (parent == NULL)
		{
			delete curr;

		}
		else
		if (parent->left == curr) parent->left = NULL;
		else parent->right = NULL;
		delete curr;
		return;
	}

	//Node with 2 children
	// replace node with smallest value in right subtree
	if (curr->left != NULL && curr->right != NULL)
	{
		tree_node* chkr;
		chkr = curr->right;
		if ((chkr->left == NULL) && (chkr->right == NULL))
		{
			curr = chkr;
			delete chkr;
			curr->right = NULL;
		}
		else // right child has children
		{
			//if the node's right child has a left child
			// Move all the way down left to locate smallest element

			if ((curr->right)->left != NULL)
			{
				tree_node* lcurr;
				tree_node* lcurrp;
				lcurrp = curr->right;
				lcurr = (curr->right)->left;
				while (lcurr->left != NULL)
				{
					lcurrp = lcurr;
					lcurr = lcurr->left;
				}
				curr->data = lcurr->data;
				delete lcurr;
				lcurrp->left = NULL;
			}
			else
			{
				tree_node* tmp;
				tmp = curr->right;
				curr->data = tmp->data;
				curr->right = tmp->right;
				delete tmp;
			}

		}
		return;
	}

}
#endif

只有Remove稍微难一点，其他都是如出一辙。



    Enjoy Reading This Article?

    Here are some more articles you might like to read next:

  • What is Mathematics: Solution Chapter 3
  • What is Mathematics: Solution Chapter 2
  • What is Mathematics: Solution Chapter 1
  • A small guide to supplements: What you need to know
  • 混乱与秩序