二叉树是一种树形结构, 它的特点是每个每个结点至多有两棵子树, 二叉树有左, 右子树之分, 且左, 右子树不能颠倒. 二叉树及其变体树形结构在实际编程中使用的非常多, 如: 哈弗曼树, 线索二叉树, 红黑树等.
1. 基本概念
树是 n(n>=0)个结点的有限集合. 在任意一个非空树中:
(1)有且仅有一个结点为根结点.
(2)当 n>1 时, 其余结点可分为 m(m>0)个互不相交的有限集 T1,T2......Tm, 其中每一个集合本身又是一棵树, 并且成为根的子树.
结点拥有的子树数称为结点的度.
度为 0 的结点称为叶子或终端结点.
度不为 0 的结点称为非终端结点或分支结点.
树的度是树内结点度的最大值.
结点的子树称为结点的孩子.
该结点称为孩子的双亲.
同一个双亲之间的孩子称为兄弟.
根结点称为祖先.
除祖先外所有结点称为子孙.
树的层, 结点的屡次从根开始定义起, 根为第一层, 根的孩子为第二层, 以此类推.
树中的最大层数称为树的深度.
如果将树中结点的各子树看成从左到右是有次序的(不能互换), 则称该树为有序树, 否则称为无序树.
二叉树是另一种树形结构, 它的特点是每个每个结点至多有两棵子树, 二叉树有左, 右子树之分, 且左, 右子树不能颠倒.
森林是 m(m>=0)棵的互不相交的树的集合. 对树中每个结点而言, 其子树的集合为森林.
- /*****************************************************************************************************
- *Copyright: Yue Workstation
- *
- *FileName: BinTree.h
- *
- *Function: 二叉树数据结构定义
- *
- *Author: Abel Lee
- *
- *CreateOn: 2012-2-19
- *
- *Log: 2012-2-19 由 Abel Lee 创建
- *****************************************************************************************************/
- #ifndef BIN_TREE_H
- #define BIN_TREE_H
- #include "global.h"
- #define STACK_INCREMENT 2 // 栈存储空间分配增量
- typedef struct Node
- {
- int data;
- struct Node *left_child;
- struct Node *right_child;
- int flag;// 专门用于二叉树后序遍历
- }BiTNode,*BiTree;
- typedef struct Stack
- {
- BiTNode *base;
- BiTNode *top;
- int stack_size;
- }Stack;
- int InitBinaryTree(BiTree *T);
- int PreviousCreateTree(BiTree *T);
- int MiddleCreateTree(BiTree *T);
- int RearCreateTree(BiTree *T);
- void PreviousPrintTree(BiTree T);
- void MiddlePrintTree(BiTree T);
- void RearPrintTree(BiTree T);
- int BinInitStack(Stack *s);
- int BinPush(Stack *s,BiTNode e);
- int BinPop(Stack *s,BiTNode **e);
- int IsNotEmptyStack(Stack *s);
- int BinGetTop(Stack *s,BiTNode **e);
- int NotRecursionPreviousPrintTree(BiTree T);
- int NotRecursionMiddlePrintTree(BiTree T);
- int NotRecursionRearPrintTree(BiTree T);
- int LevelPrintTree(BiTree T);
- int BinaryTreeIsEmpty(BiTree T);
- int BinaryTreeDepth(BiTree T);
- int GetRoot(BiTree T);
- int Value(BiTree p);
- void Assign(BiTree p,int value);
- int GetParentNode(BiTree T, int e);
- int ChangeNode(BiTree T,int e,int v);
- int GetNoteLeftChild(BiTree T, int e);
- int GetNoteRightChild(BiTree T, int e);
- int GetLeftBrother(BiTree T, int e);
- int GetRightBrother(BiTree T, int e);
- int InsertChild(BiTree *T, int e, int v,int LR);
- int DestroyBinaryTree(BiTree *T);
- int DeleteChildTree(BiTree *T, int e);
- #endif
- /*****************************************************************************************************
- *Copyright:Yue Workstation
- *
- *FileName: BinTree.c
- *
- *Function: 二叉树操作
- *
- *Author:Abel Lee
- *
- *CreateOn:2012-2-19
- *
- *Log:2011-5-3 由 Abel Lee 创建
- *****************************************************************************************************/
- #include "../inc/BinTree.h"
- /****************************************************************************************************
- *Function Name: InitBinaryTree
- *
- *Function: 初始化二叉树
- *
- *Parameter: T: 二叉树头指针
- *
- *Return Value: 成功返回 0, 失败返回 - 1
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int InitBinaryTree(BiTree *T)
- {
- *T = (BiTree)malloc(sizeof(BiTNode));
- if(*T)
- {
- return 0;
- }
- else
- {
- return -1;
- }
- }
- /****************************************************************************************************
- *Function Name: PreviousCreateTree
- *
- *Function: 先序创建一个二叉树
- *
- *Parameter: T: 二叉树头指针
- *
- *Return Value: 成功返回 0
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int PreviousCreateTree(BiTree *T)
- {
- int ch;
- scanf("%d",&ch);
- if(ch == 0)
- {
- (*T) = NULL;
- }
- else
- {
- (*T) = (BiTree)malloc(sizeof(BiTNode));
- (*T)->data = ch;
- PreviousCreateTree(&((*T)->left_child));
- PreviousCreateTree(&((*T)->right_child));
- }
- return 0;
- }
- /****************************************************************************************************
- *Function Name: MiddleCreateTree
- *
- *Function: 中序建立一个二叉树
- *
- *Parameter: T: 二叉树头指针
- *
- *Return Value: 成功返回 0
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int MiddleCreateTree(BiTree *T)
- {
- int ch;
- scanf("%d",&ch);
- if(ch == 0)
- {
- (*T) = NULL;
- }
- else
- {
- (*T) = (BiTree)malloc(sizeof(BiTNode));
- MiddleCreateTree(&((*T)->left_child));
- (*T)->data = ch;
- MiddleCreateTree(&((*T)->right_child));
- }
- return 0;
- }
- /****************************************************************************************************
- *Function Name: RearCreateTree
- *
- *Function: 后序建立一个二叉树
- *
- *Parameter: T: 二叉树头指针
- *
- *Return Value: 成功返回 0
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int RearCreateTree(BiTree *T)
- {
- int ch;
- scanf("%d",&ch);
- if(ch == 0)
- {
- (*T) = NULL;
- }
- else
- {
- (*T) = (BiTree)malloc(sizeof(BiTNode));
- RearCreateTree(&((*T)->left_child));
- RearCreateTree(&((*T)->right_child));
- (*T)->data = ch;
- }
- return 0;
- }
- /****************************************************************************************************
- *Function Name: PreviousPrintTree
- *
- *Function: 先序遍历二叉树
- *
- *Parameter: T: 二叉树头
- *
- *Return Value: 无
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- void PreviousPrintTree(BiTree T)
- {
- if(T)
- {
- printf("%d",T->data);
- PreviousPrintTree(T->left_child);
- PreviousPrintTree(T->right_child);
- }
- }
- /****************************************************************************************************
- *Function Name: MiddlePrintTree
- *
- *Function: 中序遍历二叉树
- *
- *Parameter: T: 二叉树头
- *
- *Return Value: 无
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- void MiddlePrintTree(BiTree T)
- {
- if(T)
- {
- MiddlePrintTree(T->left_child);
- printf("%d",T->data);
- MiddlePrintTree(T->right_child);
- }
- }
- /****************************************************************************************************
- *Function Name: RearPrintTree
- *
- *Function: 后序遍历二叉树
- *
- *Parameter: T: 二叉树头
- *
- *Return Value: 无
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- void RearPrintTree(BiTree T)
- {
- if(T)
- {
- RearPrintTree(T->left_child);
- RearPrintTree(T->right_child);
- printf("%d",T->data);
- }
- }
- /****************************************************************************************************
- *Function Name: BinInitStack
- *
- *Function: 初始化一个栈
- *
- *Parameter: s: 栈指针
- *
- *Return Value: 成功返回 0, 失败返回 - 1
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int BinInitStack(Stack *s)
- {
- s->base = (BiTree)malloc(STACK_INIT_SIZE * sizeof(BiTNode));
- if(!s->base)
- {
- perror("Init stack error,malloc have a error message.");
- return -1;
- }
- s->top = s->base;
- s->stack_size = STACK_INIT_SIZE;
- return 0;
- }
- /****************************************************************************************************
- *Function Name: BinPush
- *
- *Function: 入栈
- *
- *Parameter: s: 栈指针
- * e: 入栈元素
- *
- *Return Value: 成功返回 0, 失败返回 - 1
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int BinPush(Stack *s,BiTNode e)
- {
- if(s->top>= s->base + s->stack_size)
- {
- s->base = (BiTree)realloc(s->base,(STACK_INIT_SIZE + STACK_INCREMENT) * sizeof(BiTNode));
- if(!s->base)
- {
- perror("Init stack error,realloc have a error message.");
- return -1;
- }
- s->stack_size += STACK_INCREMENT;
- }
- *(s->top) = e;
- s->top++;
- return 0;
- }
- /****************************************************************************************************
- *Function Name: BinPop
- *
- *Function: 出栈
- *
- *Parameter: s: 栈指针
- * e: 保存出栈元素
- *
- *Return Value: 成功返回 0, 失败返回 - 1
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int BinPop(Stack *s,BiTNode **e)
- {
- if(s->top != s->base)
- {
- s->top--;
- *e = s->top;
- return 0;
- }
- else
- {
- return -1;
- }
- }
- /****************************************************************************************************
- *Function Name: IsNotEmptyStack
- *
- *Function: 栈是否为空
- *
- *Parameter: s: 栈指针
- *
- *Return Value: 为空返回 0, 不空返回 1
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int IsNotEmptyStack(Stack *s)
- {
- if(s->top == s->base)
- {
- return 0;
- }
- else
- {
- return 1;
- }
- }
- /****************************************************************************************************
- *Function Name: BinGetTop
- *
- *Function: 获取栈顶元素
- *
- *Parameter: s: 栈指针
- * e: 保存出栈元素
- *
- *Return Value: 成功返回 0, 失败返回 - 1
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int BinGetTop(Stack *s,BiTNode **e)
- {
- Stack *temp = s;
- if(!IsNotEmptyStack(s))
- {
- perror("That is a empty stack!");
- return -1;
- }
- temp->top--;
- *e = temp->top;
- return 0;
- }
- /****************************************************************************************************
- *Function Name: NotRecursionPreviousPrintTree
- *
- *Function: 栈的非递归先序遍历二叉树
- *
- *Parameter: T: 二叉树头
- *
- *Return Value: 成功返回 0
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int NotRecursionPreviousPrintTree(BiTree T)
- {
- Stack new_stack;
- BiTree p = T;
- BinInitStack(&new_stack);
- while(p || IsNotEmptyStack(&new_stack))
- {
- while(p)
- {
- printf("%d",p->data);
- BinPush(&new_stack,*p);
- p = p->left_child;
- }
- if(IsNotEmptyStack(&new_stack))
- {
- BinPop(&new_stack,&p);
- p = p->right_child;
- }
- }
- return 0;
- }
- /****************************************************************************************************
- *Function Name: NotRecursionMiddlePrintTree
- *
- *Function: 栈的非递归中序遍历二叉树
- *
- *Parameter: T: 二叉树头
- *
- *Return Value: 成功返回 0
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int NotRecursionMiddlePrintTree(BiTree T)
- {
- Stack new_stack;
- BiTree p = T;
- BinInitStack(&new_stack);
- while(p || IsNotEmptyStack(&new_stack))
- {
- while(p)
- {
- BinPush(&new_stack,*p);
- p = p->left_child;
- }
- if(IsNotEmptyStack(&new_stack))
- {
- BinPop(&new_stack,&p);
- printf("%d",p->data);
- p = p->right_child;
- }
- }
- return 0;
- }
- /****************************************************************************************************
- *Function Name: NotRecursionRearPrintTree
- *
- *Function: 栈的非递归后序遍历二叉树
- *
- *Parameter: T: 二叉树头
- *
- *Return Value: 成功返回 0
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int NotRecursionRearPrintTree(BiTree T)
- {/*
- Stack new_stack;
- BiTree p = T;
- BiTree q;
- InitStack(&new_stack);
- do
- {
- while(p)
- {
- if(p->flag != 2)
- {
- if(p->flag !=1 )
- {
- p->flag = 1;
- Push(&new_stack, *p);
- }
- if(p->left_child && p->left_child->flag != 2)
- {
- q = p;
- p = p->left_child;
- }
- else if(p->right_child && p->right_child->flag != 2)
- {
- q = p;
- p = p->right_child;
- }
- else
- {
- break;
- }
- }
- else
- {
- break;
- }
- }
- if (IsNotEmptyStack(&new_stack))
- {
- Pop(&new_stack,&q);
- if(p->flag == 1)
- {
- p->flag = 2;
- printf("%d",p->data);
- p = q;
- }
- }
- else
- {
- break;
- }
- }while(p || IsNotEmptyStack(&new_stack));
- */
- return 0;
- }
- /****************************************************************************************************
- *Function Name: LevelPrintTree
- *
- *Function: 层次遍历二叉树
- *
- *Parameter: T: 二叉树头
- *
- *Return Value: 成功返回 0
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int LevelPrintTree(BiTree T)
- {
- BiTree Q[MAX_LENGTH];
- int front = 0,rear = 0;
- BiTree p;
- if(T)
- {
- Q[rear] = T;
- rear = (rear + 1)%MAX_LENGTH;
- }
- while(front != rear)
- {
- p = Q[front];// 队头元素出队
- front = (front + 1)%MAX_LENGTH;
- printf("%d",p->data);
- if(p->left_child)
- {
- Q[rear] = p->left_child;
- rear = (rear + 1)%MAX_LENGTH;
- }
- if(p->right_child)
- {
- Q[rear] = p->right_child;
- rear = (rear + 1)%MAX_LENGTH;
- }
- }
- return 0;
- }
- /****************************************************************************************************
- *Function Name: BinaryTreeIsEmpty
- *
- *Function: 判断二叉树是否为空
- *
- *Parameter: 二叉树头
- *
- *Return Value: 为空返回 0, 不空返回 1
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int BinaryTreeIsEmpty(BiTree T)
- {
- if(T)
- {
- return 1;
- }
- else
- {
- return 0;
- }
- }
- /****************************************************************************************************
- *Function Name: BinaryTreeDepth
- *
- *Function: 求二叉树的深度
- *
- *Parameter: T: 二叉树头
- *
- *Return Value: 返回二叉树深度值
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int BinaryTreeDepth(BiTree T)
- {
- int left = 0;
- int right = 0;
- if(!T)
- {
- return 0;
- }
- if(T->left_child)
- {
- left = BinaryTreeDepth(T->left_child);
- }
- else
- {
- left = 0;
- }
- if(T->right_child)
- {
- right = BinaryTreeDepth(T->right_child);
- }
- else
- {
- right = 0;
- }
- return left> right ? (left+1):(right+1);
- }
- /****************************************************************************************************
- *Function Name: GetRoot
- *
- *Function: 返回二叉树根结点
- *
- *Parameter: T: 二叉树头
- *
- *Return Value: 成功返回头数据, 失败返回 - 1
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int GetRoot(BiTree T)
- {
- if(T)
- {
- return T->data;
- }
- else
- {
- return -1;
- }
- }
- /****************************************************************************************************
- *Function Name: Value
- *
- *Function: 返回二叉树某节点的值
- *
- *Parameter: T: 二叉树头
- *
- *Return Value: 返回二叉树结点保存的值
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int Value(BiTree p)
- {
- return p->data;
- }
- /****************************************************************************************************
- *Function Name: Assign
- *
- *Function: 为某个节点分配值
- *
- *Parameter: p: 二叉树头
- * value: 要分配的值
- *
- *Return Value: 无
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- void Assign(BiTree p,int value)
- {
- p->data = value;
- }
- /****************************************************************************************************
- *Function Name: GetParentNode
- *
- *Function: 若 e 是非根结点, 返回他的双亲
- *
- *Parameter: T: 二叉树头
- * e: 结点值
- *
- *Return Value: 成功返回 0
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int GetParentNode(BiTree T, int e)
- {
- if((T->left_child && T->left_child->data == e) || (T->right_child && T->right_child->data == e))
- {
- return T->data;
- }
- else
- {
- if(T->left_child)
- {
- return GetParentNode(T->left_child, e);
- }
- if(T->right_child)
- {
- return GetParentNode(T->right_child, e);
- }
- }
- return 0;
- }
- /****************************************************************************************************
- *Function Name: ChangeNode
- *
- *Function: 如果 T 中存在 e, 则将 e 改为 v
- *
- *Parameter: T: 二叉树头
- * e: 被该数据
- * v: 修改后的数据
- *
- *Return Value: 成功返回 0, 失败返回 - 1
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int ChangeNode(BiTree T,int e,int v)
- {
- if(T->data == e)
- {
- T->data = v;
- }
- else
- {
- if(T->left_child)
- {
- ChangeNode(T->left_child,e,v);
- return 0;
- }
- if(T->right_child)
- {
- ChangeNode(T->right_child,e,v);
- return 0;
- }
- }
- return -1;
- }
- /****************************************************************************************************
- *Function Name: GetNoteLeftChild
- *
- *Function: 如果二叉树中存在 e 则返回其左孩子
- *
- *Parameter: T: 二叉树头
- * e: 结点值
- *
- *Return Value: 成功返回 0
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int GetNoteLeftChild(BiTree T, int e)
- {
- if(T->data == e)
- {
- if(T->left_child)
- {
- return T->left_child->data;
- }
- else
- {
- return 0;
- }
- }
- else
- {
- if(T->left_child)
- {
- return GetNoteLeftChild(T->left_child,e);
- }
- else
- {
- return 0;
- }
- if(T->right_child)
- {
- return GetNoteLeftChild(T->right_child,e);
- }
- {
- return 0;
- }
- }
- }
- /****************************************************************************************************
- *Function Name: GetNoteRightChild
- *
- *Function: 如果二叉树中存在 e 则返回其右孩子
- *
- *Parameter: T: 二叉树头
- * e: 结点值
- *
- *Return Value: 成功返回 0
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int GetNoteRightChild(BiTree T, int e)
- {
- if(T->data == e)
- {
- if(T->right_child)
- {
- return T->right_child->data;
- }
- else
- {
- return 0;
- }
- }
- else
- {
- if(T->left_child)
- {
- return GetNoteRightChild(T->left_child,e);
- }
- else
- {
- return 0;
- }
- if(T->right_child)
- {
- return GetNoteRightChild(T->right_child,e);
- }
- {
- return 0;
- }
- }
- }
- /****************************************************************************************************
- *Function Name: GetLeftBrother
- *
- *Function: 如果 T 中存在 e, 则返回其左兄弟
- *
- *Parameter: T: 二叉树头
- * e: 结点值
- *
- *Return Value: 成功返回左兄弟值
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int GetLeftBrother(BiTree T, int e)
- {
- if(T->right_child && T->right_child->data == e)
- {
- if(T->left_child)
- {
- return T->left_child->data;
- }
- }
- else
- {
- if(T->left_child)
- {
- return GetLeftBrother(T->left_child, e);
- }
- if(T->right_child)
- {
- return GetLeftBrother(T->right_child, e);
- }
- }
- return 0;
- }
- /****************************************************************************************************
- *Function Name: GetRightBrother
- *
- *Function: 如果 T 中存在 e, 则返回其右兄弟
- *
- *Parameter: T: 二叉树头
- * e: 结点值
- *
- *Return Value: 成功返回左兄弟值
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int GetRightBrother(BiTree T, int e)
- {
- if(T->left_child && T->left_child->data == e)
- {
- if(T->right_child)
- {
- return T->right_child->data;
- }
- }
- else
- {
- if(T->left_child)
- {
- return GetRightBrother(T->left_child, e);
- }
- if(T->right_child)
- {
- return GetRightBrother(T->right_child, e);
- }
- }
- return 0;
- }
- /****************************************************************************************************
- *Function Name: InsertChild
- *
- *Function: 如果 T 中存在 e, 则 LR 为 1 时, 插入 v 为 e 的左孩子, LR 为 2 时插入 v 为 e 的右孩子, 如果不存在返回 0
- *
- *Parameter: T: 二叉树头指针
- * e: 结点
- * v: 结点
- * LR: 标识
- *
- *Return Value: 成功返回 0, 失败返回 1
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int InsertChild(BiTree *T, int e, int v,int LR)
- {
- BiTree p = NULL;
- if((*T)->data == e)
- {
- if(LR == 1)
- {
- InitBinaryTree(&p);
- p->data = v;
- p->right_child = (*T)->left_child;
- p->left_child = NULL;
- (*T)->left_child = p;
- }
- if(LR == 2)
- {
- InitBinaryTree(&p);
- p->data = v;
- p->right_child = (*T)->right_child;
- p->left_child = NULL;
- (*T)->right_child = p;
- }
- }
- else
- {
- if((*T)->left_child)
- {
- if(InsertChild(&((*T)->left_child),e,v,LR))
- {
- return 1;
- }
- }
- if((*T)->right_child)
- {
- if(InsertChild(&((*T)->right_child),e,v,LR))
- {
- return 1;
- }
- }
- }
- return 0;
- }
- /****************************************************************************************************
- *Function Name: DestroyBinaryTree
- *
- *Function: 销毁二叉树
- *
- *Parameter: 二叉树头指针
- *
- *Return Value: 成功返回 1
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int DestroyBinaryTree(BiTree *T)
- {
- if(*T)
- {
- DestroyBinaryTree(&((*T)->left_child));
- DestroyBinaryTree(&((*T)->right_child));
- free(*T);
- *T = NULL;
- }
- return 1;
- }
- /****************************************************************************************************
- *Function Name: DeleteChildTree
- *
- *Function: 如果 T 中存在 e, 删除 e 结点子树并返回 1, 否则返回 0
- *
- *Parameter: T: 二叉树头指针
- * e: 结点值
- *
- *Return Value: 成功返回 0, 失败返回 1
- *
- *Author:Abel Lee
- *
- *Log:2012-2-19
- ***************************************************************************************************/
- int DeleteChildTree(BiTree *T, int e)
- {
- if((*T)->data == e)
- {
- free(*T);
- *T = NULL;
- return 1;
- }
- else
- {
- if((*T)->left_child)
- {
- if(DeleteChildTree(&((*T)->left_child),e))
- {
- return 1;
- }
- }
- {
- if(DeleteChildTree((&(*T)->left_child),e))
- {
- return 1;
- }
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2962616.html