1. 二叉树的基本运算

1.1 创建二叉树

str - A(B(D(,G)), C(E,F))

code:

#include<iostream>
using namespace std;

#define MAXSIZE 100

typedef struct BTNode {
	char val;
	BTNode* lchild = NULL;
	BTNode* rchild = NULL;
}BTNode;

BTNode* creatBTNode(char* str) {
	BTNode* root = NULL;
	BTNode* p = NULL;
	int i = 0;
	int k = 1;
	BTNode* St[MAXSIZE];
	int top = -1;
	while (str[i] != '\0') {
		char ch = str[i];
		i++;
		switch (ch) {
		case '(':
			top++;
			St[top] = p;
			k = 1;
			break;
		case ',':
			k = 2;
			break;
		case ')':
			top--;
			break;
		default:
			BTNode* s = (BTNode*)malloc(sizeof(BTNode));
			s->val = ch;
			p = s;
			if (root == NULL) root = s;
			else {
				switch(k) {
				case 1:
					St[top]->lchild = s;
					break;
				case 2:
					St[top]->rchild = s;
					break;
				}
			}

		}
	}
	return root;
}


void main()
{
	char tree[] = "A(B(D(,G)),C(E,F))";
	BTNode* myTree = creatBTNode(tree);
	
}

 

1.2 查找结点

//查找结点
BTNode* FindBTNode(BTNode* r,char ch) {
	if (r == NULL) return NULL;
	if (r->val == ch) return r;
	else {
		BTNode*p = FindBTNode(r->lchild,ch);
		if (p == NULL) {
			BTNode*q = FindBTNode(r->rchild, ch);
			return q;
		}
		return p;
	}
}

1.3 找孩子节点

//查找左孩子和右孩子
BTNode* FindLchild(BTNode* r) {
	return r->lchild;
}
BTNode* FindRchild(BTNode* r) {
	return r->rchild;
}

1.4 求高度

//计算树的高度
int BTNodeHeight(BTNode* r) {
	int lheight, rheight;
	if (r == NULL) return 0;
	else {
		lheight = BTNodeHeight(r->lchild);
		rheight = BTNodeHeight(r->rchild);
		return ((lheight > rheight)? (lheight + 1) : (rheight + 1));
	}
}

1.5 输出二叉树

void DispBTNode(BTNode* r) {
	if (r != NULL) {
		cout << r->val;
		if (r->lchild || r->rchild) {
			cout << '(';
			DispBTNode(r->lchild);
			cout << ',';
			DispBTNode(r->rchild);
			cout << ')';
		}
	}
}