树
树型结构是一类重要的非线性数据结构。树是n（n>=0）个结点的有限集。在任意一颗非空树中，有且仅有
一个特定的称为根的结点；当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1,T2,...,Tm，其中每一个
集合本身又是一棵树，并且称为根的子树。因此树的数据结构定义为：
#define ElemType char typedef struct BinTreeNode { ElemType data; BinTreeNode *leftChild; BinTreeNode *rightChild; }BinTreeNode; typedef struct BinTree { BinTreeNode *root; }BinTree;
在树型结构中可以进行以下操作：
void InitBinTree(BinTree *t); void CreateBinTree(BinTree *t); void CreateBinTree(BinTreeNode *&t); int Size(BinTree *t); int Size(BinTreeNode *t); int Height(BinTree *t); int Height(BinTreeNode *t); BinTreeNode* Find(BinTree *t, ElemType key); BinTreeNode* Find(BinTreeNode *t, ElemType key); BinTreeNode* LeftChild(BinTreeNode *t); BinTreeNode* RightChild(BinTreeNode *t); BinTreeNode* Parent(BinTree *t, ElemType key); BinTreeNode* Parent(BinTreeNode *t, ElemType key);bool Equal(BinTree *t1, BinTree *t2); bool Equal(BinTreeNode *t1, BinTreeNode *t2); void Copy(BinTree *t, BinTree *t1); void Copy(BinTreeNode *t, BinTreeNode *&t1); void ClearBinTree(BinTree *t); void ClearBinTree(BinTreeNode *&t);
上面声明的方法有：（1）初始化一个二叉树.（2）创建出二叉树.（3）求二叉树的结点个数.（4）求二叉树
的高度.（5）在一个二叉树中，查找出key值的结点，并返回其地址.（6）在二叉树中，求出该结点的左子树.(7)
在二叉树中，求出该结点的右子树.（8）在一个二叉树中，查找key值的结点的父结点，并返回地址.（9）比较两
个二叉树是否相等.（10）根据一个二叉树去复制出另一个二叉树.（11）清空一个二叉树.
将声明的方法进行实现有：
void InitBinTree(BinTree *t) { t->root = NULL; } void CreateBinTree(BinTree *t) { CreateBinTree(t->root); } void CreateBinTree(BinTreeNode *&t) { ElemType item; cin>>item; if(item == ‘#‘) t = NULL; else { t = (BinTreeNode*)malloc(sizeof(BinTreeNode)); assert(t != NULL); t->data = item; CreateBinTree(t->leftChild); CreateBinTree(t->rightChild); } } int Size(BinTree *t) { return Size(t->root); } int Size(BinTreeNode *t) { if(t == NULL) return 0; else return Size(t->leftChild) + Size(t->rightChild) + 1; } int Height(BinTree *t) { return Height(t->root); } int Height(BinTreeNode *t) { if(t == NULL) return 0; else { int left_height = Height(t->leftChild); int right_height = Height(t->rightChild); return (left_height > right_height ? left_height : right_height) + 1; } } BinTreeNode* Find(BinTree *t, ElemType key) { return Find(t->root, key); } BinTreeNode* Find(BinTreeNode *t, ElemType key) { if(t == NULL) return NULL; if(t->data == key) return t; BinTreeNode *r = Find(t->leftChild, key); if(r != NULL) return r; return Find(t->rightChild, key); } BinTreeNode* LeftChild(BinTreeNode *t) { if(t == NULL) return NULL; return t->leftChild; } BinTreeNode* RightChild(BinTreeNode *t) { if(t == NULL) return NULL; return t->rightChild; } BinTreeNode* Parent(BinTree *t, ElemType key) { return Parent(t->root, key); } BinTreeNode* Parent(BinTreeNode *t, ElemType key) { if(t==NULL || t->data==key) return NULL; BinTreeNode *p = Find(t, key); if(p == NULL) return NULL; if(t->leftChild==p || t->rightChild==p) return t; BinTreeNode *r = Parent(t->leftChild, key); if(r != NULL) return r; return Parent(t->rightChild, key); } bool Equal(BinTree *t1, BinTree *t2) { return Equal(t1->root, t2->root); } bool Equal(BinTreeNode *t1, BinTreeNode *t2) { if(t1==NULL && t2==NULL) return true; if(t1!=NULL && t2!=NULL && t1->data==t2->data && Equal(t1->leftChild,t2->leftChild) && Equal(t1->rightChild, t2->rightChild)) return true; else return false; } void Copy(BinTree *t, BinTree *t1) { Copy(t->root, t1->root); } void Copy(BinTreeNode *t, BinTreeNode *&t1) { if(t == NULL) t1 = NULL; else { t1 = (BinTreeNode*)malloc(sizeof(BinTreeNode)); assert(t1 != NULL); t1->data = t->data; Copy(t->leftChild, t1->leftChild); Copy(t->rightChild, t1->rightChild); } } void ClearBinTree(BinTree *t) { ClearBinTree(t->root); } void ClearBinTree(BinTreeNode *&t) { if(t != NULL) { ClearBinTree(t->leftChild); ClearBinTree(t->rightChild); free(t); t = NULL; } }
原文：https://www.cnblogs.com/XNQC1314/p/8893850.html