做外贸需要到外汇管理网站,免费网页代理ip地址网站,公司网站建设费分录,wordpress 外国主题1.树
1.1结构特点
非线性结构#xff0c;有一个直接前驱#xff0c;但可能有多个直接后继有递归性#xff0c;树中还有树可以为空#xff0c;即节点个数为零
1.2相关术语
根#xff1a;即根结点#xff0c;没有前驱叶子#xff1a;即终端结点#xff0c;没有后继森…1.树
1.1结构特点
非线性结构有一个直接前驱但可能有多个直接后继有递归性树中还有树可以为空即节点个数为零
1.2相关术语
根即根结点没有前驱叶子即终端结点没有后继森林即树的集合结点的度直接后继的个数树的度结点的度的最大值树的深度高度结点的最大层数
1.3树的表示法
1.3.1图形表示法 1.3.2广义表表示法 1.3.3左孩子右兄弟表示法 将一颗多插树转化为二叉树如下 其中结点结构为
左结点为孩子结点右节点为兄弟结点
2.二叉树
2.1定义
一个根节点和两棵不相交的二叉树组成即1:2
2.2基本特征
每个节点最多有两棵子树——每个节点的度2
左子树和右子树的顺序不能颠倒——有序树
2.3二叉树性质 满二叉树深度为k有2^k-1个节点
完全二叉树除最后一层每一层节点数达到最大值在最后一层只缺右边的若干节点
2.4二叉树的遍历
//单个结点
struct BinaryNode
{char ch;struct BinaryNode* lChild;struct BinaryNode* rChild;
};
void test()
{struct BinaryNode A { A,NULL,NULL };struct BinaryNode B { B,NULL,NULL };struct BinaryNode C { C,NULL,NULL };struct BinaryNode D { D,NULL,NULL };struct BinaryNode E { E,NULL,NULL };struct BinaryNode F { F,NULL,NULL };struct BinaryNode G { G,NULL,NULL };struct BinaryNode H { H,NULL,NULL };//创建节点之间的关系A.lChild B;A.rChild F;B.rChild C;C.lChild D;C.rChild E;F.rChild G;G.lChild H;//先序遍历printf(先序遍历\n);PreorderTraversal(A);printf(中序遍历\n);InorderTraversal(A);printf(后序遍历\n);PostorderTraversal(A);
}
先序遍历DLR
//DLR
void PreorderTraversal(struct BinaryNode* node)
{if (node NULL){return NULL;}printf(%c\n,node-ch);PreorderTraversal(node-lChild);PreorderTraversal(node-rChild);
}
中序遍历LDR
//LDR
void InorderTraversal(struct BinaryNode* node)
{if (node NULL){return NULL;}InorderTraversal(node-lChild);printf(%c\n, node-ch);InorderTraversal(node-rChild);
}
后序遍历LRD
//LRD
void PostorderTraversal(struct BinaryNode* node)
{if (node NULL){return NULL;}PostorderTraversal(node-lChild);PostorderTraversal(node-rChild);printf(%c\n, node-ch);
}
2.5统计二叉树的叶子数量
左孩子和右孩子都为空指针时即为叶子结点
//统计叶子数量
void calculateLeadNum(struct BinaryNode* root, int* p)
{if (root NULL){return NULL;}if (root-lChild NULL root-rChild NULL){(*p);}calculateLeadNum(root-lChild, p);calculateLeadNum(root-rChild, p);
}
2.6统计二叉树的高度
比较左子树和右子树的高度取最大的一个加一即为树的高度
//计算树的高度
int calculateHeight(struct BinaryNode* root)
{if (root NULL){return NULL;}int lp calculateHeight(root-lChild);int rp calculateHeight(root-rChild);int height lp rp ? lp 1 : rp 1;return height;
}
2.7拷贝二叉树
拷贝左子树拷贝右子树创建新节点将拷贝的左子树和右子树挂载到新节点上将新节点赋值
//拷贝二叉树
struct BinaryNode* copyTree(struct BinaryNode* root)
{if (root NULL){return NULL;}struct BinaryNode* lpcopyTree(root-lChild);struct BinaryNode* rpcopyTree(root-rChild);struct BinaryNode* newNode malloc(sizeof(struct BinaryNode));if (newNode NULL){return;}newNode-lChild lp;newNode-rChild rp;newNode-ch root-ch;return newNode;
}
2.8释放二叉树
释放左子树释放右子树释放根节点
//释放二叉树
void releaseTree(struct BinaryNode* root)
{if (root NULL){return NULL;}releaseTree(root-lChild);releaseTree(root-rChild);printf(%c结点已被释放, root-ch);releaseTree(root);
}
2.9二叉树的非递归遍历
将每个节点设一个标志默认false
1将根节点压入栈中
2进入循环只要栈中元素个数大于0进行循环操作
弹出栈顶元素若栈顶元素标志为true输出此元素并执行下一次循环若栈顶元素标志为false将节点标志设为true将该节点的右子树、左子树、根压入栈中执行下一次循环
