优享揭阳网站建设,商务网站建设实训过程,wordpress 邮箱登录插件,wordpress仿腾讯一、二叉树定义二叉树是N#xff08;N0#xff09;个节点的有限集#xff0c;它可能是空集或者由一个根节点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。二、二叉树特点1、每个节点最多两个孩子。#xff08;也就是二叉树的度小于等于2#xff09;2…一、二叉树定义二叉树是NN0个节点的有限集它可能是空集或者由一个根节点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。二、二叉树特点1、每个节点最多两个孩子。也就是二叉树的度小于等于22、根有左右之分不可颠倒。3、二叉树可以是空集根的左子树或右子树可以为空。三、图示四、二叉树性质1、性质一深度为k的二叉树至多有2的k次方再减一。推导第一层有一个2的0次方第二层最多有两个2的1次方第三层最多有四个2的2次方。我们可以用等比求和公式Sn(a1-an*q)/(1-q)(1-4*2)/(-1)7。2、性质二在二叉树的第i层上至多有2的i-1次方个节点。3、性质三对任何一棵二叉树T如果其叶子数为n0度为2的节点数为n2n0n21。五、特殊形式的二叉树1、满二叉树1定义和图示满二叉树在相同深度的二叉树中结点数和叶子结点数是最多的。2、完全二叉树1定义和图示深度为k的具有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时称之为完全二叉树。满二叉树是完全二叉树完全二叉树不一定是满二叉树。2特性一具有n个结点的完全二叉树深度为log(2)(n)向下取整1。3特性二如果对一棵有n个结点的完全二叉树深度为log(2)(n)向下取整1的结点按照层序编号从上到下从左到右则对于任一结点i1in有1如果i1则结点i是二叉树的根无双亲。如果是i1则双亲是结点i/2再向下取整。2如果2in则结点i为叶子节点无左孩子否则其左孩子是结点2i。3如果2i1n则结点i无右孩子。否则其右孩子是结点2i1。六、二叉搜索树二叉搜索树Binary Search Tree简称BST如果结点的左子树不为空则左子树存储的数据需要小于结点存储的数据。如果结点的右子树不为空则右子树存储的数据需要大于结点存储的数据。二叉搜索树的中序遍历最终会形成一个从小到大排列的数组。将数组{6,3,8,2,5,1,7}变为一棵BSTBST如下图七、BST结构体1、BinaryTreeNode1描述二叉树结点定义Data数据域LeftNodePtr左子树指针RightNodePtr右子树指针JudegeTreeUsedArray在非递归后续遍历时用到其他并未用到数组长度2分别表示左右子树状态JUDGE_TREE_UNUSED为此树没遍历JUDGE_TREE_USED为此树遍历。2定义#define JUDGE_TREE_UNUSED 0
#define JUDGE_TREE_USED 1
#define JUDGE_TREE_ARRAY_LEN 2typedef int ElemType;typedef struct BinaryTreeNode
{ElemType Data;struct BinaryTreeNode* LeftNodePtr;struct BinaryTreeNode* RightNodePtr;int JudegeTreeUsedArray[JUDGE_TREE_ARRAY_LEN];//为了实现非递归后序遍历使用的数据其他遍历方法未使用。
}BinaryTreeNode, *BinaryTreeNodePtr;2、BinaryTree1描述二叉树结点定义NodePtr树的根节点TreeNodeNum树的总结点数。2定义typedef struct BinaryTree
{BinaryTreeNodePtr NodePtr;BinaryTreeSizeType TreeNodeNum;
}BinaryTree;八、BST函数其中前中后序遍历非递归方法实现需要用到顺序栈可以参考之前写的博客《数据结构与算法基础-学习-09-线性表之栈的理解、初始化顺序栈、判断顺序栈空、获取顺序栈长度的实现》和《数据结构与算法基础-学习-10-线性表之顺序栈的清理、销毁、压栈、弹栈》1、NewBinaryTreeNode1描述生成一个新节点把数据放入结点中。2定义BinaryTreeNodePtr NewBinaryTreeNode(ElemType InputData)
{BinaryTreeNodePtr NewNodePtr (BinaryTreeNodePtr)MyMalloc(sizeof(BinaryTreeNode));NewNodePtr-Data InputData;NewNodePtr-LeftNodePtr NULL;NewNodePtr-RightNodePtr NULL;memset(NewNodePtr-JudegeTreeUsedArray, JUDGE_TREE_UNUSED, sizeof(int) * JUDGE_TREE_ARRAY_LEN);//非递归前序遍历使用Log(New Binary Tree Node : OK\n,Debug);return NewNodePtr;
}3参数介绍参数名描述InputDataElemType类型的数据。2、GetBinaryTreeNodeNum1描述获取BST的总结点数。2定义BinaryTreeSizeType GetBinaryTreeNodeNum(BinaryTree* BT)
{JudgeAllNullPointer(BT);return BT-TreeNodeNum;
}3参数介绍参数名描述BTBinaryTree*类型的BST指针。3、CmpElemTypeData1描述对比ET1和ET2的大小。2定义#define LARGE_FLAG 0
#define LITTLE_FLAG 1
#define EQUAL_FLAG 2Status CmpElemTypeData(ElemType ET1, ElemType ET2)
{if(ET1 ET2){return LARGE_FLAG;}else if(ET1 ET2){return LITTLE_FLAG;}else{return EQUAL_FLAG;}
}3参数介绍参数名描述ET1ElemType类型数据。ET2ElemType类型数据。4、AddBinarySearchTreeNode1描述将InputData数据放入BST中。2定义//假设二叉搜索树中没有相同元素且数据都是正数根节点大于左子树小于右子树。
Status AddBinarySearchTreeNode(BinaryTree* BT, ElemType InputData)
{JudgeAllNullPointer(BT);if(BT-NodePtr NULL){BT-NodePtr NewBinaryTreeNode(InputData);BT-TreeNodeNum;Log(Add BST Node : OK\n,Debug);return SuccessFlag;}BinaryTreeNodePtr TmpPtr BT-NodePtr;while(TmpPtr){if(CmpElemTypeData(TmpPtr-Data, InputData) LARGE_FLAG){if(TmpPtr-LeftNodePtr NULL){TmpPtr-LeftNodePtr NewBinaryTreeNode(InputData);BT-TreeNodeNum;Log(Add BST Node : OK\n,Debug);return SuccessFlag;}TmpPtr TmpPtr-LeftNodePtr;}else if(CmpElemTypeData(TmpPtr-Data, InputData) LITTLE_FLAG){if(TmpPtr-RightNodePtr NULL){TmpPtr-RightNodePtr NewBinaryTreeNode(InputData);BT-TreeNodeNum;Log(Add BST Node : OK\n,Debug);return SuccessFlag;}TmpPtr TmpPtr-RightNodePtr;}else{Log(AddBinarySearchTreeNode function not supported : same element.\n,Debug);Log(Add BST Node : Fail\n,Debug);return FailFlag;}}return FailFlag;
}3参数介绍参数名描述BTBinaryTree*类型的BST。InputDataElemType类型的输入数据。5、NewBinarySearchTree1描述给一个数组生成一棵BST。2定义Status NewBinarySearchTree(BinaryTree* BT, ElemType* Array)
{BinaryTreeSizeType i; for(i 0; i InsertDataArrayLen; i){AddBinarySearchTreeNode(BT, Array[i]);}Log(New Binary Search Tree: OK\n,Info);return SuccessFlag;
}3参数介绍参数名描述BTBinaryTree*类型的BST。ArrayElemType*类型的输入数据数据。6、InitBinaryTree1描述初始化二叉树。2定义Status InitBinaryTree(BinaryTree* BT)
{JudgeAllNullPointer(BT);BT-TreeNodeNum 0;Log(Init Binary Tree : OK\n,Info);return SuccessFlag;
}3参数介绍参数名描述BTBinaryTree*类型的BST。7、InOrderTraverseNoRecursion1描述中序遍历非递归方法实现。2定义Status InOrderTraverseNoRecursion(BinaryTreeNodePtr RootPTR)
{if(RootPTR NULL){return SuccessFlag;}SqStack* S (SqStack*)MyMalloc(sizeof(SqStack));BinaryTreeNodePtr TmpPtr RootPTR;InitSqStack(S);while(TmpPtr || JudgeSqStackIsEmpty(S) FailFlag)//如果指针和栈为空退出循环{if(TmpPtr)//如果节点不为空说明有数据中序遍历左根右。将根压入栈指针指向左子树。{PushSqStack(S, *TmpPtr);TmpPtr TmpPtr-LeftNodePtr;}else//如果节点为空说明左子树没有数据弹栈获取上一层节点指针获取根节点数据再将指针指向右子树。{BinaryTreeNodePtr TmpPtr1 (BinaryTreeNodePtr)MyMalloc(sizeof(BinaryTreeNode));PopSqStack(S, TmpPtr1);Insert2GlobalArray(GA,TmpPtr1-Data);TmpPtr TmpPtr1-RightNodePtr;free(TmpPtr1);TmpPtr1 NULL;}}DestroyStack(S);return SuccessFlag;
}3参数介绍参数名描述RootPTRBinaryTreeNodePtr类型根节点。8、PreOrderTraverseNoRecursion1描述前序遍历非递归方法实现。2定义Status PreOrderTraverseNoRecursion(BinaryTreeNodePtr RootPTR)
{if(RootPTR NULL){return SuccessFlag;}SqStack* S (SqStack*)MyMalloc(sizeof(SqStack));BinaryTreeNodePtr TmpPtr RootPTR;InitSqStack(S);while(TmpPtr || JudgeSqStackIsEmpty(S) FailFlag)//如果指针和栈为空退出循环{if(TmpPtr){PushSqStack(S, *TmpPtr);Insert2GlobalArray(GA,TmpPtr-Data);TmpPtr TmpPtr-LeftNodePtr;}else{BinaryTreeNodePtr TmpPtr1 (BinaryTreeNodePtr)MyMalloc(sizeof(BinaryTreeNode));PopSqStack(S, TmpPtr1);TmpPtr TmpPtr1-RightNodePtr;free(TmpPtr1);TmpPtr1 NULL;}}DestroyStack(S);return SuccessFlag;
}3参数介绍参数名描述RootPTRBinaryTreeNodePtr类型根节点。9、PostOrderTraverseNoRecursion1描述后序遍历非递归方法实现。2定义Status PostOrderTraverseNoRecursion(BinaryTreeNodePtr RootPTR)
{if(RootPTR NULL){return SuccessFlag;}SqStack* S (SqStack*)MyMalloc(sizeof(SqStack));BinaryTreeNodePtr TmpPtr RootPTR;InitSqStack(S);while(TmpPtr || JudgeSqStackIsEmpty(S) FailFlag)//如果指针和栈为空退出循环{if(TmpPtr TmpPtr-JudegeTreeUsedArray[0] JUDGE_TREE_UNUSED){TmpPtr-JudegeTreeUsedArray[0] JUDGE_TREE_USED;PushSqStack(S, *TmpPtr);TmpPtr TmpPtr-LeftNodePtr;}else{BinaryTreeNodePtr TmpPtr1 (BinaryTreeNodePtr)MyMalloc(sizeof(BinaryTreeNode));PopSqStack(S, TmpPtr1);if((TmpPtr1-JudegeTreeUsedArray)[JUDGE_TREE_ARRAY_LEN-1] JUDGE_TREE_USED){//printf(%d %d\n,TmpPtr1-JudegeTreeUsedArray[0],TmpPtr1-JudegeTreeUsedArray[JUDGE_TREE_ARRAY_LEN-1]);Insert2GlobalArray(GA,TmpPtr1-Data);//PrintfGlobalArray(GA,tmp);if(PopSqStack(S, TmpPtr1) FailFlag)//如果栈是空的说明已经完成所有节点的遍历跳出循环。{free(TmpPtr1); TmpPtr1 NULL;break;}}TmpPtr TmpPtr1-RightNodePtr;TmpPtr1-JudegeTreeUsedArray[JUDGE_TREE_ARRAY_LEN-1] JUDGE_TREE_USED;PushSqStack(S, *TmpPtr1);free(TmpPtr1);TmpPtr1 NULL;}}DestroyStack(S);return SuccessFlag;
}3参数介绍参数名描述RootPTRBinaryTreeNodePtr类型根节点。10、InOrderTraverse1描述中序遍历递归方法实现。2定义Status InOrderTraverse(BinaryTreeNodePtr RootPTR)
{if(RootPTR NULL){return SuccessFlag;}else{InOrderTraverse(RootPTR-LeftNodePtr);//printf(%d\n,RootPTR-Data);Insert2GlobalArray(GA,RootPTR-Data);InOrderTraverse(RootPTR-RightNodePtr);}return SuccessFlag;
}3参数介绍参数名描述RootPTRBinaryTreeNodePtr类型根节点。11、PreOrderTraverse1描述前序遍历递归方法实现。2定义Status PreOrderTraverse(BinaryTreeNodePtr RootPTR)
{if(RootPTR NULL){return SuccessFlag;}else{Insert2GlobalArray(GA,RootPTR-Data);PreOrderTraverse(RootPTR-LeftNodePtr);PreOrderTraverse(RootPTR-RightNodePtr);}return SuccessFlag;
}3参数介绍参数名描述RootPTRBinaryTreeNodePtr类型根节点。12、PostOrderTraverse1描述后序遍历递归方法实现。2定义Status PostOrderTraverse(BinaryTreeNodePtr RootPTR)
{if(RootPTR NULL){return SuccessFlag;}else{PostOrderTraverse(RootPTR-LeftNodePtr);PostOrderTraverse(RootPTR-RightNodePtr);Insert2GlobalArray(GA,RootPTR-Data);}return SuccessFlag;
}3参数介绍参数名描述RootPTRBinaryTreeNodePtr类型根节点。九、LINUX环境测试[gbaseczg2 Tree]$ make
gcc -Wall -g ../Log/Log.c BinaryTree.c main.c -o TestBinaryTree -I ../Log/[gbaseczg2 Tree]$ ./TestBinaryTree
2023-3--[Info]--Init Global Array : OK
2023-3--[Info]--Init Binary Tree : OK
2023-3--[Info]--New Binary Search Tree : OK
2023-3--[Info]--PreOrderTraverse : [6 ,3 ,2 ,1 ,5 ,8 ,7 ], CurSize : 7
2023-3--[Info]--InOrderTraverse : [1 ,2 ,3 ,5 ,6 ,7 ,8 ], CurSize : 7
2023-3--[Info]--PostOrderTraverse : [1 ,2 ,5 ,3 ,7 ,8 ,6 ], CurSize : 7
2023-3--[Info]--PreOrderTraverseNoRcs : [6 ,3 ,2 ,1 ,5 ,8 ,7 ], CurSize : 7
2023-3--[Info]--InOrderTraverseNoRcs : [1 ,2 ,3 ,5 ,6 ,7 ,8 ], CurSize : 7
2023-3--[Info]--PostOrderTraverseNoRcs : [1 ,2 ,5 ,3 ,7 ,8 ,6 ], CurSize : 7
